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

Jonin616

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

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

Jonin616

1. move = [(1,2),(2,1),(2,-1),(1,-2),(-1,-2),(-2,-1),(-2,1),(-1,2)]
   
2. hlocate = [0,0]
   
3. step = []
   
4. step.append(hlocate.copy())
   
5. dep = 1
   
6. hlocate_next = [0,0]
   
7. def find(hlocate,dep):
   
8.     #print(dep,step)
   
9.     if dep == 65:
   
10.         return 1
    
11.     for each in move:
    
12.         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):
    
13.             hlocate_next[0] = hlocate[0] + each[0]
    
14.             hlocate_next[1] = hlocate[1] + each[1]
    
15.             step.append(hlocate_next.copy())
    
16.             
    
17.             if find(hlocate_next,dep + 1) == 1:
    
18.                 return 1
    
19.             else:
    
20.                 step.remove(step[len(step) - 1])
    
21.                 hlocate = step[len(step) - 1].copy()
    
22.     return 0
    
23. 
    
24. def fuckit():
    
25.     if find(hlocate,dep + 1) == 1:
    
26.         print(step)
    
27.         print('成功')
    
28. 
    
29. fuckit()

复制代码

Jonin616

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

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

jerryxjr1220

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

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

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

Jonin616

1. #马踏棋盘
   
2. def horsejump2():
   
3.     direct = [(1,2),(2,1),(2,-1),(1,-2),(-1,-2),(-2,-1),(-2,1),(-1,2)]
   
4.     dir_count = []
   
5.     for i in range(0,65):
   
6.         dir_count.append(0)
   
7. 
   
8.     chess_way = []
   
9.     count_step = 0
   
10.     hlocate = [0,0]
    
11.     chess_way.append(hlocate.copy())
    
12. 
    
13.     finish = 0
    
14.     back_flag = 0
    
15. 
    
16.     while finish == 0:
    
17.         while back_flag == 0:
    
18.             if len(chess_way) == 64 or dir_count[count_step] == 8:
    
19.                 back_flag = 1
    
20.                 break
    
21.             else:
    
22.                 if (0 <= hlocate[0] + direct[dir_count[count_step]][0] <= 7) and (0 <= hlocate[1] + direct[dir_count[count_step]][1] <= 7):
    
23.                     if [hlocate[0] + direct[dir_count[count_step]][0],hlocate[1] + direct[dir_count[count_step]][1]] in chess_way:
    
24.                         dir_count[count_step] += 1
    
25.                         continue
    
26.                     else:
    
27.                         hlocate[0] += direct[dir_count[count_step]][0]
    
28.                         hlocate[1] += direct[dir_count[count_step]][1]
    
29.                         dir_count[count_step] += 1
    
30.                         count_step += 1
    
31.                         chess_way.append(hlocate.copy())
    
32.                 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:
    
33.                     dir_count[count_step] += 1
    
34. 
    
35.         if back_flag == 1:
    
36.             
    
37.             dir_count[count_step] = 0
    
38.             count_step -= 1
    
39.             chess_way.remove(hlocate.copy())
    
40.             hlocate = chess_way[count_step].copy()
    
41.             back_flag = 0
    
42.         if len(chess_way) == 64:
    
43.             finish = 1
    
44.             print('路径为：',chess_way)
    
45. 
    

复制代码

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

1. #马踏棋盘
   
2. def horsejump2():
   
3.     direct = [(1,2),(2,1),(2,-1),(1,-2),(-1,-2),(-2,-1),(-2,1),(-1,2)]
   
4.     dir_count = []
   
5.     for i in range(0,65):
   
6.         dir_count.append(0)
   
7. 
   
8.     chess_way = []
   
9.     count_step = 0
   
10.     hlocate = [0,0]
    
11.     chess_way.append(hlocate.copy())
    
12. 
    
13.     finish = 0
    
14.     back_flag = 0
    
15. 
    
16.     while finish == 0:
    
17.         while back_flag == 0:
    
18.             
    
19.             if len(chess_way) == 64 or dir_count[count_step] == 8:
    
20.                 back_flag = 1
    
21.                 break
    
22.                
    
23.             else:
    
24.                 if (0 <= hlocate[0] + direct[dir_count[count_step]][0] <= 7) and (0 <= hlocate[1] + direct[dir_count[count_step]][1] <= 7):
    
25.                     if [hlocate[0] + direct[dir_count[count_step]][0],hlocate[1] + direct[dir_count[count_step]][1]] in chess_way:
    
26.                         dir_count[count_step] += 1
    
27.                         continue
    
28.                     else:
    
29.                         hlocate[0] += direct[dir_count[count_step]][0]
    
30.                         hlocate[1] += direct[dir_count[count_step]][1]
    
31.                         dir_count[count_step] += 1
    
32.                         count_step += 1
    
33.                         chess_way.append(hlocate.copy())
    
34.                 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:
    
35.                     dir_count[count_step] += 1
    
36.         if len(chess_way) == 64:
    
37. #在这里我将if len(chess_way) == 64 语句块移到了前面执行 这样就避免刚才我在楼上说的那个死循环bug了
    
38.             finish = 1
    
39.             print('路径为：',chess_way)
    
40.         if back_flag == 1:
    
41.             dir_count[count_step] = 0
    
42.             count_step -= 1
    
43.             chess_way.remove(hlocate.copy())
    
44.             hlocate = chess_way[count_step].copy()
    
45.             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

1. n = 6
   
2. chess = [[0]*n for i in range(n)]
   
3. 
   
4. start = (0, 0)
   
5. moves = [[2, 1], [2, -1], [-2, 1], [-2, -1], [1, 2], [1,-2], [-1, 2], [-1, -2]]
   
6. 
   
7. chess[start[0]][start[1]] = 1
   
8. 
   
9. def dfs(loc, step):
   
10.     if step == n*n:
    
11.         for each in chess:
    
12.             print(each)
    
13.         return True
    
14.     for each in moves:
    
15.         x = loc[0] + each[0]
    
16.         y = loc[1] + each[1]
    
17.         if -1 < x < n and -1< y < n and chess[x][y] == 0:
    
18.             chess[x][y] = step + 1
    
19.             if dfs((x, y), step + 1):
    
20.                 return True
    
21.             chess[x][y] = 0
    
22. 
    
23. 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分钟也算不出来……