jerryxjr1220 发表于 2017-2-9 15:42
不能说效率高，一般递归的效率都不太高，但是一般回溯法都是用递归写的，代码简洁，可读性强。
现在只能自己先写一个递归版本
本帖最后由 Jonin616 于 2017-2-9 20:24 编辑
move = [(1,2),(2,1),(2,-1),(1,-2),(-1,-2),(-2,-1),(-2,1),(-1,2)]
hlocate =
step = []
step.append(hlocate.copy())
dep = 1
hlocate_next =
def find(hlocate,dep):
#print(dep,step)
if dep == 65:
return 1
for each in move:
if (0 <= hlocate + each <= 7 and 0 <= hlocate + each <=7 and + each,hlocate + each] not in step):
hlocate_next = hlocate + each
hlocate_next = hlocate + each
step.append(hlocate_next.copy())
if find(hlocate_next,dep + 1) == 1:
return 1
else:
step.remove(step)
hlocate = step.copy()
return 0
def fuckit():
if find(hlocate,dep + 1) == 1:
print(step)
print('成功')
fuckit()
Jonin616 发表于 2017-2-9 20:20
同样用递归，运行速度是楼主的两倍，我想差距应该是出在频繁的append和remove还有copy操作上
Jonin616 发表于 2017-2-9 20:23
同样用递归，运行速度是楼主的两倍，我想差距应该是出在频繁的append和remove还有copy操作上
能写出来就已经不错了，优化可以继续做{:5_106:}
不过递归算法是比较容易写的，我想看看你的非递归版本怎么写？{:5_109:}
本帖最后由 Jonin616 于 2017-2-10 00:33 编辑
#马踏棋盘
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 =
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 == 8:
back_flag = 1
break
else:
if (0 <= hlocate + direct] <= 7) and (0 <= hlocate + direct] <= 7):
if + direct],hlocate + direct]] in chess_way:
dir_count += 1
continue
else:
hlocate += direct]
hlocate += direct]
dir_count += 1
count_step += 1
chess_way.append(hlocate.copy())
if hlocate + direct] < 0 or hlocate + direct] > 7 or hlocate + direct] < 0 or hlocate + direct] > 7:
dir_count += 1
if back_flag == 1:
dir_count = 0
count_step -= 1
chess_way.remove(hlocate.copy())
hlocate = chess_way.copy()
back_flag = 0
if len(chess_way) == 64:
finish = 1
print('路径为：',chess_way)
jerryxjr1220 发表于 2017-2-9 22:06
能写出来就已经不错了，优化可以继续做
不过递归算法是比较容易写的，我想看看你的非递归版 ...
已经贴出来了讲真 这段程序从昨天下午5点跑到快晚上12点都没跑出结果，也没有报错 不是单纯因为效率低的话那肯定是有bug了 但我一时半会真的找不出来问题在哪
从你的程序看，应该是死循环了。
当你的回溯标志back_flag=1时，开始回溯，但是你的回溯只执行了一步，然后又重新进入循环。真正的回溯应该是可以连续回溯到上一节点的，而不是只回溯一步。
jerryxjr1220 发表于 2017-2-10 07:17
从你的程序看，应该是死循环了。
当你的回溯标志back_flag=1时，开始回溯，但是你的回溯只执行了一步，然 ...
好 我看看 然后改进一下
jerryxjr1220 发表于 2017-2-10 07:17
从你的程序看，应该是死循环了。
当你的回溯标志back_flag=1时，开始回溯，但是你的回溯只执行了一步，然 ...
执行回溯一步后退回到上一步，在进入while back_flag == 0循环体时立刻判断上一步的dir_count参数是否也是等于8 如果等于8 就再进行回溯 我是这样做的这样应该不会出现死循环问题吧
Jonin616 发表于 2017-2-10 15:18
执行回溯一步后退回到上一步，在进入while back_flag == 0循环体时立刻判断上一步的dir_count
举个例子，如果搜索到了末节点，而且这条路径已经走完了，回溯法应该是连续回溯到初始节点再走另外一条路径。你只回溯一步的话，假如末节点是第64步，你退回到63步，又进入循环，又到64步。意味着一直在第63和64步之间死循环。
回溯法很重要的一点是，递归有"记忆"功能，可以记住退回去的路。
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执行，从而造成了死循环
#马踏棋盘
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 =
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 == 8:
back_flag = 1
break
else:
if (0 <= hlocate + direct] <= 7) and (0 <= hlocate + direct] <= 7):
if + direct],hlocate + direct]] in chess_way:
dir_count += 1
continue
else:
hlocate += direct]
hlocate += direct]
dir_count += 1
count_step += 1
chess_way.append(hlocate.copy())
if hlocate + direct] < 0 or hlocate + direct] > 7 or hlocate + direct] < 0 or hlocate + direct] > 7:
dir_count += 1
if len(chess_way) == 64:
#在这里我将if len(chess_way) == 64 语句块移到了前面执行 这样就避免刚才我在楼上说的那个死循环bug了
finish = 1
print('路径为：',chess_way)
if back_flag == 1:
dir_count = 0
count_step -= 1
chess_way.remove(hlocate.copy())
hlocate = chess_way.copy()
back_flag = 0
jerryxjr1220 发表于 2017-2-10 15:28
举个例子，如果搜索到了末节点，而且这条路径已经走完了，回溯法应该是连续回溯到初始节点再走另外一条路 ...
另一个是您提到的回溯到原点的问题，由于这个程序是设计成当chess_way等于64时就结束程序，所以之后的回溯操作我就没有关心了 还有一点是 程序的执行时间在3分钟左右，比之前我写的那个递归版本慢了快2分钟 还是很谢谢你刚才的回复 不然我短时间内根本不会注意到程序存在这样的bug
Jonin616 发表于 2017-2-10 19:13
另一个是您提到的回溯到原点的问题，由于这个程序是设计成当chess_way等于64时就结束程序，所以之后的 ...
所以回溯法还是应该用递归写，首先是程序比较简洁（30行代码就够了），可读性也强，效率的话，没有做过比较，如果按照你的说法，效率可能也是递归的高。
学习
厉害
学习下
n = 6
chess = [*n for i in range(n)]
start = (0, 0)
moves = [, , [-2, 1], [-2, -1], , , [-1, 2], [-1, -2]]
chess]] = 1
def dfs(loc, step):
if step == n*n:
for each in chess:
print(each)
return True
for each in moves:
x = loc + each
y = loc + each
if -1 < x < n and -1< y < n and chess == 0:
chess = step + 1
if dfs((x, y), step + 1):
return True
chess = 0
dfs(start, 1)
求教啊，思路应该跟你的思路非常接近，但是我的程序只能算n = 6的情况， n =8的情况就很长时间也计算不出来了，为什么吗呢？
WelanceLee 发表于 2017-6-14 18:42
求教啊，思路应该跟你的思路非常接近，但是我的程序只能算n = 6的情况， n =8的情况就很长时间也计算不出 ...
程序的逻辑应该是对的，但是执行效率不高。
其实我原本的程序效率也不高，差不多n=8的话，要1分多钟才出结果。
jerryxjr1220 发表于 2017-6-14 20:06
程序的逻辑应该是对的，但是执行效率不高。
其实我原本的程序效率也不高，差不多n=8的话，要1分多钟才出 ...
我的是10分钟也算不出来……