N皇后问题Sosic和Gu线性算法的高效实现与碰撞检测优化-Python教程-PHP中文网

N皇后问题Sosic和Gu线性算法的高效实现与碰撞检测优化

本文深入探讨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)的局部冲突检测。

AVCLabs

AI移除视频背景，100%自动和免费

268

查看详情

优化后的initial_search函数

通过将partial_collision替换为total_collisions，我们可以优化initial_search函数：

import random

def initialize_diagonal_arrays(n):
    neg_diagonal = [0] * (2 * n - 1)
    pos_diagonal = [0] * (2 * n - 1)
    return neg_diagonal, pos_diagonal

def 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] += 1

def 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] += 1

def 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] - 2

def 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_diagonal

def 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] += 1

def 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] += 1

def 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] - 2

def 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 < 7000: # 限制迭代次数
                j = random.randint(0, n - 1)
                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) # 撤销交换
                    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线性算法的高效实现与碰撞检测优化的详细内容，更多请关注php中文网其它相关文章！