What are the problems associated with the first search in artificial intelligence?

Question

I know that common problems include local highs and plateaus, however, I am curious if there are any problems associated with this particular search, and what is my best course of action to solve these problems.

Can someone give me an example of what problem this search would be useful for?

Answer 1

Problems with the best first search:

• This is greedy. In many cases, this leads to a very quick solution (since the number of developed nodes does not increase exponentially, the solution increases linearly with depth!), However, it is usually not optimized because your heuristic function has some error and sometimes the answer that the next node to study is wrong .

• There is also a problem with an infinite branch. Suppose you are after a branch where a node at depth i has a heuristic value h(v_i) = 2^-i . You will never achieve zero, but at first the greedy will continue to develop these nodes.
  Example:

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

Please note that the above is a valid heuristic function , but, nevertheless, the best first search will never get a solution, it will get stuck in an infinite branch.

Solutions:

• To overcome this, we can use a unified algorithm (such as Dijkstra's algorithm or BFS for unweighted graphs)
• You can use the combination of "best first search" and Dijkstra, which is known as the A * algorithm. The A * algorithm is actually the greedy best first algorithm, but instead of choosing according to h(v) , you have chosen which node to explore further with f(v) = h(v) + g(v) ( where g(v) is “still cost.” The algorithm is complete (finds a solution if it exists) and is optimal (finds a “best” solution) if it is assigned a valid heuristic function .

When to use Best First Search anyway:

• If you have a perfect heuristic (denoted by h* in the literature), the best first search will find the optimal solution - and quickly.
• If you don’t care about the optimal solution, you just want to quickly find one solution - this is usually a trick (but you need to be careful for the problem with an infinite branch).
• When we use A *, we actually use the best first search, but instead of f:V->R instead of h:V->R