hello everyone can anybody help me with the DFS algorithm : Path* agent_DFS (void* arg1,...); which is written on C program and is about Artificial intelligence which I have to find a way for a car to his goal ..?? it returns an array of type path I got absoloutely no idea about that ... please help me
A:
In order to know where the car is in the maze with respect to where it came from, it keeps track of all moves made (north, east, west, south). Whenever you backpedal, it doesn't add to the path, but rather removes from it (what point is there to know that you've been to a dead-end and come back for example?).
Neil
2010-10-28 09:49:26
Well, remembering this is useful, so that you don't choose that route again (if you return to a junction).
Oli Charlesworth
2010-10-28 11:05:37
Well I suppose it really depends on how the algorithm works. If you always stuck to the left, it wouldn't matter but then, I don't know how this AI works.
Neil
2010-10-29 09:48:02
A:
Recursion is useful for implementing this.
Remembering if a location is on your current path as you traverse it will help you not to go in circles. You may also want to remember which addresses that you have not yet been to (interesting paths) and addresses you have already decided were dead ends (or at least not helpful in reaching your goal).
If you are looking for the optimal path then remembering how far (through the maze) each address on a path is from both the beginning and the end (on the shortest path discovered that goes through that address) is also helpful. The sum of both of these distances should be the same for all addresses along the shortest paths (paths because their could be more than one path with the same distance), by the way.
nategoose
2010-10-28 15:40:53
A:
thanks I understood what's going on but I need a code can anyone help me ?
navid
2010-10-29 14:57:49
Ok. Start from determining what is the output and what is the input. For example the input is the Graph G which can be implemented in a various of ways and the output is a sequence composed of Vertices that are in accordance with what you are trying to solve, in this case going from point A to point B. If you got that clear then DFS is fairly easy to follow and implement as an algorithm.
Cristina
2010-10-29 15:34:29