JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
<< PREV    [ 1 2 ]
Re: Will this dfs work? (response to post by misof) | Reply
This is very cool, Misof.

One question, is there any reason why there is only one stack? If we use one stack for the local variable neighbor, and one for the current node index, is it basically the same thing?

I'm guessing that you are using one stack because you are simulating what happens if you use an actual recursive function call? Does it make any difference as far as efficiency / speed are concerned?

I guess maybe system memory management of two stacks is harder than for a single one?
Re: Will this dfs work? (response to post by hughperkins) | Reply
Ok, nm, after playing, using a single stack is much easier than using multiple ones.
Re: Will this dfs work? (response to post by misof) | Reply
I tried translating/simplifying misof's code above, not sure if its correct, if anyone spots an error, kindly correct me before i go astray. In the meanwhile, i am still puzzled by backtracking that misof mentioned. Can someone kindly give an example on how backtracking can be used, especially within a dfs template. Thanks in advance.

Mafoko.


int g[N][N];
int visited[N];
 
void dfs(int x){ //recursive
  for(n=0;n<N:++n) if (g[x][n]&&!visited[n]) {visited[n]=1;dfs(n);}
  visited[x]=0;//for backtracking
}
 
void dfs(int x) { //iterative
  stack<int> s;
  s.push(x);
  visited[x]=1;
  while (!s.empty()) {
    int t = s.top(); s.pop();
    for(n=0;n<N;++n){if (g[t][n]&&!visited[n]) {visited[n]=1; s.push(n);}}
    visited[t]=0;//for backtracking
  }
}


[edit] There is a problem with iterative code above, sorry, still fixing it :-|
Re: Will this dfs work? (response to post by mafoko) | Reply
Shift operations are usually faster operations than multiply and especially divide.
Re: Will this dfs work? (response to post by hughperkins) | Reply
Perhaps of interest is the fact that some architectures have a seperate stack for "data" than for "instruction pointers". This is useful in a number of ways. Reading the invocation stack becomes trivial, since there is no data on it. Corruption of the invocation stack becomes very difficult. I'm sure there are other benefits.

Probably a downside in # of transistors and added complexity - but there is usually a trade off.
Re: Will this dfs work? (response to post by gladius) | Reply
The other glaring issue I saw in this article is the section on BFS:

// Now we need to generate all of the transitions between nodes, we can do this quite easily using some
// nested for loops, one for each direction that it is possible for one player to move.  Since we need
// to generate the following deltas: (-1,-1), (-1,0), (-1,1), (0,-1), (0,0), (0,1), (1,-1), (1,0), (1,1)
// we can use a for loop from -1 to 1 to do exactly that.
for (int player1XDelta = -1; player1XDelta <= -1; player1XDelta++) {
  for (int player1YDelta = -1; player1YDelta <= -1; player1YDelta++) {
    for (int player2XDelta = -1; player2XDelta <= -1; player2XDelta++) {
      for (int player2YDelta = -1; player2YDelta <= -1; player2YDelta++) {


The loops should obviously go from -1 to 1, not -1 to -1. I think that was the author's intent, and he even says so in the comment, it's just incorrect in the actual pseudocode.
<< PREV    [ 1 2 ]

RSS