为什么偶数 N 比奇数 N 花费的时间更长?
Why do the Even Ns take longer than the Odd Ns?
我这里有一些代码可以解决 python 中使用回溯的 n 皇后问题。当我 运行 它时,赔率总是比偶数花费的时间少得多。当 n 达到 20+ 左右时,这一点尤其明显。有谁知道这是为什么?
import time
global N
N = int(input("Enter N: "))
def display_solution(board):
print('\n'.join(['\t'.join([str(cell) for cell in row]) for row in
board]))
def safe(board, row, col):
for i in range(col):
if board[row][i] == 1:
return False
for i, j in zip(range(row, -1, -1), range(col, -1, -1)):
if board[i][j] == 1:
return False
for i, j in zip(range(row, N, 1), range(col, -1, -1)):
if board[i][j] == 1:
return False
return True
def solve_help(board, col):
if col >= N:
return True
for i in range(N):
if safe(board, i, col):
board[i][col] = 1
if solve_help(board, col + 1) is True:
return True
board[i][col] = 0
return False
def solve():
board = [[0 for x in range(N)] for y in range(N)]
if solve_help(board, 0) is False:
print("Solution does not exist")
return False
display_solution(board)
return True
start = time.clock()
solve()
end = time.clock()
print(N, "\t", end-start)
我假设这一定与赔率和偶数的对角线不同有关。我也不确定这是针对此问题的所有回溯算法的问题,还是仅针对此特定代码。无论哪种方式,感谢您的帮助。
当第一列中的其中一列发生回溯并且必须尝试下一行时,该算法会花费相当多的时间。将奇数 N 板与 N-1 板进行比较确实表明,偶数板的解决方案通常需要进行更多此类 backtracking/try-next 处理。例如,N=19 的解决方案的左上角如下所示:
1 0 0 0 0
0 0 0 1 0
0 1 0 0 0
0 0 0 0 1*
0 0 1 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
前五列的这5个皇后很快就找到了,因为它们是第一个不与前面的皇后发生碰撞的。显然可以放置其他皇后而不必重新考虑这前五个皇后。
对于 N=18,解决方案的同一角如下所示:
1 0 0 0 0
0 0 0 1 0
0 1 0 0 0
0 0 0 0 0-
0 0 1 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 1*
注意标有减号的位置。这个看起来很有前途(因为它是 19 板):它的调查需要相当长的时间才能得出其他皇后不能正确放置的结论。这种早期的失败成本。
因此19板的解比18板的解快
请注意,27 的解决方案比 26 的解决方案花费的时间略长,尽管这并不重要:看起来时间复杂度是 O(2n),所以比较不同板尺寸的时间最好在对数 Y 轴上完成:
"work"表示函数safe
被执行的次数
这个算法是否总是需要相对更多的时间用于偶数板(与 N+1 板所需的时间相比)是不清楚,但对于这几个棋盘尺寸,它似乎与该算法自然形成的从左上角开始的骑士跳跃有关。请注意此模式如何完美适用于尺寸为 5 和 7 的棋盘:下一个皇后可以坐下而不会干扰先前定位的皇后的第一个位置是 always 解决方案的一部分。而对于尺寸为 4 和 6 的棋盘,甚至 任何 的解决方案都没有一个角落有皇后,这是该算法的起点。
备选方案
从程序员的角度来看这个问题,有一种补救方法可以使差异(平均)消失:以不同(甚至随机)的顺序选择列。事实证明,采用正常顺序是获得解决方案的效率较低的方法之一。
换档选择
这个算法的一个简单转变,你不考虑前两行,除非所有其他行都失败了,已经大大改变了统计数据:
在 solve_help
中更改为:
for i in range(N):
至:
for i in range(N):
i = (i + 2) % N
查看现在平均性能如何提高:log(work)/n 的所有度量均低于 1,n=6 除外。而且:现在更频繁地查看 N 的奇数值。
随机选择
for i in random.sample(range(N), N):
下面是这样一个随机 运行 的结果:
比原来的顺序好多了!当然,你偶尔会得到一个糟糕的统计数据,......因为它是随机的。但平均而言,它的表现(好得多)。
非随机顺序的其他方式可能包括 col
和 N//2
具有不同的系数,例如 i = (i + col*2 + N//2) % N
,...等。但请参阅下面的最后评论。
其他备注
我将应用以下优化:跟踪哪些行、前向“对角线”和后向“对角线”已经被占用。您可以为此使用列表或集合。请注意,如果两个单元格的坐标之和相等,则它们位于同一前向对角线中。向后对角线上的单元格的共同点是它们的坐标差相等。这样您就不必每次都在这些行中扫描“1”。
此外,board
可能只是一个列号列表。没有必要存储所有这些零。保留它仅供展示。
最后,有一些简单的方法可以在线性时间内得到解决方案。参见 Wikipedia。
我这里有一些代码可以解决 python 中使用回溯的 n 皇后问题。当我 运行 它时,赔率总是比偶数花费的时间少得多。当 n 达到 20+ 左右时,这一点尤其明显。有谁知道这是为什么?
import time
global N
N = int(input("Enter N: "))
def display_solution(board):
print('\n'.join(['\t'.join([str(cell) for cell in row]) for row in
board]))
def safe(board, row, col):
for i in range(col):
if board[row][i] == 1:
return False
for i, j in zip(range(row, -1, -1), range(col, -1, -1)):
if board[i][j] == 1:
return False
for i, j in zip(range(row, N, 1), range(col, -1, -1)):
if board[i][j] == 1:
return False
return True
def solve_help(board, col):
if col >= N:
return True
for i in range(N):
if safe(board, i, col):
board[i][col] = 1
if solve_help(board, col + 1) is True:
return True
board[i][col] = 0
return False
def solve():
board = [[0 for x in range(N)] for y in range(N)]
if solve_help(board, 0) is False:
print("Solution does not exist")
return False
display_solution(board)
return True
start = time.clock()
solve()
end = time.clock()
print(N, "\t", end-start)
我假设这一定与赔率和偶数的对角线不同有关。我也不确定这是针对此问题的所有回溯算法的问题,还是仅针对此特定代码。无论哪种方式,感谢您的帮助。
当第一列中的其中一列发生回溯并且必须尝试下一行时,该算法会花费相当多的时间。将奇数 N 板与 N-1 板进行比较确实表明,偶数板的解决方案通常需要进行更多此类 backtracking/try-next 处理。例如,N=19 的解决方案的左上角如下所示:
1 0 0 0 0
0 0 0 1 0
0 1 0 0 0
0 0 0 0 1*
0 0 1 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
前五列的这5个皇后很快就找到了,因为它们是第一个不与前面的皇后发生碰撞的。显然可以放置其他皇后而不必重新考虑这前五个皇后。
对于 N=18,解决方案的同一角如下所示:
1 0 0 0 0
0 0 0 1 0
0 1 0 0 0
0 0 0 0 0-
0 0 1 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 1*
注意标有减号的位置。这个看起来很有前途(因为它是 19 板):它的调查需要相当长的时间才能得出其他皇后不能正确放置的结论。这种早期的失败成本。
因此19板的解比18板的解快
请注意,27 的解决方案比 26 的解决方案花费的时间略长,尽管这并不重要:看起来时间复杂度是 O(2n),所以比较不同板尺寸的时间最好在对数 Y 轴上完成:
"work"表示函数safe
被执行的次数
这个算法是否总是需要相对更多的时间用于偶数板(与 N+1 板所需的时间相比)是不清楚,但对于这几个棋盘尺寸,它似乎与该算法自然形成的从左上角开始的骑士跳跃有关。请注意此模式如何完美适用于尺寸为 5 和 7 的棋盘:下一个皇后可以坐下而不会干扰先前定位的皇后的第一个位置是 always 解决方案的一部分。而对于尺寸为 4 和 6 的棋盘,甚至 任何 的解决方案都没有一个角落有皇后,这是该算法的起点。
备选方案
从程序员的角度来看这个问题,有一种补救方法可以使差异(平均)消失:以不同(甚至随机)的顺序选择列。事实证明,采用正常顺序是获得解决方案的效率较低的方法之一。
换档选择
这个算法的一个简单转变,你不考虑前两行,除非所有其他行都失败了,已经大大改变了统计数据:
在 solve_help
中更改为:
for i in range(N):
至:
for i in range(N):
i = (i + 2) % N
查看现在平均性能如何提高:log(work)/n 的所有度量均低于 1,n=6 除外。而且:现在更频繁地查看 N 的奇数值。
随机选择
for i in random.sample(range(N), N):
下面是这样一个随机 运行 的结果:
比原来的顺序好多了!当然,你偶尔会得到一个糟糕的统计数据,......因为它是随机的。但平均而言,它的表现(好得多)。
非随机顺序的其他方式可能包括 col
和 N//2
具有不同的系数,例如 i = (i + col*2 + N//2) % N
,...等。但请参阅下面的最后评论。
其他备注
我将应用以下优化:跟踪哪些行、前向“对角线”和后向“对角线”已经被占用。您可以为此使用列表或集合。请注意,如果两个单元格的坐标之和相等,则它们位于同一前向对角线中。向后对角线上的单元格的共同点是它们的坐标差相等。这样您就不必每次都在这些行中扫描“1”。
此外,board
可能只是一个列号列表。没有必要存储所有这些零。保留它仅供展示。
最后,有一些简单的方法可以在线性时间内得到解决方案。参见 Wikipedia。