Let's take a look at the diagram below: This is a pretty typical problem, no? We have a starting point, and ending point, and a bunch of roads we can take to get there. We can even abstract this so that the roads are "moves" (of, say, a little sliding puzzle) and the points are states of the puzzle. Our goal is to find the shortest path possible to the end node in the fewest moves — and not take a long time to find it! Depth First Search (dfs) The simplest (and least efficient) method of traversing a graph is the Depth First Search (dfs). Recursion suits this method well. Examine the pseudocode for a simple dfs: 1: 2: 3: 4: 5: 6: 7: 8: // Simple dfs function dfs(node position) color(position) for each successor adjacent to node "position" if successor is colored, skip it if next is the goal node, stop the search else, dfs(successor) end end ... Breadth First Search (bfs) Yep, you saw it coming.
Read full article from Searching using A* (A-Star)
No comments:
Post a Comment