python小练习（068）：回溯法（深度优先搜索）30行代码求解“马踏棋盘”问题

Jonin616

jerryxjr1220 发表于 2017-2-9 15:42
不能说效率高，一般递归的效率都不太高，但是一般回溯法都是用递归写的，代码简洁，可读性强。

现在只能自己先写一个递归版本

Jonin616

move = [(1,2),(2,1),(2,-1),(1,-2),(-1,-2),(-2,-1),(-2,1),(-1,2)]
hlocate = [0,0]
step = []
step.append(hlocate.copy())
dep = 1
hlocate_next = [0,0]
def find(hlocate,dep):
    #print(dep,step)
    if dep == 65:
        return 1
    for each in move:
        if (0 <= hlocate[0] + each[0] <= 7 and 0 <= hlocate[1] + each[1] <=7 and [hlocate[0] + each[0],hlocate[1] + each[1]] not in step):
            hlocate_next[0] = hlocate[0] + each[0]
            hlocate_next[1] = hlocate[1] + each[1]
            step.append(hlocate_next.copy())
            
            if find(hlocate_next,dep + 1) == 1:
                return 1
            else:
                step.remove(step[len(step) - 1])
                hlocate = step[len(step) - 1].copy()
    return 0

def fuckit():
    if find(hlocate,dep + 1) == 1:
        print(step)
        print('成功')

fuckit()

Jonin616

Jonin616 发表于 2017-2-9 20:20

同样用递归，运行速度是楼主的两倍，我想差距应该是出在频繁的append和remove还有copy操作上

jerryxjr1220

Jonin616 发表于 2017-2-9 20:23
同样用递归，运行速度是楼主的两倍，我想差距应该是出在频繁的append和remove还有copy操作上

能写出来就已经不错了，优化可以继续做

不过递归算法是比较容易写的，我想看看你的非递归版本怎么写？

Jonin616

#马踏棋盘
def horsejump2():
    direct = [(1,2),(2,1),(2,-1),(1,-2),(-1,-2),(-2,-1),(-2,1),(-1,2)]
    dir_count = []
    for i in range(0,65):
        dir_count.append(0)

    chess_way = []
    count_step = 0
    hlocate = [0,0]
    chess_way.append(hlocate.copy())

    finish = 0
    back_flag = 0

    while finish == 0:
        while back_flag == 0:
            if len(chess_way) == 64 or dir_count[count_step] == 8:
                back_flag = 1
                break
            else:
                if (0 <= hlocate[0] + direct[dir_count[count_step]][0] <= 7) and (0 <= hlocate[1] + direct[dir_count[count_step]][1] <= 7):
                    if [hlocate[0] + direct[dir_count[count_step]][0],hlocate[1] + direct[dir_count[count_step]][1]] in chess_way:
                        dir_count[count_step] += 1
                        continue
                    else:
                        hlocate[0] += direct[dir_count[count_step]][0]
                        hlocate[1] += direct[dir_count[count_step]][1]
                        dir_count[count_step] += 1
                        count_step += 1
                        chess_way.append(hlocate.copy())
                if hlocate[0] + direct[dir_count[count_step]][0] < 0 or hlocate[0] + direct[dir_count[count_step]][0] > 7 or hlocate[1] + direct[dir_count[count_step]][1] < 0 or hlocate[1] + direct[dir_count[count_step]][1] > 7:
                    dir_count[count_step] += 1

        if back_flag == 1:
            
            dir_count[count_step] = 0
            count_step -= 1
            chess_way.remove(hlocate.copy())
            hlocate = chess_way[count_step].copy()
            back_flag = 0
        if len(chess_way) == 64:
            finish = 1
            print('路径为：',chess_way)

Jonin616

jerryxjr1220 发表于 2017-2-9 22:06
能写出来就已经不错了，优化可以继续做

不过递归算法是比较容易写的，我想看看你的非递归版 ...

已经贴出来了  讲真 这段程序从昨天下午5点跑到快晚上12点都没跑出结果，也没有报错 不是单纯因为效率低的话那肯定是有bug了 但我一时半会真的找不出来问题在哪

jerryxjr1220

从你的程序看，应该是死循环了。
当你的回溯标志back_flag=1时，开始回溯，但是你的回溯只执行了一步，然后又重新进入循环。真正的回溯应该是可以连续回溯到上一节点的，而不是只回溯一步。

Jonin616

jerryxjr1220 发表于 2017-2-10 07:17
从你的程序看，应该是死循环了。
当你的回溯标志back_flag=1时，开始回溯，但是你的回溯只执行了一步，然 ...

好 我看看 然后改进一下

Jonin616

jerryxjr1220 发表于 2017-2-10 07:17
从你的程序看，应该是死循环了。
当你的回溯标志back_flag=1时，开始回溯，但是你的回溯只执行了一步，然 ...

执行回溯一步后退回到上一步，在进入while back_flag == 0循环体时立刻判断上一步的dir_count[count_step]参数是否也是等于8 如果等于8 就再进行回溯 我是这样做的  这样应该不会出现死循环问题吧

jerryxjr1220

Jonin616 发表于 2017-2-10 15:18
执行回溯一步后退回到上一步，在进入while back_flag == 0循环体时立刻判断上一步的dir_count[count_step ...

举个例子，如果搜索到了末节点，而且这条路径已经走完了，回溯法应该是连续回溯到初始节点再走另外一条路径。你只回溯一步的话，假如末节点是第64步，你退回到63步，又进入循环，又到64步。意味着一直在第63和64步之间死循环。
回溯法很重要的一点是，递归有"记忆"功能，可以记住退回去的路。

Jonin616

jerryxjr1220 发表于 2017-2-10 15:28
举个例子，如果搜索到了末节点，而且这条路径已经走完了，回溯法应该是连续回溯到初始节点再走另外一条路 ...

找到错误了  是代码的顺序不对造成了死循环 刚才成功运行出正确答案了 您刚才说的话提醒到我了 也是死循环问题  在我先前的代码中当chess_way数组长度等于64时，原本应当执行 if len(chess_way) == 64的语句块打印结果，但我将这段代码放到了if back_flag == 1:之后了，由于当chess_way长度等于64时也会触发back_flag = 1，所以这样就变成if back_flag == 1:语句块先于if len(chess_way) == 64执行，从而造成了死循环

Jonin616

#马踏棋盘
def horsejump2():
    direct = [(1,2),(2,1),(2,-1),(1,-2),(-1,-2),(-2,-1),(-2,1),(-1,2)]
    dir_count = []
    for i in range(0,65):
        dir_count.append(0)

    chess_way = []
    count_step = 0
    hlocate = [0,0]
    chess_way.append(hlocate.copy())

    finish = 0
    back_flag = 0

    while finish == 0:
        while back_flag == 0:
            
            if len(chess_way) == 64 or dir_count[count_step] == 8:
                back_flag = 1
                break
                
            else:
                if (0 <= hlocate[0] + direct[dir_count[count_step]][0] <= 7) and (0 <= hlocate[1] + direct[dir_count[count_step]][1] <= 7):
                    if [hlocate[0] + direct[dir_count[count_step]][0],hlocate[1] + direct[dir_count[count_step]][1]] in chess_way:
                        dir_count[count_step] += 1
                        continue
                    else:
                        hlocate[0] += direct[dir_count[count_step]][0]
                        hlocate[1] += direct[dir_count[count_step]][1]
                        dir_count[count_step] += 1
                        count_step += 1
                        chess_way.append(hlocate.copy())
                if hlocate[0] + direct[dir_count[count_step]][0] < 0 or hlocate[0] + direct[dir_count[count_step]][0] > 7 or hlocate[1] + direct[dir_count[count_step]][1] < 0 or hlocate[1] + direct[dir_count[count_step]][1] > 7:
                    dir_count[count_step] += 1
        if len(chess_way) == 64:
#在这里我将if len(chess_way) == 64 语句块移到了前面执行 这样就避免刚才我在楼上说的那个死循环bug了
            finish = 1
            print('路径为：',chess_way)
        if back_flag == 1:
            dir_count[count_step] = 0
            count_step -= 1
            chess_way.remove(hlocate.copy())
            hlocate = chess_way[count_step].copy()
            back_flag = 0

Jonin616

jerryxjr1220 发表于 2017-2-10 15:28
举个例子，如果搜索到了末节点，而且这条路径已经走完了，回溯法应该是连续回溯到初始节点再走另外一条路 ...

另一个是您提到的回溯到原点的问题，由于这个程序是设计成当chess_way等于64时就结束程序，所以之后的回溯操作我就没有关心了 还有一点是 程序的执行时间在3分钟左右，比之前我写的那个递归版本慢了快2分钟 还是很谢谢你刚才的回复 不然我短时间内根本不会注意到程序存在这样的bug

jerryxjr1220

Jonin616 发表于 2017-2-10 19:13
另一个是您提到的回溯到原点的问题，由于这个程序是设计成当chess_way等于64时就结束程序，所以之后的 ...

所以回溯法还是应该用递归写，首先是程序比较简洁（30行代码就够了），可读性也强，效率的话，没有做过比较，如果按照你的说法，效率可能也是递归的高。

荷风香煞

学习

zcr林枫

厉害

WelanceLee

学习下

WelanceLee

n = 6
chess = [[0]*n for i in range(n)]

start = (0, 0)
moves = [[2, 1], [2, -1], [-2, 1], [-2, -1], [1, 2], [1,-2], [-1, 2], [-1, -2]]

chess[start[0]][start[1]] = 1

def dfs(loc, step):
    if step == n*n:
        for each in chess:
            print(each)
        return True
    for each in moves:
        x = loc[0] + each[0]
        y = loc[1] + each[1]
        if -1 < x < n and -1< y < n and chess[x][y] == 0:
            chess[x][y] = step + 1
            if dfs((x, y), step + 1):
                return True
            chess[x][y] = 0

dfs(start, 1)

求教啊，思路应该跟你的思路非常接近，但是我的程序只能算n = 6的情况， n =8的情况就很长时间也计算不出来了，为什么吗呢？

jerryxjr1220

WelanceLee 发表于 2017-6-14 18:42
求教啊，思路应该跟你的思路非常接近，但是我的程序只能算n = 6的情况， n =8的情况就很长时间也计算不出 ...

程序的逻辑应该是对的，但是执行效率不高。
其实我原本的程序效率也不高，差不多n=8的话，要1分多钟才出结果。

WelanceLee

jerryxjr1220 发表于 2017-6-14 20:06
程序的逻辑应该是对的，但是执行效率不高。
其实我原本的程序效率也不高，差不多n=8的话，要1分多钟才出 ...

我的是10分钟也算不出来……