Sunway
table of Contents
1 What is the heuristic search algorithm?
2 first knowledge a * algorithm
The original intention of writing this article is the request of a netizen, of course, I also found that there is now too little Chinese site about artificial intelligence. I will take a brick here, I hope everyone will come to the enthusiasm. Still talking about, I will take a A * algorithm to open the knife, because A * has a typical usage in the game, is the representative of artificial intelligence in the game. A * algorithm is a typical heuristic search algorithm in artificial intelligence, in order to say clearly A * algorithm, I still talk about the heuristic algorithm. 1. What is the heuristic search algorithm that prompts the status space before saying it. Status Space Search, if the professional point is to find the problem solving process as the process of finding this path from the initial state to the target status. Popular point is that when solving a problem, finding a solution process can be the result of solving to the problem (as if it is not popular). Due to many branches in the process of solving the problem, it is mainly the uncertainty of solving conditions during the solution, which makes it unfair to solve the path, which constitutes a picture, we say that this picture is the state space. The solving problem is actually found in this figure, which can be started to the results from the beginning. The process of this search is the state space search. The commonly used state space search has depth priority and breadth priority. The sizzling is to find a layer from the initial state, until the target is found. The depth is preferred to find a branch in front of a certain order, and then find another branch to find the target. These two algorithms have a description in the data structure book, which can be found in more detailed explanation. The broadness and depth priority search for the previous sector has a big defect that they are exhausted in a given state space. This is a very suitable algorithm in the case where the state space is not large, but when the state space is very large, it is not allowed to be taken. His efficiency is too low, or not even. Here you need to use the heuristic search. Heuristic Search is to evaluate each search location in the status space, get the best position, and search from this location until the target. This will omit a large number of fearless search paths to mention efficiency. In heuristic searches, the valuation of the location is very important. Different valuation can have different effects. Let's take a look at how the valuation is expressed. The valuation in inspiration is to use the valuation function, such as:
f (n) = g (n) h (n)
Where f (n) is the estimation function of Node N, G (n) is actually the actual price from the initial node to the n node in the status space, and H (n) is an estimated cost from the N to the target node optimal path. Here, h (n) reflects the inspiration information of the search because g (n) is known. If the detailed point, G (n) represents the broad priority trend of the search. However, when h (n) >> g (n), G (n) can be omitted, and efficiency can be improved. These are deep, don't understand it! We continue to see what is a * algorithm. 2, Item A * Algorithm Heuristic Search In fact, there are many algorithms, such as: local selection of search, preferably priority search, and so on. Of course A * is also. These algorithms use inspiration functions, but the strategy when the specific selection is the best search node. Like the local selection of the search method, it is to choose "Best Nod" after searching for the "best node", and have always been searching for the father's node. The results of this search are obvious. Because of the abandoning other nodes, it may also give up the best nodes, because the best nodes for solving are only the best in this phase is not necessarily the best. It is best to make more smart, when he is searching, there is no discarding node (unless the node is a dead node), the current node and the previous node's valuation value are compared to a "best" in each estimate of each step. Node ". This can effectively prevent the loss of "best nodes". So what kind of algorithm is a * algorithm? In fact, A * algorithm is also a best priority algorithm. Just add some constraints. Due to some problems, we hope to solve the shortest path to solve the status space search, that is, solve the problem with the fastest way, A * is doing this! Let's define next, if an valuation function can find the shortest path, we call it adopt. A * algorithm is an adopted best priority algorithm. A * algorithm's valuation function can be represented as: f '(n) = g' (n) h '(n)
