Menu
I know how this algorithm works, but cant decide when to use which algorithm ?
Are there some guidelines, where one better perform than other or any considerations ?
Thanks very much.
593
BFS is more suitable for searching vertices closer to the given source. DFS is more suitable when there are solutions away from source. 8. BFS considers all neighbors first and therefore not suitable for decision-making trees used in games or puzzles.
BFS can be used to find the shortest path, with unit weight edges, from a node (origional source) to another. Whereas, DFS can be used to exhaust all the choices because of its nature of going in depth, like discovering the longest path between two nodes in an acyclic graph.
Best-first search is informed whereas Breadth-first search is uninformed, as in one has a metal detector and the other doesn't! Breadth-first search is complete, meaning it'll find a solution if one exists, and given enough resources will find the optimal solution.
Best-first search (BFS) expands the fewest nodes among all admissible algorithms using the same cost function, but typically requires exponential space. Depth-first search needs space only linear in the maximum search depth, but expands more nodes than BFS.
If you want to find a solution with the shortest number of steps or if your tree has infinite height (or very large) you should use breadth first.
If you have a finite tree and want to traverse all possible solutions using the smallest amount of memory then you should use depth first.
If you are searching for the best chess move to play you could use iterative deepening which is a combination of both.
IDDFS combines depth-first search's space-efficiency and breadth-first search's completeness (when the branching factor is finite).
69
BFS is generally useful in cases where the graph has some meaningful "natural layering" (e.g., closer nodes represent "closer" results) and your goal result is likely to be located closer to the starting point or the starting points are "cheaper to search".
When you want to find the shortest path, BFS is a natural choice.
If your graph is infinite or pro grammatically generated, you would probably want to search closer layers before venturing afield, as the cost of exploring remote nodes before getting to the closer nodes is prohibitive.
If accessing more remote nodes would be more expensive due to memory/disk/locality issues, BFS may again be better.
32
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
