鱼C论坛

 找回密码
 立即注册
查看: 6930|回复: 43

[技术交流] python小练习(064):探索法(广度优先搜索)不到40行代码求解拼图游戏的最优路径

[复制链接]
发表于 2017-2-4 10:02:30 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
本帖最后由 jerryxjr1220 于 2017-2-7 11:23 编辑

在python小练习(012)中介绍了探索解法求解不确定的路径问题,在python小练习(060)中又介绍了拼图小游戏,今天我们把这2个内容结合起来,利用探索法求解拼图游戏的最优路径。

这题原本是一道面试笔试题。

原文题目:
There're 7 red tiles, 8 blue titles and one white title in a 4 x 4 plane. We could only move the white tile. When moving it, the white tile swaps the position with the adjacent tile. L, R, U, D are corresponding to four directions which the tile could be moved to (Left, Right, Up, Down) For example, starting from configuration (S), by the move sequence RDRDLwe reach the configuration (E). Now, starting from configuration (S), find the shortest way to reach configuration (T).
SZDcMp3.jpg
简单翻译一下:
在如图4x4的16宫格内,有7个红块和8个蓝块以及1个白块,这个白块可以上下左右移动(对应关系为:L左、R右、U上、D下)与其他颜色的方块交换位置。如果起始状态为S,通过RDRDL后,我们可以得到E的状态。
那么如何从起始状态S通过最短路径得到T的最终状态。请给出最短交换路径。

先给个参考答案:
R R D L L U R R R D L L U R D D L D R U R D L U L L D R U U L U
[Finished in 1.0s]

不到40行的源代码:
游客,如果您要查看本帖隐藏内容请回复

本帖被以下淘专辑推荐:

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2017-2-4 10:36:05 | 显示全部楼层
探索法是我取的名字,科学一点的叫法应该称作“广度搜索”,与“深度搜索”正好相反,是解决不确定性路径问题的很好的解法。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-2-4 14:20:28 | 显示全部楼层
我只是来赚鱼币的~
表示没有看懂~
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-2-4 20:07:24 | 显示全部楼层
听说回复有鱼币~
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-2-5 12:48:02 | 显示全部楼层
sda
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2017-2-5 17:11:41 | 显示全部楼层
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2017-2-7 11:05:00 | 显示全部楼层
好高深,好牛逼~~~
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-2-19 00:54:59 | 显示全部楼层
学院报到要用Python编个小游戏 简直了  有点小麻烦 还没有找到源码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-2-19 14:13:25 | 显示全部楼层
不错,学习了,谢谢~!~!!~
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-3-27 09:05:28 | 显示全部楼层
好棒呀!
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-3-27 11:01:05 | 显示全部楼层
感谢分享
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-4-18 19:27:02 | 显示全部楼层
感觉思路和那个象棋马走的路线有点像
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-5-3 00:23:55 | 显示全部楼层
看答案
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-5-8 23:24:44 | 显示全部楼层
谢谢分享~~!!!!
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-5-9 23:35:01 | 显示全部楼层
学习一下算法
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-5-15 10:25:13 | 显示全部楼层
感谢!!!!!!!!!!!
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2017-6-13 16:19:48 | 显示全部楼层
学习下
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-6-15 20:23:48 | 显示全部楼层
求教~这种问题一般是如何避免queue中的状态回到之前遍历过的状态?
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2017-6-15 20:32:02 | 显示全部楼层
WelanceLee 发表于 2017-6-15 20:23
求教~这种问题一般是如何避免queue中的状态回到之前遍历过的状态?

所以会有visited来记录遍历过的状态
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-6-16 11:24:08 | 显示全部楼层
  1. import copy
  2. ##start = [[0,1,2,2], [1,1,2,2], [1,1,2,2], [1,1,2,2]]
  3. ##end = [[0,2,1,2], [2,1,2,1], [1,2,1,2], [2,1,2,1]]
  4. start = ['0122112211221122', 0, 0]
  5. end = ['0212212112122121', 0, 0]
  6. moves = [[1,0], [-1,0], [0,1], [0, -1]]
  7. action = {}
  8. queue = [start]
  9. index = 0
  10. flag = True
  11. while flag:
  12.     for each in moves:
  13.         q = queue[index]
  14.         qx = copy.deepcopy(q)
  15.         if qx == end:
  16.             flag = False
  17.             break
  18.         x = qx[1] + each[0]
  19.         y = qx[2] + each[1]
  20.         if -1 < x < 4 and -1 < y < 4:
  21.             qy = list(qx[0])
  22.             l = 4*x + y
  23.             m = 4*qx[1] + qx[2]
  24.             tmp = qy[l]
  25.             qy[l] = qy[m]
  26.             qy[m] = tmp
  27.             qx[1] = x
  28.             qx[2] = y
  29.             qx[0] = ''.join(qy)
  30.             if qx not in queue:
  31.                 queue.append(qx)
  32. ##                action[(qx[1], qx[2])] = (q[1], q[2])
  33.                 action[str(qx)] = q
  34.     index += 1

  35. while qx != start:
  36.     qx = action[str(qx)]
  37.     print(qx)
复制代码

修修补补总算把答案整出来了,但是真的丑~
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-28 18:54

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表