Heuristic search strategy

Reference resources    Heuristic search strategy - cloud + Community - Tencent cloud

Search for It is the main strategy to solve problems in artificial intelligence , Looking at 《 Artificial intelligence , A modern way 》 When , Found this search algorithm . But the book is mainly about theory , The following is a summary of the algorithm and a comparison with ACM Combined training of .

1、 Blind search

No information search （ Blind ） Search strategy , In addition to Problem definition Provided in State information Outside , No additional information . The search will only be carried out blindly . The search method is as follows ：

1. Width first search （BFS）
2. Consistent cost search （ class Dijkstra Shortest path search algorithm ）
3. Depth-first search （DFS）
4. Depth limited search （ A tree used to control infinite depth , Define a depth search boundary l）
5. Iterative depth first search （ Used in conjunction with depth first search to determine the best depth bounds ）
6. Two way search （ Search from both sides at the same time , because bd/2+bd/2 than dd Many small ）

The above search is among the questions I have done before , More or less . But because the scope of the question is limited , The depth of search is not very high . Once you encounter a deep search tree , It's embarrassing .

2、 Heuristic search

There's information （ heuristic ） Search can tell whether a non target state is better than other states “ More promising ” Get close to the target , So as to achieve better search results than blind search

First , What is the target state , What is the non target state

The figure below is an eight digit problem . Numbers near empty cells can be moved to empty cells ., How can the left square state change into the right square state after moving .

                           

namely , The state of the box on the left is the non target state , The state of the grid on the right is the target state

The average solution of a randomly generated eight digit problem is 22 Step . The branching factor is about 3（ The branching factor is the number of possible steps per move , There are four ways to move in the middle , There are only two ways to move around the four corners , There are three ways to move on the four sides ）

That means , Reach a depth of 22 The exhaustive search tree will consider 322≈3.1×1010 Status , Graph search can reduce this number to about 170000 times , Because only 9!/2=181440 A different state .

But if you extend to 15 Digital problems （3×3 become 4×4）, Then the number is about 1013, A huge set of states can crash your computer directly , So we need to find a good heuristic function

Here we describe two commonly used heuristic functions ：

• h1 = The number of pieces not in position , Pictured above , In the initial state ,h1 = 8（ All the pieces are not in the right position ）
• h2 = The sum of the distances from all the pieces to their target positions . Because the pieces can't move sideways , The distance is equal to the sum of the horizontal and vertical distances , Also known as Manhattan distance , See Manhattan distance in the above figure h2 = 3+1+2+2+2+3+3+2=18

So here comes the question , What is the use of these two heuristic functions ,h1 and h2 Can you help us better solve the eight digit problem ？

What is the use of heuristic functions ？

First we define ：f(n) = g(n) + h(n)

among ,f(n) Is the total cost from the initial state to the target state .g(n) Is the path cost from the initial state to the target state , and h(n) Is the estimated value of the minimum cost path from the initial state to the target state , That is, a heuristic function . Then we assume that the empty lattice is in the middle . Then the empty grid can be moved up （ We move other numbers into the empty grid as if the empty grid were moved over ）, Move down , Move left , Move right . These four directions g(n) All are 1. That is, it only costs 1 The cost of one step can reach the goal .h(n) Here we use the above h2, It can be proved that h2 The efficiency of is always higher than h1（ It is self-evident that ）. Then the four states of up, down, left and right can calculate four different h(n), By choosing the smallest h(n), Move on to the next step . because g(n) All are 1, therefore f(n) The comparison of is h(n) Comparison .

Is it a little Dijkstra Algorithm means , One is from A->B, When choosing each step of action , Is to choose the nearest road , Then refresh the distance from all points to the end point . And heuristic search , stay g(n) Can be equal , It is based on h(n) To choose the path of action

actual combat

#include <iostream>
#include <cstring>
#include <cmath>
#include <queue>
#define inf 0x7fffffff   // Maximum value of an integer 
using namespace std;
struct node{
    int map[3][3],x,y,f,g,h;
    friend bool operator < (node a,node b){
        return a.f > b.f;   // Automatic sorting from small to large 
    }
}start,target;  // Define start state and target state 
int step[400010],v[400010],book[400010],targetNum=46234;
char str[4]={'u','d','l','r' };
int Can[10]={1,1,2,6,24,120,720,5040,40320 };  // A fully arranged compressed sequence 
int an[4][2]={-1,0, 1,0, 0,-1, 0,1 };  // Up, down, left and right 
int Cantor(node cur){ // Cantor unfold 
    int an[10],k=0,sum=0;
    for (int i=0 ;i<3 ;i++)
        for (int j=0 ;j<3 ;j++)
            an[k++]=cur.map[i][j];  // Convert two dimensions to one dimension 
    for (int i=0 ;i<9 ;i++){
        int k=0;
        for (int j=i+1 ;j<9 ;j++)
            if (an[i]>an[j]) k++;
        sum += k*Can[9-i-1];  // Find out which number of the current full permutation is the initial full permutation 
    }
    return sum+1;
}
int checkRoad(node an) {  /// Judge the parity at this time （ Because each exchange does not change its parity ）
    int a[10],k=0,sum=0;
    for (int i=0 ;i<3 ;i++)
        for (int j=0 ;j<3 ;j++)
            a[k++]=an.map[i][j];  // The binary state space is transformed into one dimension 
    for (int i=0 ;i<k ;i++) 
        if (a[i]!=0)
            for (int j=0 ;j<i ;j++)
                if (a[j]>a[i]) sum ++;  // Determine whether the movement needs to change in reverse order 
    if (sum&1) return 0;   // Odd returns 0
    return 1;  
}
void printRoad(node cur){   // Output moving path 
    string ans;
    int sum=targetNum;
    while (step[sum] != -1){  // If the previous state exists 
        switch (v[sum]) {  // Select the steps from the previous state to this state 
            case 0 : ans += str[0];break;
            case 1 : ans += str[1];break;
            case 2 : ans += str[2];break;
            case 3 : ans += str[3];break;
        }
        sum=step[sum];
    }
    for (int i=ans.size()-1; i>=0; i--)  cout<<ans[i];
    cout<<endl;
    return ;
}
int getH(node cur){
    int sum=0;
    for (int i=0 ;i<3 ;i++)
        for (int j=0 ;j<3 ;j++){
            int u = cur.map[i][j];
            int x = u>0?(u-1)/3:2, y = u>0?(u-1)%3:2;
            sum += abs(x-i)+abs(y-j);
        }
    return sum;
}
void aStar(node cur){
    priority_queue<node> Q;  // Priority queue , The default is from large to small 
    cur.g=0; 
    cur.h=getH(cur);  // To get this status h value 
    cur.f=cur.g + cur.h;
    Q.push(cur);  // take f Save as a comparison keyword to Q in 
    memset(book,-1,sizeof(book));   // initialization 
    memset(step,-1,sizeof(step));
    memset(v,-1,sizeof(v));
    book[Cantor(cur)]=1;   // The tag already has this status 
    while (!Q.empty()){
        cur=Q.top();Q.pop();  // Get the minimum path state 
        if (Cantor(cur)==targetNum){  // If you have reached your goal 
            printRoad(cur);   // Print the walking path 
            return ;
        }
        for (int i=0 ;i<4 ;i++){   // Move up, down, left and right 
            target.x=cur.x+an[i][0];
            target.y=cur.y+an[i][1];
            int x=cur.x ,y=cur.y ;
            for (int u=0 ;u<3 ;u++)  // Initialize the state after the move 
                for (int v=0 ;v<3 ;v++)
                    target.map[u][v]=cur.map[u][v];
            if (target.x<0||target.x>=3||target.y<0||target.y>=3) continue;  // Make sure you don't move out of the grid 
            swap(target.map[target.x][target.y],target.map[x][y]);
            int sum=Cantor(target);
            if (book[sum]==-1){   // If this state does not exist 
                if (checkRoad(target)==0) continue;
                book[sum]=1;
                target.g=cur.g+1;  // The paths are the same 1
                target.h=getH(target);   // Get new h value 
                target.f=target.g+target.h;
                step[sum]=Cantor(cur);  // Used to mark the status of the previous 
                v[sum]=i;  // Used to mark the direction of travel 
                Q.push(target);   
            }
        }
    }
    return ;
}
int main(){
    char str[100];  // Stored the initial string 
    while (cin.getline(str,100)){  // Read in 
        int tx=0,ty=0;
        for (int i=0 ;i<strlen(str) ;i++){   // Traverse the read string 
            if (str[i]>='0' && str[i]<='9') {
                start.map[tx][ty]=str[i]-'0';  // Initialization start state 
                if (++ty==3) {tx++;ty=0; }
            } else if (str[i]=='x') {
                start.map[tx][ty]=0;  // take x With 0 Form storage of 
                start.x=tx ;start.y=ty ;  // Record start x Coordinates of 
                if (++ty==3) {tx++;ty=0; }
            }
        }
        if (checkRoad(start)==0) {  // Determine if you can move to 
            cout<<"unsolvable"<<endl;
            continue; 
        } 
        aStar(start);
    }
    return 0;
}

priority_queue It's a priority queue , Every time you insert a new element , The interior will be rearranged . In structure node We overloaded the operator in <, in other words , The first element of the priority queue , namely top() The value obtained , Is the smallest in the queue . Because the up, down, left, right and four moving states are compared, additional storage is required , So we use priority queues , The comparison step is omitted , How to get the heuristic function , We have seen h1（ Number of misplaced pieces ） and h2（ Manhattan distance ） It is a good heuristic for the eight digit problem , and h2 Better . that h2 How it was extracted , In the field of artificial intelligence , Can computers mechanically design such heuristics ？

The answer is yes

h1 and h2 It estimates the length of the remaining path in the eight digit problem , For a simplified version of the problem, they are also fairly accurate path lengths . If the rules of the game are changed to that each piece can move freely , Instead of being able to move to an empty space adjacent to it , that h1 Is the exact number of steps of the shortest solution . Allied , If a piece can move in any direction , You can even move to a position occupied by other pieces , that h2 The exact number of steps of the shortest solution will be given . Reduced the problem of movement restrictions , We call it the relaxation problem . Any optimal solution of the original problem is also the optimal solution of the relaxation problem ; But the relaxation problem may have a better solution , The reason is that the added edge may lead to a shortcut .