鱼C论坛

 找回密码
 立即注册
楼主: jerryxjr1220

[技术交流] python小练习(055):回溯法(深度优先搜索)与探索法(广度优先搜索)求解迷宫问题

[复制链接]
 楼主| 发表于 2017-6-13 15:08:32 | 显示全部楼层

来一道扩展题,同样的思路可解
我们把场地分为一个个的格子,给每个格子标定一个整数,代表这个格子所代表的地面的海拔高度。
比赛的参赛者可以从任意一个格子开始,但只能向相邻的四个格子移动,并且目地格子的高度必须
小于现在所在格子的高度。我们假设从一个格子滑行到另一个格子所用的时间为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.
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-6-13 16:04:52 | 显示全部楼层
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. n = 5
  12. m = 4
  13. H = [[i + j * m  for i in range(1, m + 1)] for j in range(n)]
  14. moves = [(1, 0), (0, 1), (-1, 0), (0, -1)]
  15. ma = 0
  16. for i in range(n):
  17.     for j in range(m):
  18.         mmax = 0
  19.         slide(i, j, 0)
  20.         if ma < mmax:
  21.             ma = mmax

  22. print(ma)
复制代码

有个问题啊,就是递归函数里的变量何时需要声明为全局变量,这里n,m都没有声明就可以通过,但是mmax没有声明就不可以运行,这是为什么呢?
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2017-6-13 19:50:29 | 显示全部楼层
WelanceLee 发表于 2017-6-13 16:04
有个问题啊,就是递归函数里的变量何时需要声明为全局变量,这里n,m都没有声明就可以通过,但是mmax没 ...

因为mmax在递归过程中不断在赋值,如果你不声明全局变量的话,递归调用就会出错。
m,n的值应该是没有变化吧,不管何时调用都是不变的。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2017-6-13 19:54:46 | 显示全部楼层
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)))
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-6-23 13:43:50 From FishC Mobile | 显示全部楼层
来看下算法
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

头像被屏蔽
发表于 2017-6-26 09:32:45 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2017-7-14 10:44:12 | 显示全部楼层
学习
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

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

使用道具 举报

发表于 2017-12-13 12:07:20 | 显示全部楼层
6666666666666666
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-12-24 09:33:47 | 显示全部楼层
看看
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2018-2-3 12:18:51 | 显示全部楼层
学习喽

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

使用道具 举报

发表于 2018-2-13 16:12:55 | 显示全部楼层
  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. a,b = 0,0
  10. end = (3,5)
  11. maze[0][0] = 8
  12. n = 2

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

  36. turn(a,b,n)
  37. for i in maze:
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

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

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

  2. t = sh.t.split('\n')
  3. s = [[] for i in range(80)]
  4. for i in range(80):
  5.     for each in  t[i].split(','):
  6.         s[i].append(int(each))


  7. right = {(0,0):s[0][0]}
  8. right1 = {}
  9. t = [(-1,0),(1,0),(0,1),(0,-1)]

  10. def move():
  11.     count = s[0][0]
  12.     a = 0
  13.     b = 0
  14.     while True:
  15.         if a == 79 and b == 79:
  16.             break
  17.         if a == 79 and b != 79:
  18.             count += s[a][b+1]
  19.             b += 1
  20.         elif a != 79 and b == 79:
  21.             count += s[a+1][b]
  22.             a += 1
  23.         else:   
  24.             count += min(s[a+1][b],s[a][b+1])
  25.             if s[a+1][b] <= s[a][b+1]:
  26.                 a += 1
  27.             else:
  28.                 b += 1
  29.     print(count)
  30.     return count


  31. def go(a,b,c,count):
  32.     q = [(a,b,c)]
  33.     while len(q) != 0:
  34.         (a,b,c) = q.pop(0)
  35.         
  36.         for i in t:
  37.             a1 = a + i[0]
  38.             b1 = b + i[1]
  39.             if 0<=a1<80 and 0<=b1<80:
  40.                 c1 = c + s[a1][b1]
  41.                
  42.                 if c1 <count:
  43.                     if (a1,b1) == (79,79):
  44.                         print(c1)
  45.                         return c1
  46.                     if (a1,b1) not in right:
  47.                         
  48.                         q.append((a1,b1,c1))
  49.                         right[(a1,b1)] = c1
  50.                     if (a1,b1) in right:
  51.                         if c1 < right[a1,b1]:
  52.                             if (a1,b1,right[(a1,b1)]) in q:
  53.                                 q.remove((a1,b1,right[(a1,b1)]))
  54.                            
  55.                             right[(a1,b1)] = c1
  56.                             right1[(a1,b1)] = (a,b)
  57.                             q.append((a1,b1,c1))
  58.                         
  59.    
  60.                     
  61. def main():
  62.     global right
  63.     global right1
  64.     count = move()
  65.    
  66.     while True:
  67.         a = 0
  68.         b = 0
  69.         c = s[0][0]
  70.         right = {(0,0):s[0][0]}
  71.         right1 = {}
  72.         t = go(a,b,c,count)
  73.         if t != None:
  74.             count = t

  75.         else:
  76.             print(count)
  77.                
  78.             break

  79. main()
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2018-2-22 10:46:23 | 显示全部楼层
JAY饭 发表于 2018-2-21 21:11
先给大神拜个新年啊~
虽然这几天一直忙着玩,但从春节前一直记挂着你说的欧拉83题,有空就想想,今天总 ...

新年好!
过年还记着解题,为你的努力点个赞!
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2018-3-26 10:28:56 | 显示全部楼层
666
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2018-3-27 16:45:01 | 显示全部楼层
888888
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2018-5-26 14:00:25 | 显示全部楼层
学习一下
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2018-6-10 14:16:19 | 显示全部楼层

学习学习,谢谢!
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2018-6-10 15:06:34 From FishC Mobile | 显示全部楼层
感谢分享这么牛逼的文件快点看
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2018-6-11 21:34:15 | 显示全部楼层
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

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

本版积分规则

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

GMT+8, 2024-3-29 03:56

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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