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
来一道扩展题，同样的思路可解

def slide(x, y, i):
    global mmax
    for mv in moves:
        lx = x + mv[0]
        ly = y + mv[1]
        if -1 < lx < n and -1 < ly < m and H[lx][ly] < H[x][y]:
            slide(lx, ly, i + 1)
    if mmax < i:
        mmax = i

    
n = 5
m = 4
H = [[i + j * m  for i in range(1, m + 1)] for j in range(n)]
moves = [(1, 0), (0, 1), (-1, 0), (0, -1)]
ma = 0
for i in range(n):
    for j in range(m):
        mmax = 0
        slide(i, j, 0)
        if ma < mmax:
            ma = mmax

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没 ...

更新一个动态规划的算法

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

qaz123765

来看下算法

蝈蝈vic

学习

liuwenqi

pikaqiu123

6666666666666666

新手·ing

看看

全体成员

学习喽

JAY饭

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]]

a,b = 0,0
end = (3,5)
maze[0][0] = 8
n = 2

def turn(a,b,n):
    #设置方向和步长
    t = [[1,0],[0,1],[0,-1],[-1,0]]    
    #递归终结条件，到达终点坐标
    if a == 3 and b==5:
        #条件式返回，终止递归，且和下面的return 1 形成单一返回
        return 1
    #每一步的每一种可能
    for i in t:
        a1,b1 = a,b
        a1 += i[0]
        b1 += i[1]
        #确定下一个落脚点的条件
        if 0<=a1<=6 and 0<=b1<=5:
            if maze[a1][b1] == 1:
                #防止无限 原地前进返回
                maze[a1][b1] = 8
                #呼应最终的返回条件
                if turn(a1,b1,n+1) == 1:
                    return 1
                #一旦此条路不通，当重新启用下一种可能之前，
                #当前脚下的地点初始化
                maze[a1][b1] = 1

turn(a,b,n)
for i in maze:

JAY饭

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

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

import shuzimigong as sh

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


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

def move():
    count = s[0][0]
    a = 0
    b = 0
    while True:
        if a == 79 and b == 79:
            break
        if a == 79 and b != 79:
            count += s[a][b+1]
            b += 1
        elif a != 79 and b == 79:
            count += s[a+1][b]
            a += 1
        else:    
            count += min(s[a+1][b],s[a][b+1]) 
            if s[a+1][b] <= s[a][b+1]:
                a += 1
            else:
                b += 1
    print(count)
    return count


def go(a,b,c,count):
    q = [(a,b,c)]
    while len(q) != 0:
        (a,b,c) = q.pop(0)
        
        for i in t:
            a1 = a + i[0]
            b1 = b + i[1]
            if 0<=a1<80 and 0<=b1<80:
                c1 = c + s[a1][b1]
                
                if c1 <count:
                    if (a1,b1) == (79,79):
                        print(c1)
                        return c1
                    if (a1,b1) not in right:
                        
                        q.append((a1,b1,c1))
                        right[(a1,b1)] = c1
                    if (a1,b1) in right:
                        if c1 < right[a1,b1]:
                            if (a1,b1,right[(a1,b1)]) in q:
                                q.remove((a1,b1,right[(a1,b1)]))
                            
                            right[(a1,b1)] = c1
                            right1[(a1,b1)] = (a,b)
                            q.append((a1,b1,c1))
                        
    
                    
def main():
    global right
    global right1
    count = move()
    
    while True:
        a = 0
        b = 0
        c = s[0][0]
        right = {(0,0):s[0][0]}
        right1 = {}
        t = go(a,b,c,count)
        if t != None:
            count = t

        else:
            print(count)
                
            break

main()

jerryxjr1220

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

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

KING_NJ

666

junlei007

888888

sheepLD

学习一下

江都梅雪

学习学习，谢谢！

weretop

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

zanglanju