0x01 前言
昨天遇到八数码问题,瞬间想到小时候玩的拼图游戏,大概长这样
(图片来源于百度图片)
看似简单但是印象中就没成功过……,不过,利用启发式搜索,这个问题就是秒解了,接下来介绍两种解决八数码问题的方法,本人认为这是启发式搜索的两种实现方式。
0x01 启发式搜索0
第一种方法较简单,步骤如下:
1.计算初始评估值,这里评估值是不在正确位置的点的数量。
2.利用队列搜索,从四个方向移动空格获得新节点,计算新节点的评估值。
3.如果新节点评估值小于等于父节点评估值+1,就是优秀节点,加入队列。
4.直到找到评估值为0的节点,就是结果。
代码如下:
//代码来源于blog.csdn.net/wangqiuyun/article/details/7840771
加入了少许注释。
#include <iostream> #include <stdio.h> #include <stdlib.h> #include <time.h> using namespace std; #define N 3 //数码组大小 #define Max_Step 50 //最大搜索深度 #define MAX 50 typedef struct node//八数码结构体 { int form[N][N];//数码组 int evalue;//评估值 int udirect;//所屏蔽方向,防止往回推到上已状态,1上2下3左4右 struct node *parent;//父节点 }Graph; Graph *Qu[MAX];//队列 Graph *St[MAX];//堆栈 /////////打印数码组 void Print(Graph *The_graph) { int i,j; if(The_graph==NULL) printf("图为空\n"); else { printf("---------------------\n"); for(i=0;i<N;i++) { printf("|\t"); for(j=0;j<N;j++) { printf("%d\t",The_graph->form[i][j]);//遍历打印 } printf("\t|\n"); } printf("|\t\t\t差距:%d\t|\n",The_graph->evalue);//差距显示 printf("---------------------\n"); } } /////////评价函数 int Evaluate(Graph *The_graph,Graph *End_graph) { int valute=0;//差距数 int i,j; for(i=0;i<N;i++) { for(j=0;j<N;j++) { if(The_graph->form[i][j]!=End_graph->form[i][j]) //if num is not in right site,valute++ { valute++; } } } The_graph->evalue=valute; return valute; } /////////移动数码组 Graph *Move(Graph *The_graph,int Direct,int CreatNew_graph) { Graph *New_graph;// int HasGetBlank=0;//是否获取空格位置 int AbleMove=1;//是否可移动 int i,j,t_i,t_j,x,y; for(i=0;i<N;i++)//获取空格坐标i,j { for(j=0;j<N;j++) { if(The_graph->form[i][j]==0) { HasGetBlank=1; break; } } if(HasGetBlank==1) break; } //printf("空格位置:%d,%d\n",i,j); t_i=i; t_j=j; //移动空格 switch(Direct) { case 1://上 t_i--; if(t_i<0) AbleMove=0; break; case 2://下 t_i++; if(t_i>=N) AbleMove=0; break; case 3://左 t_j--; if(t_j<0) AbleMove=0; break; case 4://右 t_j++; if(t_j>=N) AbleMove=0; break; } if(AbleMove==0)//不能移动则返回原节点 { return The_graph; } if(CreatNew_graph==1) { New_graph=(Graph *)malloc(sizeof(Graph));//生成节点 for(x=0;x<N;x++) { for(y=0;y<N;y++) { New_graph->form[x][y]=The_graph->form[x][y];//复制数码组,save every statuses. } } } else { New_graph=The_graph; } //移动后 New_graph->form[i][j]=New_graph->form[t_i][t_j]; //0 change to num New_graph->form[t_i][t_j]=0; //num change to 0 //printf("移动产生的新图:\n"); //Print(New_graph); return New_graph; } /////////搜索函数 Graph *Search(Graph *Begin,Graph *End) { Graph *g1,*g2,*g; int Step=0;//深度 int Direct=0;//方向 int i; int front,rear; front=rear=-1;//队列初始化 g=NULL; rear++;//入队 Qu[rear]=Begin; while(rear!=front)//队列不空 { front++;//出队 g1=Qu[front]; //printf("开始第%d个图:\n",front); //Print(g1); for(i=1;i<=4;i++)//分别从四个方向推导出新子节点 { Direct=i; if(Direct==g1->udirect)//跳过屏蔽方向 continue; g2=Move(g1, Direct, 1);//移动数码组 if(g2!=g1)//数码组是否可以移动 { //可以移动 Evaluate(g2, End);//评价新的节点 //printf("开始产生的第%d个图:\n",i); //Print(g2); if(g2->evalue<=g1->evalue+1) { //是优越节点 g2->parent=g1; //移动空格 switch(Direct)//设置屏蔽方向,防止往回推 { case 1://上 g2->udirect=2; break; case 2://下 g2->udirect=1; break; case 3://左 g2->udirect=4; break; case 4://右 g2->udirect=3; break; } rear++; Qu[rear]=g2;//存储节点到待处理队列 if(g2->evalue==0)//为0则搜索完成 { g=g2; //i=5; break; } } else { free(g2);//抛弃劣质节点 g2=NULL; } } } if(g!=NULL)//为0则搜索完成 { if(g->evalue==0) { break; } } Step++;//统计深度 if(Step>Max_Step) { break; } } return g; } /////////初始化一个八数码结构体 Graph *CR_BeginGraph(Graph *The_graph) { srand((unsigned)time(0)); int M=10;//随机移动步数 int Direct; int i,x,y; Graph *New_graph; New_graph=(Graph *)malloc(sizeof(Graph)); for(x=0;x<N;x++) { for(y=0;y<N;y++) { New_graph->form[x][y]=The_graph->form[x][y]; //init as end graph } } for(i=0;i<M;i++) { Direct=rand()%4+1;//产生1-4随机数 //printf("Direct:%d\n",Direct); New_graph=Move(New_graph, Direct, 0); //Print(New_graph); } New_graph->evalue=0; New_graph->udirect=0; New_graph->parent=NULL; return New_graph; } int main (int argc, const char * argv[]) { // insert code here... /* Graph Begin_graph={ {{2,8,3},{1,6,4},{0,7,5}},0,0,NULL }; Graph Begin_graph={ {{2,8,3},{1,0,4},{7,6,5}},0,0,NULL }; Graph Begin_graph={ {{2,0,1},{4,6,5},{3,7,8}},0,0,NULL }; */ //目标数码组 Graph End_graph={ {{1,2,3},{8,0,4},{7,6,5}},0,0,NULL }; //初始数码组 Graph *Begin_graph; Begin_graph=CR_BeginGraph(&End_graph);//随机产生初始数码组 Evaluate(Begin_graph, &End_graph);//对初始的数码组评价 printf("初始数码组:\n"); Print(Begin_graph); printf("目标数码组:\n"); Print(&End_graph); Graph *G,*P; int top=-1; //图搜索 G=Search(Begin_graph, &End_graph); //打印 if(G) { //把路径倒序 P=G; //压栈 while(P!=NULL) { top++; St[top]=P; P=P->parent; } printf("<<<<<<<<<<<<<<<搜索结果>>>>>>>>>>>>>>>>\n"); //弹栈打印 while(top>-1) { P=St[top]; top--; Print(P); } printf("<<<<<<<<<<<<<<<<<完成>>>>>>>>>>>>>>>>>>\n"); } else { printf("搜索不到结果,深度为%d\n",Max_Step); //设计搜索深度范围主要是防止队列内存越界 } return 0; }
0x02 启发式搜索-A*算法
这个方法利用评估函数判断最优解,评估函数f = g + h
g是当前节点距离初始节点的值,h是不在正确位置的点数量(同0x01评估值),其实h只要保证递减收敛即可,这里评估值就是f。
这里我在原代码基础上增加了判断是否有解的代码,判断代码也是用别人的,但是感觉有bug,有解也有时输出无解,利用的是奇偶性,逆序数,奇数无解,偶数有解,不大懂……。
这里需要用到open,close表,open存放待扩展节点,close存已扩展节点。
步骤如下:
1.将初始节点放入open表。
2.在open表中选出评估值f最小的节点,放入close表,同时删除open表中的该节点。
3.不断移动空格的位置扩展新节点,若不和close表的节点重复,则加入到open表中。
4.直到找到h为0的节点。
代码如下:
//代码来源于blog.sina.com.cn/s/blog_5be64cb70100lyx5.html
增加了少许注释。
判断代码Check()函数来源于blog.csdn.net/qq_32400847/article/details/51816685
//启发规则:评价函数是f(n)=d(n)+w(n) //其中d(n)是结点深度,w(n)是将牌不在位数 //实现自输入初态:从左至右,从上到下输入 //目标棋局定为:1 2 3 // 8 4 // 7 6 5 //本程序中以0作为空格结点的值 #include<iostream> #include<vector> using namespace std; struct point { int a[3][3]; //graph int w;//the num about not in right site int d;//depth int f;//评价函数 }; vector<point*> close;//已扩展节点 vector<point*> open;//待扩展节点 int aim[3][3]={1,2,3,8,0,4,7,6,5};//目标棋局 int check(point *cs) //check if it has solution { int i,j,k; int s[20]; int cnt=0; for(i=0;i<3;i++) { for(j=0;j<3;j++) { s[3*i+j]=cs->a[i][j]; if(s[3*i+j]=='x') continue; for(k=3*i+j-1;k>=0;k--) { if(s[k]=='x') continue; if(s[k]>s[3*i+j]) cnt++; } } } if(cnt%2) return 0; return 1; } int Cout(point *&s) //count the num about not in right site { s->w=0; for(int i=0;i<3;i++) { for(int j=0;j<3;j++) { if(s->a[i][j]!=aim[i][j]) s->w++; } } return s->w; } bool init(point * &s)//初始化接点 { s=(point *)malloc(sizeof(point)); if(!s) return false; s->d=1; s->w=0; cout<<"请输入初始化接点:"; for(int i=0;i<3;i++) { for(int j=0;j<3;j++) { int a; cin>>a; s->a[i][j]=a; } } Cout(s); s->f=s->d+s->w; //f return true; } int sort()//将open表中接点按评价函数排序,返回评价函数值最小的节点在队列中的位置 { if(open.size()!=0) { int min=0; int temp=open.at(0)->f; for(int i=0;i<open.size();i++) { if(open[i]->f<temp) { temp=open[i]->f; min=i; } } return min; } return -1; } bool compare(point *s)//比较可扩展接点与colse表中接点是否重复,true:不重复 false:重复 { vector<point*>::iterator it; for(it=close.begin();it!=close.end();it++) { int n=0; for(int i=0;i<3;i++) { for(int j=0;j<3;j++) { if(s->a[i][j]!=(*it)->a[i][j]) { n++; break; } } } if(n==0) return false; } return true; } void expand(point *s)//扩展接点 { int a,b; for(int i=0;i<3;i++) //get 0 site { for(int j=0;j<3;j++) { if(s->a[i][j]==0) { a=i;b=j; break; } } }//确定空格位置 for(int i=0;i<4;i++)//四个方向探测--0:上 1:下 2:左 3:右 { int n=0; point *p=(point *)malloc (sizeof(point)); for(int c=0;c<3;c++) { for(int z=0;z<3;z++) p->a[c][z]=s->a[c][z]; } if(i==0&&b-1>=0)//左可行,交换 { int temp=p->a[a][b-1]; p->a[a][b-1]=p->a[a][b]; p->a[a][b]=temp; n++; } else if(i==1&&a+1<=3)//下可行,交换 { int temp=p->a[a+1][b]; p->a[a+1][b]=p->a[a][b]; p->a[a][b]=temp; n++; } else if(i==2&&a-1>=0)//上可行,交换 { int temp=p->a[a-1][b]; p->a[a-1][b]=p->a[a][b]; p->a[a][b]=temp; n++; } else if(i==3&&b+1<=3)//右可行,交换 { int temp=p->a[a][b+1]; p->a[a][b+1]=p->a[a][b]; p->a[a][b]=temp; n++; } if(n==0)//此方向不可行,试探下一个方向 continue; p->d=s->d+1; p->w=0; Cout(p); p->f=p->d+p->w; if(compare(p))//与已扩展节点相比无重复则加入open表 open.insert(open.begin(),p); } } void print()//输出搜索路径 { vector<point*>::iterator it; for(it=close.begin();it!=close.end();it++) { for(int i=0;i<3;i++) { cout<<endl; cout<<(*it)->a[i][0]<<" "<<(*it)->a[i][1]<<" "<<(*it)->a[i][2]<<endl; } if(it!=close.end()-1) { cout<<" |"<<endl; cout<<" |"<<endl; cout<<"<>"<<endl; } } } void Num() { point *s; init(s); if(!check(s)){ printf("no solution!\n"); return; } open.push_back(s); while(open.size()!=0) { int min=sort(); point *ex=open.at(min); if(min!=-1) { if(close.size()!=0)//若open表中评价函数最小值节点的层数小于close表中层数,说明该路径非最优, { //退回,删除close表中与最小值节点同层和下层节点 vector<point*>::iterator it=close.end()-1; while(open.at(min)->d<=(*it)->d) { close.pop_back(); } } close.push_back(open.at(min));//最小值节点入close open.erase(open.begin()+min);//同时删除open表中相应节点 if(Cout(ex)==0)//若不在位节点数为0,则打印输出最优路径 { print(); return; } expand(ex);//若非目标棋局,则扩展节点 } } } int main() { Num(); return 0; }
0x03 结语
晕乎乎,有空再仔细研究一下。
0x04 参考资料
blog.csdn.net/qq_32400847/article/details/51816685
blog.csdn.net/wangqiuyun/article/details/7840771
blog.csdn.net/zuzubo/article/details/1540280
blog.sina.com.cn/s/blog_4e0c21cc0102wvd3.html
blog.sina.com.cn/s/blog_5be64cb70100lyx5.html
aaa 2017/11/26 01:46