python小练习（055）：回溯法（深度优先搜索）与探索法（广度优先搜索）求解迷宫问题

jerryxjr1220

之前已经有好多帖子讨论过“迷宫问题”了，解法也各有千秋。

今天闲来无事又琢磨了一种“字典+递归的回溯算法”（深度优先搜索算法），供大家参考。

解题思路：
利用字典把所有可能的路径列出来，利用递归算法逐层从字典中把路径找出来。

其他的看注解吧，写得很详细了。

举例：
迷宫为：（0为墙，1为路，起始（0，0），终点（3，5））

1. maze = [
   
2. #start (0,0)
   
3. [1 ,0, 1, 0, 0, 0],
   
4. [1, 1, 1, 1, 0, 1],
   
5. [0, 0, 1, 0, 1, 0],
   
6. [1, 0, 1, 0, 1, 1],#End (3,5)
   
7. [1, 1, 1, 1, 1, 1],
   
8. [0, 1, 0, 1, 0, 0],
   
9. [0, 1, 0, 1, 1, 1]]

复制代码

程序输出：（正确路径用“8”标记出来了）

1. Done!
   
2. The right way marked "8"!
   
3. [8, 0, 1, 0, 0, 0]
   
4. [8, 8, 8, 1, 0, 1]
   
5. [0, 0, 8, 0, 1, 0]
   
6. [1, 0, 8, 0, 1, 8]
   
7. [1, 1, 8, 8, 8, 8]
   
8. [0, 1, 0, 1, 0, 0]
   
9. [0, 1, 0, 1, 1, 1]
   
10. [Finished in 0.2s]

复制代码

源代码：

游客，如果您要查看本帖隐藏内容请回复

另外一种探索解法（广度优先搜索算法）：

游客，如果您要查看本帖隐藏内容请回复

jerryxjr1220

只要有合适的解法，像这种复杂的迷宫问题，对计算机来说，也是小case，要人眼来看几乎是不可能完成的任务。

                               
登录/注册后可看大图

PatrickTse

可以可以，楼主好厉害

念桥红药

学习学习，谢谢！

panda小正太

学习下！！！嘻嘻~

Jonin616

1. #回溯加递归
   
2. maze = [
   
3. [1 ,0, 1, 0, 0, 0],
   
4. [1, 1, 1, 1, 0, 1],
   
5. [0, 0, 1, 0, 1, 0],
   
6. [1, 0, 1, 0, 1, 1],
   
7. [1, 1, 1, 1, 1, 1],
   
8. [0, 1, 0, 1, 0, 0],
   
9. [0, 1, 0, 1, 1, 1]]
   
10. 
    
11. move = [(1,0),(-1,0),(0,1),(0,-1)]
    
12. way = {(0,0):(-1,-1)}
    
13. cpos = [0,0]
    
14. final = [3,5]
    
15.    
    
16. def Stra(cpos):
    
17.     for each in move:
    
18.         x = cpos[0] + each[0]
    
19.         y = cpos[1] + each[1]
    
20.         if 0 <= x <= 6 and 0 <= y <= 5 and (x,y) not in way:
    
21.             if maze[x][y] == 1:
    
22.                 if final == [x,y]:
    
23.                     return 1
    
24.                 else:
    
25.                     maze[x][y] = 8
    
26.                     way[(x,y)] = (cpos[0],cpos[1])
    
27.             else:
    
28.                 continue
    
29.         else:
    
30.             continue
    
31.         if Stra([x,y]) == 1:
    
32.             return 1
    
33.         else:
    
34.             continue
    
35.     maze[cpos[0]][cpos[1]] = 1
    
36.     way.pop((cpos[0],cpos[1]))
    
37.     return 0
    
38. 
    
39. def main():
    
40.     if Stra(cpos) == 1:
    
41.         maze[3][5] = 8
    
42.         for each in maze:
    
43.             print(each)
    
44. main()

复制代码

jerryxjr1220

Jonin616 发表于 2017-3-2 17:35

这题会解了那就来做做“欧拉计划的81~83题”吧，同样的最优路径搜索问题，应该也可以解了。
81、82题可以用动态规划，83题DFS或者BFS
http://bbs.fishc.com/thread-74713-1-3.html

Jonin616

jerryxjr1220 发表于 2017-3-2 20:11
这题会解了那就来做做“欧拉计划的81~83题”吧，同样的最优路径搜索问题，应该也可以解了。
81、82题可 ...

81跟82已经做出来了 还差83

Jonin616

jerryxjr1220 发表于 2017-3-2 20:11
这题会解了那就来做做“欧拉计划的81~83题”吧，同样的最优路径搜索问题，应该也可以解了。
81、82题可 ...

我觉得欧拉计划里面倒是很多有关数论的题目真的挺头大的 数学知识差不多都忘关了

过去吧

学习

jerryxjr1220

Jonin616 发表于 2017-3-5 17:58
我觉得欧拉计划里面倒是很多有关数论的题目真的挺头大的 数学知识差不多都忘关了

欧拉计划本来就是偏数学理论和算法的题目，其实和python没多大关系，很多解题者用的也根本不是python语言，只是python比较容易使用，所以比较受欢迎而已。
81和82是动态规划算法，用时都很短（<0.5 sec），83题才是搜索算法，不过如果你理解了上述的算法也挺简单的。

Jonin616

jerryxjr1220 发表于 2017-3-5 20:41
欧拉计划本来就是偏数学理论和算法的题目，其实和python没多大关系，很多解题者用的也根本不 ...

最近除了在学数据结构与算法之外还在考虑应该学python的哪个方向 因为python的生态圈太庞大了

jerryxjr1220

Jonin616 发表于 2017-3-8 20:58
最近除了在学数据结构与算法之外还在考虑应该学python的哪个方向 因为python的生态圈太庞大了

看你的兴趣是什么了，python无所不能

Jonin616

jerryxjr1220 发表于 2017-3-8 21:00
看你的兴趣是什么了，python无所不能

主要是不懂要哪个方向 之前是学了linux 和MySQL 因为python在运维方面用得挺多才来学Python的，现在想往web开发方向学习 你知道需要掌握哪些东西么

jerryxjr1220

Jonin616 发表于 2017-3-8 22:34
主要是不懂要哪个方向 之前是学了linux 和MySQL 因为python在运维方面用得挺多才来学Python的，现在想往w ...

web开发的话，Django、Flask、数据库、selenium这些都需要的，其实做web最关键还是要把java学好

Jonin616

jerryxjr1220 发表于 2017-3-9 09:14
web开发的话，Django、Flask、数据库、selenium这些都需要的，其实做web最关键还是要把java学好

web开发一定要触及到Java么？ s话实话对java实在不感兴趣

jerryxjr1220

Jonin616 发表于 2017-3-9 10:26
web开发一定要触及到Java么？ s话实话对java实在不感兴趣

但是做一个稍微能看的web，你肯定绕不开javascript的呀，除非你自己搞个其他脚本语言，还要能被广大互联网用户普遍接受的，因为客户端的解析器（浏览器）不在你这边，这是不受你控制的

qpwoeiruyt

不错  学习了

gweuro

学习一下～

WelanceLee

1. # start = (0, 0)
   
2. # end = (3, 5)
   
3. 
   
4. maze = [
   
5. [1 ,0, 1, 0, 0, 0],
   
6. [1, 1, 1, 1, 0, 1],
   
7. [0, 0, 1, 0, 1, 0],
   
8. [1, 0, 1, 0, 1, 1],
   
9. [1, 1, 1, 1, 1, 1],
   
10. [0, 1, 0, 1, 0, 0],
    
11. [0, 1, 0, 1, 1, 1]]
    
12. 
    
13. c = [[0]*6 for i in range(7)]
    
14. moves = [(1, 0), (0, 1), (-1, 0), (0, -1)]
    
15. s = [(0, 0)]
    
16. c[0][0] = 1
    
17. a = {}
    
18. while True:
    
19.     location = s.pop(0)
    
20.     if location == (3, 5):
    
21.         break
    
22.     for m in moves:
    
23.         x = location[0] + m[0]
    
24.         y = location[1] + m[1]
    
25.         if -1< x < 7 and -1 < y < 6 and maze[x][y] == 1 and c[x][y] == 0:
    
26.             c[x][y] = 1
    
27.             s.append((x, y))
    
28.             a[(x, y)] = m
    
29. 
    
30. location = (3, 5)
    
31. l = [location]
    
32. while location != (0, 0):
    
33.     x = location[0] - a[location][0]
    
34.     y = location[1] - a[location][1]
    
35.     location = (x, y)
    
36.     l.insert(0, location)
    
37. 
    
38. print(l)

复制代码