What are the problems associated to Best First Sea

问题:

I Know general issues include local maxima and plateaus however I am curious if there is any more issues associated to this specific search and what my best course of action would be in order to overcome these issues.

Can someone also give me an example of which sort of problem this search would be good to use for?

回答1:

Problems with best first search:

1. It is greedy. In many cases it leads to a very quick solution (because your number of developed nodes does not increase exponentially, it is increased linearly with the depth of the solution!), however it is usually not optimized, because your heuristic function has some error and sometimes gets the wrong answer which next node to explore.

2. There is also an issue with an infinite branch. Assume you are following a branch where node at depth i has a heuristic value of h(v_i) = 2^-i. You will never get to zero, but greedy best first will keep developing these nodes.
   Example:

                           2
                          / \  
                         /   \
                        /     \
                       1      1.5
                       |       |
                      1/2      1
                       |       |
                      1/4      0
                       |
                      1/8
                       |
                      1/16
                       |
                      ... 
   

Note that the above is admissible heuristic function, but nevertheless best first search will never get the solution, it'll get stuck in the infinite branch.

Solutions:

1. To overcome it, we can use an uniformed algorithm (such as Dijkstra's algorithm or BFS for unweighted graphs)
2. You can use a combination of "best first search" and Dijkstra, which is known as A* algorithm.
   A* Algorithm is actually a greedy best first algorithm, but instead of choosing according to h(v), you chose which node to explore next with f(v) = h(v) + g(v) (where g(v) is the "so far cost". The algorithm is complete (finds a solution if one exists) and optimal (finds the "best" solution) if it is given an admissible heuristic function.

When to use Best First Search anyway:

1. If you have a perfect heuristic (denoted as h* in the literature), best first search will find an optimal solution - and fast.
2. If you don't care about optimal solution, you just want to find one solution fast - it usually does the trick (but you will have to be careful for the infinite branch problem).
3. When we use A*, we actually use best first search - but on f:V->R instead of on h:V->R.