The shortest path of heuristic algorithm

The so-called shortest path problem has many meanings. Heuristic method here refers to the function h(n) defined on a node of the search tree, which is used to evaluate the cheapest path from this node to the target node. Heuristic algorithms are usually used for well-informed search algorithms, such as the best priority greedy algorithm and A*. The optimal priority greedy algorithm will choose the node with the lowest cost as the heuristic function; A* will choose the node with the lowest cost for g(n)+h(n), which is the real cost of the path from the starting node to the current node. If h(n) is acceptable, that is to say, the cost of h(n) does not exceed the cost of reaching the goal, then A* will definitely find the optimal solution.

The classic problem that can feel the benefits of heuristic algorithm most is n-puzzle. This problem uses this algorithm when calculating the sum of the wrong puzzle graphics, the Manhattan distance of any two puzzles and how far it is from the destination. Note that the above two conditions must be within the acceptable range.