启发式算法
如果在选择节点时能充分利用与问题有关的特征信息，估计出节点的重要性，就能在搜索时选择重要性较高的节点，以利于求得最优解。这个过程称为启发式搜索。
与被解问题的某些特征值有关的控制信息（如解的出现规律、解的结构特征等）称为搜索的启发信息。它反映在评估函数中，评估函数的作用是评估待扩展各节点在问题求解中的价值，即评估节点的重要性。
评估函数:f()= g(x)+ h(x)
g(x)是从初始节点到一个节点x的实际代价。
h(x)是这个节点x到目标节点的最优路径的估计代价，体现了问题的启发式信息，h(x)称为启发式函数。
??????
?
?迭代加深A*算法
迭代加深A*算法:IDA*
设置一个限制值c
只有当节点n的子节点n'的f(n')< c时,才扩展n'节点放到栈中，并且更新c的值(取它和f(n')较小的那个值)
算法终止的条件是:·找到目标节点
·栈为空并且限制值c'= co (可以理解成是一个巨大的值，如100000000)使用IDA*是为了优化空间，节省内存。
A*代码：
#include<queue>
#include<iostream>
#include"stdlib.h"
#include<stack>
#include"math.h "
#define num 9
//伪代码
/*
1 读取初始状态和目标状态
2 将初始节点压入open表中
3 取出open表中估计值最小的节点，放入close表中
4 判断该节点是否为目标节点，不是的话，拓展该节点，将子节点放入open表中，返回上一步
5 将该节点压入栈中，并将指针指向父节点
6 如果父节点不为空，继续5
7 如果栈不为空，出栈并输出该节点
*/
using namespace std;
struct Node {
int state[9]; //用一维数组储存方阵
struct Node* parent; //定义指向其父节点的指针
int value; // 曼哈顿数
int depth; // 深度也就是第几次移动
friend bool operator < (Node A,Node B) { //按照value值+depth值小的方案构造优先级队列
return A.value+A.depth > B.value+B.depth;//最小优先队列
}
};
priority_queue<Node> openTable; //优先级队列open表
queue<Node> closeTable; //普通的队列close表
stack<Node> Path; // 栈用于存储 正确的步骤
int count1=0,count2=0; //判断逆序数奇偶是否相同
int judge(Node& S,Node& G) {
S.parent=NULL; S.depth=0; S.value=0;
G.parent=NULL; G.depth=0; G.value=0;
cout<<"请输入初始状态\n";
for(int i=0; i<num; i++)
cin>>S.state[i];
cout<<"请输入目标状态\n";
for(int i=0; i<num; i++)
cin>>G.state[i];
//将方阵变成线性数列后，计算初始状态和目标状态的逆序数奇偶行是否一致判断是否有解，一致则有解，否则无解。
for(int i=0; i<=num-2; i++)
for(int j=i+1; j<num; j++)
if(S.state[i]>S.state[j]&&S.state[i]*S.state[j]!=0)
count1++;
for(int i=0; i<=num-2; i++)
for(int j=i+1; j<num; j++)
if(G.state[i]>G.state[j]&&G.state[i]*G.state[j]!=0)
count2++;
if(count1%2==count2%2)
{
return 1;
}
return 0;
}
int value(Node A,Node G) {
int count=0,begin[3][3],end[3][3]; //count 记录所有棋子移动到正确位置所需要的步数
for(int i=0; i<num; i++) {
begin[i/3][i%3]=A.state[i];
end[i/3][i%3]=G.state[i];
}
for(int i=0; i<3; i++)
for(int j=0; j<3; j++) {
if(begin[i][j]!=end[i][j]) {
for(int k=0; k<3; k++)
for(int w=0; w<3; w++)
if(begin[i][j]==end[k][w])
count =count+fabs(i-k)+fabs(j-w); //计算每个数字当前状态与最终状态的曼哈顿距离
} else {
continue;
}
}
return count+A.depth;
}
bool equal(Node S,Node G) {
for(int i=0; i<=8; i++) {
if(S.state[i]!=G.state[i]) {
return false;
}
}
return true;
}
void creatNode(Node& S,Node& G) {
//计算原状态下，空格所在的行列数，从而判断空格可以往哪个方向移动
int blank;
for(blank=0; blank<9&&S.state[blank]!=0; blank++); //找到空白格
int x=blank/3,y=blank%3; //获取0所在的编号
for(int d=0; d<4; d++) { //找到S扩展的子节点，加入open表中
int newX=x,newY=y;
Node tempNode;
/*移动空白格*/
if(d==0) newX=x-1;
if(d==1) newY=y-1;
if(d==2) newX=x+1;
if(d==3) newY=y+1;
int newBlank =newX*3+newY; //0新的位置
if(newX>=0 && newX<3 && newY>=0 && newY<3) { //如果移动合法
/*交换格子的内容*/
tempNode = S;
tempNode.state[blank]=S.state[newBlank];
tempNode.state[newBlank] =0;
if(S.parent!=NULL&&(*S.parent).state[newBlank]==0) {
continue;
}
/*把子节点都加入open表中*/
tempNode.parent= &S;
tempNode.value = value(tempNode,G);
tempNode.depth = S.depth+1;
openTable.push(tempNode);
}
}
}
int main()
{
Node S0,Sg; //S0 初始状态 0 1 2 3 4 5 6 7 8 Sg最终状态 1 2 3 8 0 4 7 6 5
if(!judge(S0,Sg)) {
cout<<"此题无解！";
return 0;
}
openTable.push(S0); //入队 将初始节点压入open表中
while(true) {
closeTable.push(openTable.top()); //将open表中优先级最高（估计值最小）的元素压入close表中
openTable.pop(); //删除open表中优先级最高的元素
if(!equal(closeTable.back(),Sg)) { //如果当前棋局与目标棋局不相同，则拓展当前节点，
creatNode(closeTable.back(),Sg);
} else
{
break;
}
}
Node tempNode; //临时变量暂存队前数据
tempNode = closeTable.back(); //back 返回队列的最后一个元素即最后入队的元素
while(tempNode.parent!=NULL) {
Path.push(tempNode); //入栈
tempNode = *(tempNode.parent); //指向父节点
}
Path.push(tempNode);
cout<<"至少要移动"<<Path.size()-1<<"步"<<endl;
/*输出方案*/
while(Path.size()!=0) {
for(int i=0; i<num; i++) {
cout<<Path.top().state[i]<<" ";
if((i+1)%3==0)
cout<<endl;
}
Path.pop();
cout<<"------"<<endl;
cout<<"\n";
}
return 0;
}?
如下是两个启发式搜索的链接，不懂的可以再研究一下：
https://www.bilibili.com/video/BV1gt4y1Q7dt?from=search&seid=10570594341702602487
https://www.bilibili.com/video/BV1QK4y1j7bi?from=search&seid=18017027603264843331