Every algorithms and artificial intelligence class starts with two simple search algorithms: Breadth First Search (BFS) and Depth First Search (DFS). They are used in data structures like trees, which is basically a network/graph of nodes that have values or states associated with them. What makes a tree a tree? Find out here.
BFS and DFS are two kinds of search algorithms in which you follow a certain path to to go through each node until you find the goal node. They are uninformed searches, meaning you do not know whether one non-goal node is better than another non-goal node. This way you do not know whether the path that you are following is better than any other path that you could follow.
Now onto search strategies. Both strategies start with expanding a parent/start node s: i.e. recording its successor nodes.
Assume the following relationship:
- s is the starting node
- a and b are successor nodes of s
- x is a successor of a
In BFS, every direct successor of s will be checked for solution before moving onto its successors' successors. So a and b are checked for solution before checking x. The path will look something like this:
In DFS, after expanding s, its first direct successor is checked for solution. If its not the goal node, we move on to the successor node of s's first direct successor node. So, a and x are checked for solution before b. The path for DFS looks like this:
Performance wise, one search strategy is not necessarily better than the other. Detailed comparisons here.
BFS and DFS are two kinds of search algorithms in which you follow a certain path to to go through each node until you find the goal node. They are uninformed searches, meaning you do not know whether one non-goal node is better than another non-goal node. This way you do not know whether the path that you are following is better than any other path that you could follow.
Now onto search strategies. Both strategies start with expanding a parent/start node s: i.e. recording its successor nodes.
Assume the following relationship:
- s is the starting node
- a and b are successor nodes of s
- x is a successor of a
In BFS, every direct successor of s will be checked for solution before moving onto its successors' successors. So a and b are checked for solution before checking x. The path will look something like this:
In DFS, after expanding s, its first direct successor is checked for solution. If its not the goal node, we move on to the successor node of s's first direct successor node. So, a and x are checked for solution before b. The path for DFS looks like this:
Performance wise, one search strategy is not necessarily better than the other. Detailed comparisons here.
0 comments:
Post a Comment