python小练习（055）：回溯法（深度优先搜索）与探索法（广度优先搜索）求解迷宫问题
本帖最后由 jerryxjr1220 于 2017-2-7 11:26 编辑之前已经有好多帖子讨论过“迷宫问题”了，解法也各有千秋。
今天闲来无事又琢磨了一种“字典+递归的回溯算法”（深度优先搜索算法），供大家参考。
解题思路：
利用字典把所有可能的路径列出来，利用递归算法逐层从字典中把路径找出来。
其他的看注解吧，写得很详细了。
举例：
迷宫为：（0为墙，1为路，起始（0，0），终点（3，5））
maze = [
#start (0,0)
,
,
,
,#End (3,5)
,
,
]
程序输出：（正确路径用“8”标记出来了）
Done!
The right way marked "8"!
源代码：
**** Hidden Message *****
另外一种探索解法（广度优先搜索算法）：
**** Hidden Message ***** 只要有合适的解法，像这种复杂的迷宫问题，对计算机来说，也是小case，要人眼来看几乎是不可能完成的任务。
http://xxx.fishc.com/forum/201611/09/110937d8g80xxxjkyggljc.png 可以可以，楼主好厉害 学习学习，谢谢！ 学习下！！！嘻嘻~ #回溯加递归
maze = [
,
,
,
,
,
,
]
move = [(1,0),(-1,0),(0,1),(0,-1)]
way = {(0,0):(-1,-1)}
cpos =
final =
def Stra(cpos):
for each in move:
x = cpos + each
y = cpos + each
if 0 <= x <= 6 and 0 <= y <= 5 and (x,y) not in way:
if maze == 1:
if final == :
return 1
else:
maze = 8
way[(x,y)] = (cpos,cpos)
else:
continue
else:
continue
if Stra() == 1:
return 1
else:
continue
maze]] = 1
way.pop((cpos,cpos))
return 0
def main():
if Stra(cpos) == 1:
maze = 8
for each in maze:
print(each)
main() Jonin616 发表于 2017-3-2 17:35
这题会解了那就来做做“欧拉计划的81~83题”吧，同样的最优路径搜索问题，应该也可以解了。
81、82题可以用动态规划，83题DFS或者BFS{:5_109:}
http://bbs.fishc.com/thread-74713-1-3.html jerryxjr1220 发表于 2017-3-2 20:11
这题会解了那就来做做“欧拉计划的81~83题”吧，同样的最优路径搜索问题，应该也可以解了。
81、82题可 ...
81跟82已经做出来了 还差83 jerryxjr1220 发表于 2017-3-2 20:11
这题会解了那就来做做“欧拉计划的81~83题”吧，同样的最优路径搜索问题，应该也可以解了。
81、82题可 ...
我觉得欧拉计划里面倒是很多有关数论的题目真的挺头大的 数学知识差不多都忘关了 学习 Jonin616 发表于 2017-3-5 17:58
我觉得欧拉计划里面倒是很多有关数论的题目真的挺头大的 数学知识差不多都忘关了
{:5_106:}
欧拉计划本来就是偏数学理论和算法的题目，其实和python没多大关系，很多解题者用的也根本不是python语言，只是python比较容易使用，所以比较受欢迎而已。
81和82是动态规划算法，用时都很短（<0.5 sec），83题才是搜索算法，不过如果你理解了上述的算法也挺简单的。 jerryxjr1220 发表于 2017-3-5 20:41
欧拉计划本来就是偏数学理论和算法的题目，其实和python没多大关系，很多解题者用的也根本不 ...
最近除了在学数据结构与算法之外还在考虑应该学python的哪个方向 因为python的生态圈太庞大了 Jonin616 发表于 2017-3-8 20:58
最近除了在学数据结构与算法之外还在考虑应该学python的哪个方向 因为python的生态圈太庞大了
看你的兴趣是什么了，python无所不能{:10_256:} jerryxjr1220 发表于 2017-3-8 21:00
看你的兴趣是什么了，python无所不能
主要是不懂要哪个方向 之前是学了linux 和MySQL 因为python在运维方面用得挺多才来学Python的，现在想往web开发方向学习 你知道需要掌握哪些东西么 Jonin616 发表于 2017-3-8 22:34
主要是不懂要哪个方向 之前是学了linux 和MySQL 因为python在运维方面用得挺多才来学Python的，现在想往w ...
web开发的话，Django、Flask、数据库、selenium这些都需要的，其实做web最关键还是要把java学好{:5_109:} jerryxjr1220 发表于 2017-3-9 09:14
web开发的话，Django、Flask、数据库、selenium这些都需要的，其实做web最关键还是要把java学好
web开发一定要触及到Java么？ s话实话对java实在不感兴趣 Jonin616 发表于 2017-3-9 10:26
web开发一定要触及到Java么？ s话实话对java实在不感兴趣
但是做一个稍微能看的web，你肯定绕不开javascript的呀，除非你自己搞个其他脚本语言，还要能被广大互联网用户普遍接受的，因为客户端的解析器（浏览器）不在你这边，这是不受你控制的{:5_109:} 不错学习了 学习一下～ 本帖最后由 WelanceLee 于 2017-6-13 14:54 编辑
# start = (0, 0)
# end = (3, 5)
maze = [
,
,
,
,
,
,
]
c = [*6 for i in range(7)]
moves = [(1, 0), (0, 1), (-1, 0), (0, -1)]
s = [(0, 0)]
c = 1
a = {}
while True:
location = s.pop(0)
if location == (3, 5):
break
for m in moves:
x = location + m
y = location + m
if -1< x < 7 and -1 < y < 6 and maze == 1 and c == 0:
c = 1
s.append((x, y))
a[(x, y)] = m
location = (3, 5)
l =
while location != (0, 0):
x = location - a
y = location - a
location = (x, y)
l.insert(0, location)
print(l)