我有2个-看似对n皇后问题的解决方案。两者都产生完全相同的结果（我在网上都找到了），但是第二个花费的时间是第一个的两倍多。您能帮我解释一下，有什么区别？
from itertools import permutations
import time
punkt1 = time.time()
N=8
sol=0
cols = range(N)
for combo in permutations(cols):
if N==len(set(combo[i]+i for i in cols))==len(set(combo[i]-i for i in cols)):
sol += 1
print('Solution '+str(sol)+' : '+str(combo)+'\n')
#print("\n".join(' o ' * i + ' X ' + ' o ' * (N-i-1) for i in combo) + "\n\n\n\n")
punkt2 = time.time()
czas = punkt2 - punkt1
###################################
def queensproblem(rows, columns):
solutions = [[]]
for row in range(rows):
solutions = add_one_queen(row, columns, solutions)
return solutions
def add_one_queen(new_row, columns, prev_solutions):
return [solution + [new_column]
for solution in prev_solutions
for new_column in range(columns)
if no_conflict(new_row, new_column, solution)]
def no_conflict(new_row, new_column, solution):
return all(solution[row] != new_column and
solution[row] + row != new_column + new_row and
solution[row] - row != new_column - new_row
for row in range(new_row))
punkt3 = time.time()
i = 1
for solution in queensproblem(8, 8):
print('Solution', i,':', solution, '\n')
i = i + 1
punkt4 = time.time()
czas2 = punkt4 - punkt3
print ("Czas wykonania pierwszej metody:")
print (czas,'\n')
print ("Czas wykonania drugiej metody:")
print (czas2)
最佳答案
乍一看，您似乎是在说这些算法产生相同的结果，并且时间上的差异是恒定的，这在谈论算法时是无关紧要的。
但是，如果将N设为功能参数并检查N = 9或N = 10的时序，则会发现它们之间有很大的差异。在N = 11时，itertools.permutations版本花费了12分钟，而另一个花费了28秒。如果它们以不同的速度增长，这将成为算法问题。
所谓“排列组合”的函数实际上是在看每个可能的木板，因此您可以连续排列三个皇后区，但它仍然认为“我必须继续添加皇后区，看看是否可行”。 （这是用该符号表示的所有可能的面板。该符号本身消除了很多，但还不够。）
另一个功能是能够停止检查不良组合，从而立即消除许多不良候选项。查看N = 4的决策树打印输出，该打印输出是通过在皇后问题for循环中添加打印（行，解决方案）而生成的：
0 [[0], [1], [2], [3]]
1 [[0, 2], [0, 3], [1, 3], [2, 0], [3, 0], [3, 1]]
2 [[0, 3, 1], [1, 3, 0], [2, 0, 3], [3, 0, 2]]
3 [[1, 3, 0, 2], [2, 0, 3, 1]]
在逻辑的早期，它研究了[0，0]和[0，1]并简单地消除了它们。因此，它从来没有看过[0，0，0]或其他许多东西。它继续仅为通过早期检查的解决方案添加新的皇后区。由于甚至没有查看在no_conflit内部消除的所有子问题，因此还节省了大量时间，这是因为“ all”和“ and”的布尔布尔逻辑短路。
关于python - Python中n皇后拼图的2个解决方案之间的区别，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/42736150/