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

jerryxjr1220

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

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

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

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

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

maze = [
 #start (0,0)
[1 ,0, 1, 0, 0, 0],
[1, 1, 1, 1, 0, 1],
[0, 0, 1, 0, 1, 0],
[1, 0, 1, 0, 1, 1],#End (3,5)
[1, 1, 1, 1, 1, 1],
[0, 1, 0, 1, 0, 0],
[0, 1, 0, 1, 1, 1]]

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

Done!
The right way marked "8"!
[8, 0, 1, 0, 0, 0]
[8, 8, 8, 1, 0, 1]
[0, 0, 8, 0, 1, 0]
[1, 0, 8, 0, 1, 8]
[1, 1, 8, 8, 8, 8]
[0, 1, 0, 1, 0, 0]
[0, 1, 0, 1, 1, 1]
[Finished in 0.2s]

源代码：

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

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

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

jerryxjr1220

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

                               
登录/注册后可看大图

PatrickTse

可以可以，楼主好厉害

念桥红药

学习学习，谢谢！

panda小正太

学习下！！！嘻嘻~

Jonin616

#回溯加递归
maze = [
[1 ,0, 1, 0, 0, 0],
[1, 1, 1, 1, 0, 1],
[0, 0, 1, 0, 1, 0],
[1, 0, 1, 0, 1, 1],
[1, 1, 1, 1, 1, 1],
[0, 1, 0, 1, 0, 0],
[0, 1, 0, 1, 1, 1]]

move = [(1,0),(-1,0),(0,1),(0,-1)]
way = {(0,0):(-1,-1)}
cpos = [0,0]
final = [3,5]
    
def Stra(cpos):
    for each in move:
        x = cpos[0] + each[0]
        y = cpos[1] + each[1]
        if 0 <= x <= 6 and 0 <= y <= 5 and (x,y) not in way:
            if maze[x][y] == 1:
                if final == [x,y]:
                    return 1
                else:
                    maze[x][y] = 8
                    way[(x,y)] = (cpos[0],cpos[1])
            else:
                continue
        else:
            continue
        if Stra([x,y]) == 1:
            return 1
        else:
            continue
    maze[cpos[0]][cpos[1]] = 1
    way.pop((cpos[0],cpos[1]))
    return 0

def main():
    if Stra(cpos) == 1:
        maze[3][5] = 8
        for each in maze:
            print(each)
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

# start = (0, 0)
# end = (3, 5)

maze = [
[1 ,0, 1, 0, 0, 0],
[1, 1, 1, 1, 0, 1],
[0, 0, 1, 0, 1, 0],
[1, 0, 1, 0, 1, 1],
[1, 1, 1, 1, 1, 1],
[0, 1, 0, 1, 0, 0],
[0, 1, 0, 1, 1, 1]]

c = [[0]*6 for i in range(7)]
moves = [(1, 0), (0, 1), (-1, 0), (0, -1)]
s = [(0, 0)]
c[0][0] = 1
a = {}
while True:
    location = s.pop(0)
    if location == (3, 5):
        break
    for m in moves:
        x = location[0] + m[0]
        y = location[1] + m[1]
        if -1< x < 7 and -1 < y < 6 and maze[x][y] == 1 and c[x][y] == 0:
            c[x][y] = 1
            s.append((x, y))
            a[(x, y)] = m

location = (3, 5)
l = [location]
while location != (0, 0):
    x = location[0] - a[location][0]
    y = location[1] - a[location][1]
    location = (x, y)
    l.insert(0, location)

print(l)