八数码问题解决方法,怎么解决八数码问题

图标

王豆瓜

豆瓜网

豆瓜网专栏

首发
王豆瓜 图标 2020-01-29 20:58:06

0.问题引入#

 在3×3的棋盘上,摆有八个棋子,每个棋子上标有1至8的某一数字。棋盘中留有一个空格,空格用0来表示。空格周围的棋子可以移到空格中。要求解的问题是:给出一种初始布局(初始状态)和目标布局(为了使题目简单,设目标状态为123804765)。

找到一种最少步骤的移动方法,实现从初始布局到目标布局的转变。

八数码问题解决方法,怎么解决八数码问题

1. 广度优先遍历#

  • 用字符串表示状态。

  • 使用 map<string,bool> 进行判定当前状态是否进行过搜索。

  • 记录进行到第几层BFS,需要一个 9! 的数组(0~8全排列的个数)。

这题是说明了不会有无解的情况,真正情况下是可能会有无解的情况的,出现在 队列为空还未走到目标状态。

 

View Code

 

  八数码问题解决方法,怎么解决八数码问题

2.DBFS 双向广度优先遍历#

双向广度优先,两个队列,一个从起点开始扩展状态,另一个从终点开始扩展状态;如果两者相遇,则表示找到了一条通路,而且是最短的通路。

双向,必须要记录下来每个状态处于第几层,因为相遇的时候,必须知道这个相遇状态是处于BFS的哪一层。

View Code

八数码问题解决方法,怎么解决八数码问题

 3.A*(启发式搜索)#

启发式搜索_百度百科#

启发策略:f(n) = g(n) + h(n),其中 g(n) 为层数,h(n)为当前状态“不在位”的数量。建立优先级队列,每次选取 f(n) 最小的状态。

View Code

但是在这个题目,两个网站上跑得都更慢了,应该数据比较特殊。

八数码问题解决方法,怎么解决八数码问题

 附测试数据:


/*273645801
out:15

053276184
out:21

836752104
out:14*/


本文由豆瓜网专栏作家 王豆瓜 投稿发布,并经过豆瓜网编辑审核。

转载此文章须经作者同意,并附上出处(豆瓜网)及本页链接。

若稿件文字、图片、视频等内容侵犯了您的权益,请联系本站进行 投诉处理

相关搜索

八数码问题
图标 图标

王豆瓜

豆瓜网

豆瓜网专栏

全部评论

王豆瓜

豆瓜网

豆瓜网专栏

  • 八数码问题解决方法,怎么解决八数码问题
  • ldap认证协议说明
  • mysql mediumblob类型详解
  • 实现遍历arraylist的几种方式
  • js递归函数详解
  • 我来说两句