|
Sequential Search Algorithms Is the search space a tree or a graph?
|
səhifə | 6/23 | tarix | 26.12.2016 | ölçüsü | 0,99 Mb. | | #3369 |
|
Is the search space a tree or a graph? The space of a 0/1 integer program is a tree, while that of an 8-puzzle is a graph. This has important implications for search since unfolding a graph into a tree can have significant overheads.
Two examples of unfolding a graph into a tree.
Depth-First Search Algorithms Applies to search spaces that are trees. DFS begins by expanding the initial node and generating its successors. In each subsequent step, DFS expands one of the most recently generated nodes. If there exists no success, DFS backtracks to the parent and explores an alternate child. Often, successors of a node are ordered based on their likelihood of reaching a solution. This is called directed DFS.
Dostları ilə paylaş:
|
|
|