热门标签
热门文章
- 1建立一个简单的网页音乐盒模型效果#css#h5
- 2支持向量机SVM、优化问题、核函数
- 3从瀑布到敏捷——漫画解读软件开发模式变迁史_瀑布开发waterfall或者敏捷开发kanban, scrum是什么?
- 4多模态大模型_多模态大模型是什么
- 57_springboot_shiro_jwt_多端认证鉴权_自定义AuthenticationToken
- 62核4g服务器能支持多少人访问?阿里云2核4g服务器在线人数
- 7Pythorch 教程-Neural Network
- 8大型语言模型（LLMs）：从训练到推理的全面概述_理解大语言模型从训练到推理的全面概述
- 9知识图谱 （2）半结构化数据的知识抽取_抽取网站上的半结构化数据
- 10BERTScore——一种衡量两段文本相似度的方法
当前位置: article > 正文
人工智能----八数码问题（启发式搜索）_八数码问题启发式搜索
作者：Monodyee | 2024-04-06 08:27:30
赞
踩
八数码问题启发式搜索
启发式搜索
一、 实验目的
- 理解人工智能系统中搜索策略的含义。
- 熟悉盲目搜索和启发式搜索算法的实际应用。
- 结合八数码问题的建模、求解及编程语言的应用，掌握启发式搜索算法的应用。
二、 实验原理
启发式搜索(Heuristically Search)又称为有信息搜索(Informed Search)，
它是利用问题拥有的启发信息来引导搜索，达到减少搜索范围、降低问题复杂度的目的。启发式策略可以通过指导搜索向最有希望的方向前进，降低了复杂性。通过删除某些状态及其延伸，启发式算法可以消除组合爆炸，并得到令人能接受的解(通常并不一定是最优解)。
然而，启发式策略是极易出错的。在解决问题的过程中启发仅仅是下一步将
要采取措施的一个猜想，常常根据经验和直觉来判断。由于启发式搜索只有有限的信息(比如当前状态的描述)，要想预测进一步搜索过程中状态空间的具体行为则很难。这是启发式搜索固有的局限性，一般说来，启发信息越强，扩展的无用节点就越少。引入强的启发信息，有可能大大降低搜索工作量，但不能保证找到 最小耗散值的解路径(最佳路径)。
用于评价节点重要性的函数称为估价函数，其一般形式为
f(x) = g(x) + h(x)
式中：g(x)为从初始节点到节点x付出的实际代价；h(x)为从节点x到目标
节点的最优路径的估计代价。启发性信息主要体现在h(x)中，其形式要根据问 题的特性来确定。在启发式搜索中，估计函数的定义是十分重要的。如定义不当， 则上述搜索算法不一定能找到问题的解，即使找到解，也不一定是最优的。
三、 实验内容
八数码问题也称为九宫问题。在3×3的方格棋盘上，摆放着1到8这八个数码，
其中有1个方格是空的，初始状态如图1所示，要求对空格执行空格左移、右移、上移和下移这四个操作使得棋盘从初始状态到目标状态。
例如：
1 2 3
8 0 4
7 6 5
(a) 初始状态 (b) 目标状态
图1 八数码问题示意图
四、 实验过程
(1) 算法描述
对启发式搜索算法，又可根据搜索过程中选择扩展节点的范围，将其分为全局择优搜索算法和局部择优搜索算法。
在全局择优搜索中，每当需要扩展节点时，总是从 Open 表的所有节点中选择一个估价函数值最小的节点进行扩展。其搜索过程可能描述如下：
（ 1 ）把初始节点 S0 放入 Open 表中， f(S0)=g(S0)+h(S0) ；
（ 2 ）如果 Open 表为空，则问题无解，失败退出；
（ 3 ）把 Open 表的第一个节点取出放入 Closed 表，并记该节点为 n ；
（ 4 ）考察节点 n 是否为目标节点。若是，则找到了问题的解，成功退出；
（ 5 ）若节点 n 不可扩展，则转到第 (2) 步；
（ 6 ）扩展节点 n ，生成子节点 ni ( i =1,2, …… ) ，计算每一个子节点的估价值 f( ni ) ( i =1,2, …… ) ，并为每一个子节点设置指向父节点的指针，然后将这些子节点放入 Open 表中；
（ 7 ）根据各节点的估价函数值，对 Open 表中的全部节点按从小到大的顺序重新进行排序；
（ 8 ）转第 (2) 步。
(2) 算法分析
在A算法中，一个结点位置的好坏用估价函数来对它进行评估。A算法的估价函数可表示为：
f’(n) = g’(n) + h’(n)
这里，f’(n)是估价函数，g’(n)是起点到终点的最短路径值（也称为最小耗费或最小代价），h’(n)是n到目标的最短路经的启发值。由于这个f’(n)其实是无法预先知道的，所以实际上使用的是下面的估价函数：
f(n) = g(n) + h(n)
其中g(n)是从初始结点到节点n的实际代价，h(n)是从结点n到目标结点的最佳路径的估计代价。在这里主要是h(n)体现了搜索的启发信息，因为g(n)是已知的。用f(n)作为f’(n)的近似，也就是用g(n)代替g’(n)，h(n)代替h’(n)。这样必须满足两个条件：（1）g(n)>=g’(n)（大多数情况下都是满足的，可以不用考虑），且f必须保持单调递增。（2）h必须小于等于实际的从当前节点到达目标节点的最小耗费h(n)<=h’(n)。第二点特别的重要。可以证明应用这样的估价函数是可以找到最短路径的。
A算法的步骤
A算法基本上与广度优先算法相同，但是在扩展出一个结点后，要计算它的估价函数，并根据估价函数对待扩展的结点排序，从而保证每次扩展的结点都是估价函数最小的结点。
A算法的步骤如下：
1）建立一个队列，计算初始结点的估价函数f，并将初始结点入队，设置队列头和尾指针。
2）取出队列头（队列头指针所指）的结点，如果该结点是目标结点，则输出路径，程序结束。否则对结点进行扩展。
3）检查扩展出的新结点是否与队列中的结点重复，若与不能再扩展的结点重复（位于队列头指针之前），则将它抛弃；若新结点与待扩展的结点重复（位于队列头指针之后），则比较两个结点的估价函数中g的大小，保留较小g值的结点。跳至第五步。
4）如果扩展出的新结点与队列中的结点不重复，则按照它的估价函数f大小将它插入队列中的头结点后待扩展结点的适当位置，使它们按从小到大的顺序排列，最后更新队列尾指针。
5）如果队列头的结点还可以扩展，直接返回第二步。否则将队列头指针指向下一结点，再返回第二步。
八数码问题的A算法的估价函数
估价函数中，主要是计算h，对于不同的问题，h有不同的含义。那么在八数码问题中，h的含意是各什么？八数码问题的一个状态实际上是数字0~8的一个排列，用一个数组p[9]来存储它，数组中每个元素的下标，就是该数在排列中的位置。例如，在一个状态中，p[3]=7，则数字7的位置是3。如果目标状态数字3的位置是8，那么数字7对目标状态的偏移距离就是3，因为它要移动3步才可以回到目标状态的位置。
八数码问题中，每个数字可以有9个不同的位置，因此，在任意状态中的每个数字和目标状态中同一数字的相对距离就有9*9种，可以先将这些相对距离算出来，用一个矩阵存储，这样只要知道两个状态中同一个数字的位置，就可查出它们的相对距离，也就是该数字的偏移距离：
0 1 2 3 4 5 6 7 8
0 0 1 2 1 2 3 2 3 4
1 1 0 1 2 1 2 3 2 3
2 2 1 0 3 2 1 4 3 2
3 1 2 3 0 1 2 1 2 3
4 2 1 2 1 0 1 2 1 2
5 3 2 1 2 1 0 3 2 1
6 2 3 4 1 2 3 0 1 2
7 3 2 3 2 1 2 1 0 1
8 4 3 2 3 2 1 2 1 0
例如在一个状态中，数字8的位置是3，在另一状态中位置是7，那么从矩阵的3行7列可找到2，它就是8在两个状态中的偏移距离。
估价函数中的h就是全体数字偏移距离之和。
显然，要计算两个不同状态中同一数字的偏移距离，需要知道该数字在每个状态中的位置，这就要对数组p[9]进行扫描。由于状态发生变化，个数字的位置也要变化，所以每次计算h都沿线扫描数组，以确定每个数字在数组中的位置。为了简化计算，这里用一个数组存储状态中各个数字的位置，并让它在状态改变时随着变化，这样就不必在每次计算h时，再去扫描状态数组。
例如，某个状态中，数字5的位置是8，如果用数组r[9]存储位置，那么就有r[5]=8。
现在用数组r[9]存储当前状态的数字位置，而用s[9]存储目标状态的数字位置，那么当前状态数字i对目标状态的偏移距离就是矩阵中r[i]行s[i]列对应的值。
可解性分析：八数码问题的一个状态实际上是0~9的一个排列，对于任意给定的初始状态和目标，不一定有解，也就是说从初始状态不一定能到达目标状态。因为排列有奇排列和偶排列两类，从奇排列不能转化成偶排列或相反。
如果一个数字0~8的随机排列871526340，用F(X)表示数字X前面比它小的数的个数，全部数字的F(X)之和为Y=∑(F(X))，如果Y为奇数则称原数字的排列是奇排列，如果Y为偶数则称原数字的排列是偶排列。
例如871526340这个排列的
Y=0+0+0+1+1+3+2+3+0=10
10是偶数，所以他偶排列。871625340
Y=0+0+0+1+1+2+2+3+0=9
9是奇数，所以他奇排列。
因此，可以在运行程序前检查初始状态和目标状态的窘是否相同，相同则问题可解，应当能搜索到路径。否则无解。
(3) 程序流程图
(4) 搜索树与对应的OPEN表和CLOSED表
五、 实验结果
六、源代码
#include<iostream> #include<stdio.h> #include<cmath> using namespace std; int open_cnt=0; //记录open表中每一个扩展的节点 int open_node_cnt;//open表节点个数 struct Node{ int a[3][3]; int x,y; int f,g,h; //启发式搜索的函数 int flag; //上一次移动方向 Node *father; }start,end; struct Open_Close{ int f; Node *np; }open[10000],close[10000]; bool isable(){/*判断是否有解，逆序数之和奇偶性相同，有解 用F(X)表示数字X前面比它小的数的个数，全部数字的F(X)之和为Y=∑(F(X))，如果Y为奇数则称原数字的排列是奇排列，如果Y为偶数则称原数字的排列是偶排列。 */ int s[9],e[9]; int tf=0,ef=0; int k=0; for(int i=0;i<3;i++){ for(int j=0;j<3;j++){ s[k]=start.a[i][j]; //将初始状态存入s[]数组中 e[k]=end.a[i][j]; //将目标状态存入e[]数组中 k++; } } for(int i=0;i<9;i++){ for(int j=0;j<i;j++){ if(s[i]>s[j]&&s[j]!=0) tf+=1; //记录对应位置上前面比他小 的数的个数 if(e[i]>e[j]&&e[j]!=0) ef+=1; } } if((tf%2==1&&ef%2==1)||(tf%2==0&&ef%2==0)) return true; //奇偶相同，则有解 else return false; } int a_start_h(Node *node){ //求 h（） 计算每个数字当前状态与最终状态的曼哈顿距离 之和作为代价 int old_x,old_y,end_x,end_y; int h=0; for(int k=1;k<9;k++){ for(int i=0;i<3;i++){ for(int j=0;j<3;j++){ if(node->a[i][j]==k){ //找到每个数在对数组中的对应位置 old_x=i; old_y=j; } if(end.a[i][j]==k){ //目标状态的数在数组中的对应位置 end_x=i; end_y=j; } } } h+=abs(old_x-end_x)+abs(old_y-end_y); //计算和目标状态偏移量之和 } return h; } void input(){ printf("请输入初始状态:\n"); //输入 for(int i=0;i<3;i++){ for(int j=0;j<3;j++){ cin>>start.a[i][j]; if(start.a[i][j]==0){ //记录0位置，即空位置 start.x=i; start.y=j; } } } printf("请输入目标状态:\n"); for(int i=0;i<3;i++){ for(int j=0;j<3;j++){ cin>>end.a[i][j]; if(end.a[i][j]==0){ //记录0位置，即空位置 end.x=i; end.y=j; } } } start.g=0; //函数g start.h=a_start_h(&start); //函数h start.f=start.g+start.h; //函数f } int show(Node *node){ //显示 Node *p = node; if(p==&start) return 1; else show(p->father); for(int i=0;i<3;i++){ for(int j=0;j<3;j++){ cout<<p->a[i][j]<<" "; } printf("\n"); } cout<<"====================================\n"; } bool isend(Node *node){ //判断是否为目标节点 for(int i=0;i<3;i++){ for(int j=0;j<3;j++){ if(node->a[i][j]!=end.a[i][j]) //对应位置元素不等于目标状态的数，返回false return false; } } return true; } void sort(Open_Close *open){ //open表排序 int min=99999,min_flag=0; Open_Close temp; for(int i=0;i<=open_cnt;i++){ if(min>open[i].f&&open[i].f>0){ //找出最小节点 min=open[i].f; min_flag=i; } } temp=open[min_flag]; //调整亲子关系 open[min_flag]=open[0]; open[0]=temp; } void move(int flag,Node *node){ //向四个方向扩展 int temp; if(flag==1&&node->x>0){ //靠右边，向左移动 Node *n = new Node(); for(int i=0;i<3;i++){ for(int j=0;j<3;j++){ n->a[i][j]=node->a[i][j]; //n接收node矩阵 } } n->a[node->x][node->y]=node->a[node->x-1][node->y]; //左移 n->a[node->x-1][node->y]=0; //对应位置置0，即置空 n->x=node->x-1; //改变x的值 n->y=node->y; //改变y的值 n->flag=3; //左边 n->father=node; n->g=node->g+1; // 求 g（） n->h=a_start_h(n); n->f=n->g+n->h; open_cnt++; //扩展的节点 open_node_cnt++; open[open_cnt].np=n; //添加到open表 open[open_cnt].f=n->f; // 求 f（） }else if(flag==2&&node->y<2){ //靠下，上移 Node *n = new Node(); for(int i=0;i<3;i++){ for(int j=0;j<3;j++){ n->a[i][j]=node->a[i][j]; } } n->a[node->x][node->y]=node->a[node->x][node->y+1]; //下移 n->a[node->x][node->y+1]=0; n->x=node->x; n->y=node->y+1; n->flag=4; n->father=node; n->g=node->g+1; // 求 g（） n->h=a_start_h(n); n->f=n->g+n->h; open_cnt++; open_node_cnt++; open[open_cnt].np=n; //添加到open表 open[open_cnt].f=n->f; // 求 f（） }else if(flag==3&&node->x<2){ //靠左边，向右移 Node *n = new Node(); for(int i=0;i<3;i++){ for(int j=0;j<3;j++){ n->a[i][j]=node->a[i][j]; } } n->a[node->x][node->y]=node->a[node->x+1][node->y]; //右移 n->a[node->x+1][node->y]=0; n->x=node->x+1; n->y=node->y; n->flag=1; n->father=node; n->g=node->g+1; // 求 g（） n->h=a_start_h(n); n->f=n->g+n->h; open_cnt++; open_node_cnt++; open[open_cnt].np=n; //添加到open表 open[open_cnt].f=n->f; // 求 f（） }else if(flag==4&&node->y>0){ //靠上，下移 Node *n = new Node(); for(int i=0;i<3;i++){ for(int j=0;j<3;j++){ n->a[i][j]=node->a[i][j]; } } n->a[node->x][node->y]=node->a[node->x][node->y-1]; n->a[node->x][node->y-1]=0; n->x=node->x; n->y=node->y-1; n->flag=2; n->father=node; n->g=node->g+1; // 求 g（） n->h=a_start_h(n); n->f=n->g+n->h; open_cnt++; open_node_cnt++; open[open_cnt].np=n; //添加到open表 open[open_cnt].f=n->f; // 求 f（） } } void expand(Node *node){ //节点扩展 for(int i=1;i<5;i++){ //向4个方向扩展 if(i!=node->flag) move(i,node); } } int main(){ input(); open[0].np = &start; //start放入open表 open_node_cnt=1; //从开始状态 if(isable()){ while(true){ //open表不为空 if(isend(open[0].np)){ printf("\n路径：\n"); show(open[0].np); break; } expand(open[0].np);//扩展最优节点的子节点 open[0].np=NULL; open[0].f=-1; open_node_cnt--; //open表数量-1 sort(open); //open表排序 } }else cout<<"无解"; system("pause"); }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
- 125
- 126
- 127
- 128
- 129
- 130
- 131
- 132
- 133
- 134
- 135
- 136
- 137
- 138
- 139
- 140
- 141
- 142
- 143
- 144
- 145
- 146
- 147
- 148
- 149
- 150
- 151
- 152
- 153
- 154
- 155
- 156
- 157
- 158
- 159
- 160
- 161
- 162
- 163
- 164
- 165
- 166
- 167
- 168
- 169
- 170
- 171
- 172
- 173
- 174
- 175
- 176
- 177
- 178
- 179
- 180
- 181
- 182
- 183
- 184
- 185
- 186
- 187
- 188
- 189
- 190
- 191
- 192
- 193
- 194
- 195
- 196
- 197
- 198
- 199
- 200
- 201
- 202
- 203
- 204
- 205
- 206
- 207
- 208
- 209
- 210
- 211
- 212
- 213
- 214
- 215
- 216
- 217
- 218
- 219
- 220
- 221
- 222
- 223
- 224
- 225
- 226
- 227
- 228
- 229
- 230
- 231
- 232
- 233
- 234
- 235
- 236
- 237
- 238
- 239
- 240
- 241
- 242
- 243
- 244
- 245
- 246
- 247
- 248
- 249
- 250
- 251
- 252
- 253
- 254
- 255
- 256
- 257
- 258
- 259
- 260
- 261
- 262
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Monodyee/article/detail/370824
推荐阅读
相关标签
