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

jerryxjr1220

WelanceLee 发表于 2017-6-13 14:53

来一道扩展题，同样的思路可解

我们把场地分为一个个的格子，给每个格子标定一个整数，代表这个格子所代表的地面的海拔高度。
比赛的参赛者可以从任意一个格子开始，但只能向相邻的四个格子移动，并且目地格子的高度必须
小于现在所在格子的高度。我们假设从一个格子滑行到另一个格子所用的时间为1个单位时间。
现在告诉你滑雪场的大小为n*m, 并给你一个n行m列的整数二维列表H，表示每个格子的海拔高度。
请你计算出在这个场地上最长能滑行多少时间。
如：
n = 4
m = 4
H= [
    [1, 2, 3, 4],
    [5,6,7,8],
    [9,10,11,12],
    [13,14,15,16]
    ]
则输出 6.

WelanceLee

jerryxjr1220 发表于 2017-6-13 15:08
来一道扩展题，同样的思路可解

1. def slide(x, y, i):
   
2.     global mmax
   
3.     for mv in moves:
   
4.         lx = x + mv[0]
   
5.         ly = y + mv[1]
   
6.         if -1 < lx < n and -1 < ly < m and H[lx][ly] < H[x][y]:
   
7.             slide(lx, ly, i + 1)
   
8.     if mmax < i:
   
9.         mmax = i
   
10. 
    
11.    
    
12. n = 5
    
13. m = 4
    
14. H = [[i + j * m  for i in range(1, m + 1)] for j in range(n)]
    
15. moves = [(1, 0), (0, 1), (-1, 0), (0, -1)]
    
16. ma = 0
    
17. for i in range(n):
    
18.     for j in range(m):
    
19.         mmax = 0
    
20.         slide(i, j, 0)
    
21.         if ma < mmax:
    
22.             ma = mmax
    
23. 
    
24. print(ma)

复制代码

有个问题啊，就是递归函数里的变量何时需要声明为全局变量，这里n，m都没有声明就可以通过，但是mmax没有声明就不可以运行，这是为什么呢？

jerryxjr1220

WelanceLee 发表于 2017-6-13 16:04
有个问题啊，就是递归函数里的变量何时需要声明为全局变量，这里n，m都没有声明就可以通过，但是mmax没 ...

因为mmax在递归过程中不断在赋值，如果你不声明全局变量的话，递归调用就会出错。
m，n的值应该是没有变化吧，不管何时调用都是不变的。

jerryxjr1220

WelanceLee 发表于 2017-6-13 16:04
有个问题啊，就是递归函数里的变量何时需要声明为全局变量，这里n，m都没有声明就可以通过，但是mmax没 ...

更新一个动态规划的算法

1.     import copy
   
2.     n = 4
   
3.     m = 4
   
4.     H= [
   
5.     [1, 2, 3, 4],
   
6.     [5,6,7,8],
   
7.     [9,10,11,12],
   
8.     [13,14,15,16]]
   
9.     dp = [[0] * m for i in range(n)]
   
10.     bk = [[]]
    
11.     while dp != bk:
    
12.             bk = copy.deepcopy(dp)
    
13.             queue = [[i, j] for i in range(n) for j in range(m)]
    
14.             d = [[0, 1], [1, 0], [-1, 0], [0, -1]]
    
15.      
    
16.             while queue:
    
17.                     q = queue.pop(0)
    
18.                     for v in d:
    
19.                             nq = [q[0] + v[0], q[1] + v[1]]
    
20.                             if 0 <= nq[0] < n and 0 <= nq[1] < m and H[nq[0]][nq[1]] < H[q[0]][q[1]]:
    
21.                                     dp[q[0]][q[1]] = max(dp[nq[0]][nq[1]] + 1, dp[q[0]][q[1]])
    
22.                             else:
    
23.                                     continue
    
24.     print(dp)
    
25.     print(max((max(i) for i in dp)))

复制代码

qaz123765

来看下算法

蝈蝈vic

学习

liuwenqi

pikaqiu123

6666666666666666

新手·ing

看看

全体成员

学习喽

JAY饭

1. maze = [
   
2. [1 ,0, 1, 0, 0, 0],
   
3. [1, 1, 1, 1, 0, 1],
   
4. [0, 0, 1, 0, 1, 0],
   
5. [1, 0, 1, 0, 1, 1],
   
6. [1, 1, 1, 1, 1, 1],
   
7. [0, 1, 0, 1, 0, 0],
   
8. [0, 1, 0, 1, 1, 1]]
   
9. 
   
10. a,b = 0,0
    
11. end = (3,5)
    
12. maze[0][0] = 8
    
13. n = 2
    
14. 
    
15. def turn(a,b,n):
    
16.     #设置方向和步长
    
17.     t = [[1,0],[0,1],[0,-1],[-1,0]]   
    
18.     #递归终结条件，到达终点坐标
    
19.     if a == 3 and b==5:
    
20.         #条件式返回，终止递归，且和下面的return 1 形成单一返回
    
21.         return 1
    
22.     #每一步的每一种可能
    
23.     for i in t:
    
24.         a1,b1 = a,b
    
25.         a1 += i[0]
    
26.         b1 += i[1]
    
27.         #确定下一个落脚点的条件
    
28.         if 0<=a1<=6 and 0<=b1<=5:
    
29.             if maze[a1][b1] == 1:
    
30.                 #防止无限 原地前进返回
    
31.                 maze[a1][b1] = 8
    
32.                 #呼应最终的返回条件
    
33.                 if turn(a1,b1,n+1) == 1:
    
34.                     return 1
    
35.                 #一旦此条路不通，当重新启用下一种可能之前，
    
36.                 #当前脚下的地点初始化
    
37.                 maze[a1][b1] = 1
    
38. 
    
39. turn(a,b,n)
    
40. for i in maze:

复制代码

JAY饭

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

先给大神拜个新年啊~
虽然这几天一直忙着玩，但从春节前一直记挂着你说的欧拉83题，有空就想想，今天总算静下心来解决了
代码很乱，思路是先用动态规划法大致取一个值，然后利用这个值不断探索，取小于这个值的路径，然后
继续利用得到下一个较小的路径总和值，继续循环。最后得到了正确的结果，写过递归，但是运行速度太慢
慢慢慢慢慢，放弃了，最后是用循环解出来的，大概三四秒。想过很多方案都失败了，中间不断的受挫，还
好坚持了下来.

1. import shuzimigong as sh
   
2. 
   
3. t = sh.t.split('\n')
   
4. s = [[] for i in range(80)]
   
5. for i in range(80):
   
6.     for each in  t[i].split(','):
   
7.         s[i].append(int(each))
   
8. 
   
9. 
   
10. right = {(0,0):s[0][0]}
    
11. right1 = {}
    
12. t = [(-1,0),(1,0),(0,1),(0,-1)]
    
13. 
    
14. def move():
    
15.     count = s[0][0]
    
16.     a = 0
    
17.     b = 0
    
18.     while True:
    
19.         if a == 79 and b == 79:
    
20.             break
    
21.         if a == 79 and b != 79:
    
22.             count += s[a][b+1]
    
23.             b += 1
    
24.         elif a != 79 and b == 79:
    
25.             count += s[a+1][b]
    
26.             a += 1
    
27.         else:   
    
28.             count += min(s[a+1][b],s[a][b+1])
    
29.             if s[a+1][b] <= s[a][b+1]:
    
30.                 a += 1
    
31.             else:
    
32.                 b += 1
    
33.     print(count)
    
34.     return count
    
35. 
    
36. 
    
37. def go(a,b,c,count):
    
38.     q = [(a,b,c)]
    
39.     while len(q) != 0:
    
40.         (a,b,c) = q.pop(0)
    
41.         
    
42.         for i in t:
    
43.             a1 = a + i[0]
    
44.             b1 = b + i[1]
    
45.             if 0<=a1<80 and 0<=b1<80:
    
46.                 c1 = c + s[a1][b1]
    
47.                
    
48.                 if c1 <count:
    
49.                     if (a1,b1) == (79,79):
    
50.                         print(c1)
    
51.                         return c1
    
52.                     if (a1,b1) not in right:
    
53.                         
    
54.                         q.append((a1,b1,c1))
    
55.                         right[(a1,b1)] = c1
    
56.                     if (a1,b1) in right:
    
57.                         if c1 < right[a1,b1]:
    
58.                             if (a1,b1,right[(a1,b1)]) in q:
    
59.                                 q.remove((a1,b1,right[(a1,b1)]))
    
60.                            
    
61.                             right[(a1,b1)] = c1
    
62.                             right1[(a1,b1)] = (a,b)
    
63.                             q.append((a1,b1,c1))
    
64.                         
    
65.    
    
66.                     
    
67. def main():
    
68.     global right
    
69.     global right1
    
70.     count = move()
    
71.    
    
72.     while True:
    
73.         a = 0
    
74.         b = 0
    
75.         c = s[0][0]
    
76.         right = {(0,0):s[0][0]}
    
77.         right1 = {}
    
78.         t = go(a,b,c,count)
    
79.         if t != None:
    
80.             count = t
    
81. 
    
82.         else:
    
83.             print(count)
    
84.                
    
85.             break
    
86. 
    
87. main()
    

复制代码

jerryxjr1220

JAY饭 发表于 2018-2-21 21:11
先给大神拜个新年啊~
虽然这几天一直忙着玩，但从春节前一直记挂着你说的欧拉83题，有空就想想，今天总 ...

新年好！
过年还记着解题，为你的努力点个赞！

KING_NJ

666

junlei007

888888

sheepLD

学习一下

江都梅雪

学习学习，谢谢！

weretop

感谢分享这么牛逼的文件快点看

zanglanju