本文深入探讨n皇后问题中sosic和gu线性算法的实现细节，特别是其初始化阶段的碰撞检测机制。我们将分析原始`partial_collision`函数的效率瓶颈，并提出一种利用对角线计数数组进行o(1)时间复杂度的优化方案。通过重构关键函数，本教程旨在指导读者构建一个更高效、更符合算法设计初衷的n皇后问题求解器。
N皇后问题与Sosic和Gu算法概述
N皇后问题是一个经典的组合优化问题，目标是在N×N的棋盘上放置N个皇后，使得任意两个皇后都不能互相攻击。这意味着任何两个皇后都不能处于同一行、同一列或同一对角线上。Sosic和Gu算法提供了一种基于局部搜索的启发式方法来解决这一问题，其核心思想是通过迭代地调整皇后的位置来消除冲突。
该算法通常分为两个主要阶段：
初始化搜索 (initial_search)：尝试在棋盘上随机放置皇后，尽量减少初始冲突。这个阶段的目标是快速找到一个冲突较少的初始布局。最终搜索 (final_search 或 final_search_reduced)：在初始化布局的基础上，通过一系列交换操作，逐步消除所有冲突，直至找到一个有效的N皇后解。
为了高效地检测冲突，Sosic和Gu算法引入了对角线计数数组。这些数组能够以O(1)的时间复杂度检查特定位置是否存在对角线冲突，从而显著提升算法性能。
初始搜索阶段的碰撞检测优化
在initial_search阶段，算法尝试将皇后放置到棋盘上，并确保新放置的皇后不与之前已放置的皇后发生冲突。原始实现中的partial_collision(queens, i)函数用于检查第i列的皇后是否与前i-1列的皇后发生对角线冲突。然而，其实现方式存在效率问题：
def partial_collision(queens, i): # 此实现遍历了所有已放置的皇后，时间复杂度为O(i) return sum(1 for j in range(i) if (i - j) == abs(queens[i] - queens[j]))
这个函数通过迭代j从0到i-1来检查对角线冲突，其时间复杂度为O(i)。在initial_search阶段，当i逐渐增大时，partial_collision的调用将导致整体效率下降。Sosic和Gu算法论文中指出，碰撞检测应达到O(1)的时间复杂度。
为了实现O(1)的碰撞检测，我们需要充分利用算法中维护的对角线计数数组：neg_diagonal和pos_diagonal。
对角线计数数组的原理
负对角线 (neg_diagonal)：对于棋盘上任意一个位置(row, col)，其负对角线索引为row + col。所有处于同一负对角线上的位置，其row + col值相同。正对角线 (pos_diagonal)：对于棋盘上任意一个位置(row, col)，其正对角线索引为row – col + n – 1（其中n是棋盘大小，用于将索引映射到非负范围）。所有处于同一正对角线上的位置，其row – col值相同。
neg_diagonal[k]存储的是row + col = k的对角线上皇后的数量，pos_diagonal[k]存储的是row – col + n – 1 = k的对角线上皇后的数量。如果这些数组中的任何一个元素大于1，则表示对应的对角线上存在冲突。
替换partial_collision为O(1)检测
total_collisions(queens, i, neg_diagonal, pos_diagonal)函数已经利用了对角线数组实现了O(1)的冲突检测：
def total_collisions(queens, i, neg_diagonal, pos_diagonal): n = len(queens) # 检查第i列皇后所在位置的负对角线和正对角线上的皇后数量 # 减去2是因为皇后自己也会被计数一次 return neg_diagonal[i + queens[i]] + pos_diagonal[i - queens[i] + n - 1] - 2
这个函数返回的是第i列的皇后与其他皇后产生的对角线冲突总数。关键在于，即使在initial_search阶段只放置了部分皇后，neg_diagonal和pos_diagonal数组也只记录了当前已放置皇后的信息。因此，total_collisions函数可以完美地替代partial_collision，提供O(1)的局部冲突检测。
优化后的initial_search函数
通过将partial_collision替换为total_collisions，我们可以优化initial_search函数：
import randomdef initialize_diagonal_arrays(n): neg_diagonal = [0] * (2 * n - 1) pos_diagonal = [0] * (2 * n - 1) return neg_diagonal, pos_diagonaldef update_diagonal_arrays(queens, neg_diagonal, pos_diagonal): n = len(queens) # 清空数组 for i in range(len(neg_diagonal)): neg_diagonal[i] = 0 for i in range(len(pos_diagonal)): pos_diagonal[i] = 0 # 重新填充 for i in range(len(queens)): neg_diagonal[i + queens[i]] += 1 pos_diagonal[i - queens[i] + n - 1] += 1def swap(queens, a, b, neg_diagonal, pos_diagonal): n = len(queens) # 移除旧位置的计数 neg_diagonal[a + queens[a]] -= 1 pos_diagonal[a - queens[a] + n - 1] -= 1 neg_diagonal[b + queens[b]] -= 1 pos_diagonal[b - queens[b] + n - 1] -= 1 # 交换皇后位置 queens[a], queens[b] = queens[b], queens[a] # 添加新位置的计数 neg_diagonal[a + queens[a]] += 1 pos_diagonal[a - queens[a] + n - 1] += 1 neg_diagonal[b + queens[b]] += 1 pos_diagonal[b - queens[b] + n - 1] += 1def total_collisions(queens, i, neg_diagonal, pos_diagonal): n = len(queens) # 计算第i列皇后的对角线冲突数 # 如果该位置没有皇后，则应返回0。此处假设queens[i]是有效的列位置。 # 减去2是因为皇后自身在两个对角线数组中各被计数一次。 # 如果neg_diagonal[i + queens[i]] 或 pos_diagonal[i - queens[i] + n - 1] 为1， # 且没有其他皇后，则结果为 1 + 1 - 2 = 0，表示无冲突。 return neg_diagonal[i + queens[i]] + pos_diagonal[i - queens[i] + n - 1] - 2def initial_search_optimized(queens, nd, pd): n = len(queens) queens[:] = list(range(n)) # 初始设置为queens[i] = i，即(i,i) update_diagonal_arrays(queens, nd, pd) # 初始化对角线数组 j = 0 # 尝试放置皇后，避免冲突 for _ in range(int(3.08 * n)): # 循环次数 if j == n: break m = random.randint(j, n - 1) # 尝试交换皇后位置 swap(queens, j, m, nd, pd) # 使用total_collisions进行O(1)的冲突检测 if total_collisions(queens, j, nd, pd) == 0: j += 1 # 如果无冲突，则确定该皇后位置 else: # 如果有冲突，则撤销交换 swap(queens, j, m, nd, pd) # 放置剩余的皇后，允许冲突 for i in range(j, n): m = random.randint(i, n - 1) swap(queens, i, m, nd, pd) # 返回有冲突的皇后数量 return n - j
重要提示：
在initial_search中，queens[:] = list(range(n))这一步将皇后初始化为(0,0), (1,1), …, (n-1,n-1)，这本身就会有大量冲突。因此，在调用update_diagonal_arrays之后，total_collisions会反映这些初始冲突。swap函数在交换皇后位置的同时，必须同步更新neg_diagonal和pos_diagonal数组，以确保它们的计数始终准确反映当前棋盘状态。这是实现O(1)冲突检测的关键。update_diagonal_arrays在每次queen_search循环开始时调用，用于根据当前的queens布局重新计算对角线计数。在实际的initial_search内部，每次swap操作都会增量更新对角线数组，因此无需频繁调用update_diagonal_arrays。
优化board_collision函数
board_collision函数用于检查整个棋盘是否存在冲突。原始实现同样依赖于partial_collision，导致其效率低下：
def board_collision(queens): # 此实现仍为O(N^2) return sum(partial_collision(queens, i) for i in range(len(queens)))
通过利用对角线计数数组，我们可以将board_collision优化为O(N)甚至更低的时间复杂度（取决于对角线数组的遍历方式）。如果任何对角线上的皇后数量大于1，就意味着存在冲突。
def board_collision_optimized(queens, neg_diagonal, pos_diagonal): n = len(queens) # 检查负对角线是否有冲突 for count in neg_diagonal: if count > 1: return 1 # 存在冲突 # 检查正对角线是否有冲突 for count in pos_diagonal: if count > 1: return 1 # 存在冲突 return 0 # 无冲突
这个优化后的board_collision_optimized函数通过遍历对角线计数数组来检查是否存在任何对角线上的冲突。由于对角线数组的大小是2*n-1，这个函数的复杂度是O(N)，远优于原始的O(N^2)。
完整代码示例（优化后）
以下是整合了上述优化方案后的Sosic和Gu算法核心部分的示例代码：
import random# --- 辅助函数 ---def initialize_diagonal_arrays(n): """初始化对角线计数数组""" neg_diagonal = [0] * (2 * n - 1) pos_diagonal = [0] * (2 * n - 1) return neg_diagonal, pos_diagonaldef update_diagonal_arrays(queens, neg_diagonal, pos_diagonal): """根据当前皇后布局更新对角线计数数组""" n = len(queens) # 清空旧计数 for i in range(len(neg_diagonal)): neg_diagonal[i] = 0 for i in range(len(pos_diagonal)): pos_diagonal[i] = 0 # 填充新计数 for i in range(n): neg_diagonal[i + queens[i]] += 1 pos_diagonal[i - queens[i] + n - 1] += 1def swap(queens, a, b, neg_diagonal, pos_diagonal): """交换两个皇后位置，并同步更新对角线计数数组""" n = len(queens) # 减少旧位置的计数 neg_diagonal[a + queens[a]] -= 1 pos_diagonal[a - queens[a] + n - 1] -= 1 neg_diagonal[b + queens[b]] -= 1 pos_diagonal[b - queens[b] + n - 1] -= 1 # 交换皇后 queens[a], queens[b] = queens[b], queens[a] # 增加新位置的计数 neg_diagonal[a + queens[a]] += 1 pos_diagonal[a - queens[a] + n - 1] += 1 neg_diagonal[b + queens[b]] += 1 pos_diagonal[b - queens[b] + n - 1] += 1def total_collisions(queens, i, neg_diagonal, pos_diagonal): """ 计算第i列皇后的对角线冲突数。 时间复杂度O(1)。 """ n = len(queens) # 减去2是因为皇后自己也会被计数两次（在两个对角线数组中各一次） return neg_diagonal[i + queens[i]] + pos_diagonal[i - queens[i] + n - 1] - 2def board_collision_optimized(neg_diagonal, pos_diagonal): """ 检查整个棋盘是否存在任何对角线冲突。 时间复杂度O(N)。 """ for count in neg_diagonal: if count > 1: return 1 # 存在冲突 for count in pos_diagonal: if count > 1: return 1 # 存在冲突 return 0 # 无冲突# --- 算法核心函数 ---def initial_search(queens, nd, pd): """ Sosic和Gu算法的初始化搜索阶段。 尝试放置皇后，尽量减少初始冲突。 """ n = len(queens) queens[:] = list(range(n)) # 初始化皇后位置为(i, i) update_diagonal_arrays(queens, nd, pd) # 初始化对角线计数 j = 0 # 尝试放置皇后，避免冲突 for _ in range(int(3.08 * n)): if j == n: break m = random.randint(j, n - 1) swap(queens, j, m, nd, pd) # 使用total_collisions进行O(1)的冲突检测 if total_collisions(queens, j, nd, pd) == 0: j += 1 else: swap(queens, j, m, nd, pd) # 撤销交换 # 放置剩余的皇后，允许存在冲突 for i in range(j, n): m = random.randint(i, n - 1) swap(queens, i, m, nd, pd) return n - j # 返回有冲突的皇后数量def final_search(queens, k, nd, pd): """ Sosic和Gu算法的最终搜索阶段（适用于较大N）。 通过局部调整消除剩余冲突。 """ n = len(queens) it = 0 for i in range(n - k, n): # 只处理可能存在冲突的皇后 if total_collisions(queens, i, nd, pd) > 0: while it 0) or \ (total_collisions(queens, j, nd, pd) > 0) if b: swap(queens, i, j, nd, pd) # 撤销交换 it += 1 else: break # 冲突消除，跳出内循环def final_search_reduced(queens, k, nd, pd): """ Sosic和Gu算法的最终搜索阶段（适用于较小N）。 """ n = len(queens) for i in range(n - k, n): # 只处理可能存在冲突的皇后 if total_collisions(queens, i, nd, pd) > 0: for j in range(n): # 遍历所有可能的交换位置 swap(queens, i, j, nd, pd) # 检查交换后i和j位置的皇后是否仍有冲突 b = (total_collisions(queens, i, nd, pd) > 0) or \ (total_collisions(queens, j, nd, pd) > 0) if b: swap(queens, i, j, nd, pd) # 撤销交换 else: break # 冲突消除，跳出内循环def queen_search(queens): """N皇后问题主搜索函数""" n = len(queens) while True: nd, pd = initialize_diagonal_arrays(n) k = initial_search(queens, nd, pd) if n > 200: final_search(queens, k, nd, pd) else: final_search_reduced(queens, k, nd, pd) # 使用优化后的board_collision检查最终结果 if board_collision_optimized(nd, pd) == 0: break# 示例使用if __name__ == "__main__": N = 8 # 棋盘大小 queens_solution = [0] * N # 用于存储皇后在每一列的行位置 print(f"开始解决 {N} 皇后问题...") queen_search(queens_solution) print(f"{N} 皇后问题的一个解: {queens_solution}") # 验证解的正确性（可选） nd_final, pd_final = initialize_diagonal_arrays(N) update_diagonal_arrays(queens_solution, nd_final, pd_final) if board_collision_optimized(nd_final, pd_final) == 0: print("解验证通过：无冲突。") else: print("解验证失败：存在冲突！") # 打印棋盘 print("\n棋盘布局:") for row in range(N): line = ["." for _ in range(N)] line[queens_solution[row]] = "Q" print(" ".join(line))
注意事项与总结
对角线数组的精确维护：swap函数是算法中进行位置调整的核心。务必确保每次交换操作后，neg_diagonal和pos_diagonal数组能够同步且准确地更新。这是O(1)冲突检测的基础。update_diagonal_arrays的使用时机：在queen_search的每次外层循环开始时，重新初始化并更新对角线数组是必要的，因为initial_search可能会产生新的皇后布局。但在initial_search或final_search内部，每次swap操作都会增量更新数组，无需再次调用update_diagonal_arrays。total_collisions的语义：total_collisions(queens, i, …)返回的是第i列皇后与所有其他皇后（包括已放置的和未放置的，但对角线数组只记录已放置的）的对角线冲突数。当它返回0时，表示该皇后在当前布局下没有对角线冲突。board_collision_optimized的效率：通过遍历对角线计数数组，board_collision_optimized能够在O(N)的时间内判断整个棋盘是否存在冲突，这比原始的O(N^2)实现效率更高。
通过上述优化，N皇后问题Sosic和Gu算法的碰撞检测部分将达到理论上的O(1)复杂度，显著提升算法在处理大规模N值时的性能。这种利用辅助数据结构进行状态维护和快速查询的策略，在许多算法设计中都具有重要的指导意义。
以上就是N皇后问题Sosic和Gu线性算法的高效实现与碰撞检测优化的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1382676.html
微信扫一扫 
支付宝扫一扫 
