About heuristic search

I definition:

As the name suggests, heuristic search is definitely not an ordinary search, but has done some inspiration and Optimization on the ordinary search.
Generally, there are two types of \ \ * search heuristic (ID A search first), one of which is breadth first search algorithm

II Basic functions:

1. Distance function \ (g(x) \):
It is used to calculate the distance from the current point to the starting point, that is, the cost consumed.
2. Valuation function \ (h(x) \):
It is used to estimate the distance from the current point to the end point in the optimal case, that is, the cost to be consumed.
3. Calculation function \ (f(x) \):
Calculate the sum of distance function and valuation function.

III Legend analysis:

\The operation steps of (A \) * algorithm are shown in the figure, which can greatly reduce the time complexity of burst search

However, there are some extreme special situations that need attention:

IV matters needing attention:

It must be noted here that the appraisal must be less than or equal to the actual value, because if the appraisal is larger than the actual value, in some cases, the larger actual value may be taken out, which will lead to wrong answer.

Typical examples

Example 11 Bentong 1251 Fairy Island for medicine

Although this problem can be easily solved by explosive search, and the data range is very small, it can be used to practice heuristic search.
The following shows the code of heuristic search in the form of structure.

Code

#include<bits/stdc++.h>
using namespace std;

int n,m,ex,ey;

char s[25][25]; 
bool vis[25][25];  

struct Node
{
	int x;
	int y; 
	int g;
	int h;
	int f;
	bool operator<(const Node b)const
	{
		return f>b.f;
	}
}start;

int dx[]={0,0,1,-1};  
int dy[]={1,-1,0,0}; 

inline int bfs()
{
	memset(vis,false,sizeof(vis));
	priority_queue<Node>q;
	start.g=0;
	start.h=abs(start.x-ex)+abs(start.y-ey);
	start.f=start.g+start.h;
	q.push(start);
	vis[start.x][start.y]=true;
	while(!q.empty())
	{
		Node now=q.top();
		q.pop();
		for(register int i=0;i<=3;i++)
		{
			int nx=now.x+dx[i];
			int ny=now.y+dy[i];
			if(nx<1||ny<1||nx>m||ny>n||s[nx][ny]=='#'||vis[nx][ny]==true)
				continue;
			if(s[nx][ny]=='*')
				return now.g+1;
			Node nxt;
			nxt.x=nx;
			nxt.y=ny;
			nxt.g=now.g+1;
			nxt.h=abs(nxt.x-ex)+abs(nxt.y-ey);
			nxt.f=nxt.g+nxt.h;
			q.push(nxt);
			vis[nxt.x][nxt.y]=true; 
		}
	}
	return -1;
}


int main()
{
	while(cin>>m>>n)
	{
		if(m==0&&n==0)
			return 0;
		for(register int i=1;i<=m;i++)
		{
			for(register int j=1;j<=n;j++)
			{
				cin>>s[i][j];
				if(s[i][j]=='@')
					start.x=i,start.y=j;
				if(s[i][j]=='*')
					ex=i,ey=j;
			}
		}
		
		printf("%d\n",bfs());
	}
	return 0;
}

Here are some points that can be optimized. When you see the data range \ (n,m \le 20 \), you can think of using a number of up to four digits to represent its state, and then you can optimize the tag array \ (vis_i \) into one dimension.

Code

#include<bits/stdc++.h>
using namespace std;

int n,m,e;

char s[25][25]; 
bool vis[2025];  

struct Node
{
	int state; 
	int g;
	int h;
	int f;
	bool operator<(const Node b)const
	{
		return f>b.f;
	}
}start;

int dx[]={0,0,1,-1};  
int dy[]={1,-1,0,0}; 

inline int bfs()
{
	memset(vis,false,sizeof(vis));
	priority_queue<Node>q;
	start.g=0;
	start.h=abs(start.state/100-e/100)+abs(start.state%100-e%100);
	start.f=start.g+start.h;
	q.push(start);
	vis[start.state]=true;
	while(!q.empty())
	{
		Node now=q.top();
		q.pop();
		for(register int i=0;i<=3;i++)
		{
			int nx=now.state/100+dx[i];
			int ny=now.state%100+dy[i];
			if(nx<1||ny<1||nx>m||ny>n||s[nx][ny]=='#'||vis[nx*100+ny]==true)
				continue;
			if((nx*100+ny)==e)
				return now.g+1;
			Node nxt;
			nxt.state=nx*100+ny;
			nxt.g=now.g+1;
			nxt.h=abs(nx-e/100)+abs(ny-e%100);
			nxt.f=nxt.g+nxt.h;
			q.push(nxt);
			vis[nxt.state]=true; 
		}
	}
	return -1;
}


int main()
{
	while(cin>>m>>n)
	{
		if(m==0&&n==0)
			return 0;
		for(register int i=1;i<=m;i++)
		{
			for(register int j=1;j<=n;j++)
			{
				cin>>s[i][j];
				if(s[i][j]=='@')
					start.state=i*100+j;
				if(s[i][j]=='*')
					e=i*100+j;
			}
		}
		
		printf("%d\n",bfs());
	}
	return 0;
}

Example 2

Posted by balsdorf on Fri, 13 May 2022 02:30:07 +0300