Tag:A*算法

Tag (A*算法)'s result:

启发式搜索解决八数码问题

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; }……