Compare different search algorithms

In what ways are DFS and Best-first search similar? How are BFS and Best-first similar?

To me, to better decribe how DFS and BestFS are similar, it might be easier to point the difference,which is that in BestFS we chose as the next to expand the one that seems closest to the goal using the heuristi function. In almost all other ways both of the best and DFS are similar.

However I find it ha开发者_JS百科rd to find the similarities between BFS and BestFS

---

Okay imagine you have a tree. You know it has one leaf with the data you want Suppose you want to find that leaf by traveling over the various branches of the tree until you find it.

With Depth First search, if you came across a branch, you would take that branch, and then take another branch and another and another until you get to a leaf.

With a Breadth first search (notice I didn't say 'best first' here) when you come across a new branch you add it to a queue to come back to later until you find all branches at the current level. Normally when people say "BFS" they mean Breadth First search, not Best First.

So what about Best first search, like you asked about? Well, suppose you're doing a depth first search and you come across two branches. With a DFS, you just pick the first one each time, later on, you'll come back and pick the other one.

With Best first search you pick a branch with the highest heuristic value, based on some heuristic you're using to help guess the best path. So a Best First search is a type of Depth first search.

Wikipedia is very helpful for these kinds of questions, btw.

---

Best First Search is a type of informed search and suits well in scenarios where some information about the state space you are searching is known. This acquaintance with the state space or the system you are working in, helps in developing a heuristic which decides the best node at each search step. In a nutshell, Best First Search uses Greedy paradigm to approach a goal i.e. your search target.

Depth First Search and Breadth First Search are uninformed search methods and are handy when you know nothing about the system you are dealing with. They have their own trade-offs (among themselves) in terms of memory and guarantee to find a solution (if it exists). You can check the details in Wiki.

I don't see much of a similarity between the uninformed search and informed search methods except that they help solve the search problem. Another aspect on which the similarity can be argued is whether a search is complete (search method is called complete when it returns a solution whenever one exists) and optimal (search method is optimal when it returns a minimum cost path solution whenever a solution exists).

Breadth First Search - Complete and Optimal (if all edges have unit cost)

Depth First Search - Complete (for finite search tree) and not optimal

Best First Search - Complete and Optimal

The key is to know which one to use in what situation.

I hope this helps.

cheers