## 四、实验要求

### 1. 实验步骤

#### **N-后问题设计**

N-后问题的本质是在一个N×N的棋盘上，逐行放置皇后，并确保任何新放置的皇后不与已放置的皇后在同一列或同一对角线上。这是一个典型的组合搜索问题，非常适合用回溯法来探索解空间。

**1. 递归回溯法**

* **核心思想**：深度优先搜索解空间树。从第0行开始，尝试为当前行 `row` 的每一列 `col` 放置皇后。如果当前位置 `(row, col)` 安全，则将皇后放置于此，并递归地进入下一行 `row + 1` 进行决策。如果下一行的所有尝试都失败了，函数会自动返回，程序会继续尝试当前行 `row` 的下一列 `col + 1`，这就构成了“回溯”。

* **流程图**
    ```mermaid
    graph TD
        A("开始: solve(row=0)") --> B{"row == N?"};
        B -- 是 --> C["找到一个解, 存储并返回"];
        B -- 否 --> D("循环 col 从 0 到 N-1");
        D --> E{"位置(row, col)安全?"};
        E -- 是 --> F["放置皇后 queens[row] = col"];
        F --> G("递归调用 solve(row + 1)");
        G --> D;
        E -- 否 --> D;
        D -- 循环结束 --> H("返回上一层");
    ```

**2. 迭代回溯法**

* **核心思想**：用循环和自定义的状态变量来模拟递归调用的过程，从而避免使用系统调用栈。关键在于如何手动管理“前进”和“回溯”的逻辑。
* **状态管理**：使用一个变量 `row` 表示当前正在处理的行。当 `row` 增加时，表示向深层“递归”；当 `row` 减少时，表示“回溯”。回溯后，必须从上一行皇后**之前位置的下一列**开始继续搜索，这是迭代实现的核心。

* **流程图**
    ```mermaid
    graph TD
        A("开始, row=0") --> B{"while row >= 0"};
        B -- 是 --> C{"row == N?"};
        C -- 是 --> D["找到解, 存储"];
        D --> E("回溯: row--");
        C -- 否 --> F("寻找当前row的安全列col");
        F -- 从row+1或0开始 --> G{"找到安全列?"};
        G -- 是 --> H["放置皇后 queens[row]=col"];
        H --> I("前进: row++");
        I --> B;
        G -- 否 --> J("重置当前行: queens[row]=-1");
        J --> E;
        B -- 否 --> K("结束");
    ```

#### **单源最短路径问题设计**

* **算法思想理解**：分支限界法是一种在问题的解空间树上进行广度优先或最佳优先搜索的算法，通常用于求解优化问题。当应用于单源最短路径问题时，其“最佳优先”的搜索策略与著名的 **Dijkstra 算法** 完全一致。
* **核心策略**：算法维护一个从源点 `source` 到各个顶点的距离集合。它总是从“待考察”的顶点中，选择一个当前距离源点最近的顶点 `u` 进行扩展（分支）。然后，通过顶点 `u` 更新其所有邻接顶点 `v` 的距离（松弛操作）。如果到达 `v` 的新路径比已知路径更短，就更新它。这个过程不断重复，直到所有可达顶点都被考察完毕。
* **关键数据结构**：为了高效地实现“选择距离最近的顶点”，**优先队列（最小堆）** 是不二之选。

* **流程图**
    ```mermaid
    graph TD
        A("开始") --> B["初始化所有距离为∞, 源点为0"];
        B --> C["将 (0, source) 推入优先队列PQ"];
        C --> D{"while PQ不为空"};
        D -- 是 --> E["从PQ弹出距离最小的顶点 (d, u)"];
        E --> F{"d > 已记录的dist[u]?"};
        F -- 是旧数据 --> D;
        F -- 否 --> G("遍历u的所有邻居v");
        G --> H{"通过u到达v的距离 < 已记录的dist[v]?"};
        H -- 是 --> I("更新dist[v], 将新(dist, v)推入PQ");
        I --> G;
        H -- 否 --> G;
        G -- 循环结束 --> D;
        D -- 否 --> J("结束, 返回所有最短距离");
        
    ```
---

### 2. 调试过程及实验结果

#### **N-后问题**

![递归回溯](../assets/Lab04-N-Que-recur.png)

![迭代回溯](../assets/Lab04-N-Que-iter.png)

#### **单源最短路径问题**

**测试数据集**

| 测试名称 | 图结构 (邻接表) | 源点 | 目标与分析 |
| :--- | :--- | :--- | :--- |
| **测试1** | `{'A': [('B', 1), ('C', 4)], 'B': ..., 'C': ...}` | 'A' | 标准情况，验证基本功能 |
| **测试2** | `{'A': [('B', 10), ('C', 3)], 'C': [('B', 4)], ...}` | 'A' | 验证算法能否找到经过更多顶点的更短路径 (A->C->B 短于 A->B) |
| **测试3** | 包含孤立顶点 `4` | `0` | 验证算法能否正确处理不连通图的情况 |

![单源最短路: 分支限界法](../assets/Lab04-sssp.png)



---

### 3. 心得体会

通过本次实验，我对回溯法和分支限界法这两种核心算法思想有了更具体、更深入的认识。

**1. 遇到的问题及解决方法**
* **问题一：如何将N-后问题的递归思路转化为迭代？**
    * **遇到的问题**：递归的实现非常自然，但要转换成迭代，核心难点在于如何模拟“回溯”后，从上一个状态的“下一个选择”继续。简单地 `row--` 之后，如果内层循环还是从 `col=0` 开始，就会陷入死循环。
    * **解决方法**：我意识到必须记录每一行做出选择时的列号。在 `queens` 数组中，`queens[row]` 的值本身就记录了这一信息。因此，当从 `row+1` 回溯到 `row` 时，下一次列的循环必须从 `queens[row] + 1` 开始，这完美地模拟了递归函数返回后继续执行 `for` 循环的逻辑。

* **问题二：“分支限界法”与“Dijkstra”的关系是什么？**
    * **遇到的问题**：课本中提到用分支限界法解最短路径，但其描述与Dijkstra算法非常相似，这让我感到困惑。
    * **解决方法**：通过查阅资料和编码实践，我最终理解到，Dijkstra算法可以被看作是分支限界法在单源最短路径问题上的一个特例。分支限界法的核心是“扩展最有希望的节点”，在SSSP问题中，“最有希望”的节点就是“当前距离源点最近”的节点。优先队列恰好是实现这一“最佳优先”搜索策略的完美工具。想通了这一点，算法的设计就变得非常清晰了。

**2. 实验过程中的收获**
* **深化了对回溯法的理解**：亲手实现递归和迭代两种版本后，我对回溯法“选择-约束-递归-回溯”的循环有了本质的认识。迭代的实现过程让我更清晰地看到了算法在解空间树上深度优先搜索和剪枝的过程，以及系统调用栈在递归中扮演的角色。

* **掌握了算法思想的统一性**：将分支限界法应用到最短路径问题，让我看到不同算法范式之间的内在联系。与其死记硬背某个特定算法的步骤，不如理解其所属的更广泛的算法思想（如“最佳优先搜索”），这样在面对新问题时，就能更灵活地设计出解决方案。

* **数据结构的重要性**：本次实验再次印证了数据结构是算法的基石。无论是N-后问题中用一维数组巧妙表示二维棋盘状态，还是在分支限界法中利用优先队列（最小堆）将 $O(V^2)$ 的朴素搜索优化到 $O(E \log V)$，都体现了选择合适的数据结构对算法效率的决定性作用。

### 4. 附录

#### 4.1 N-后问题: 递归回溯法

```python
def solve_n_queens_recursive(n):
    """
    使用递归回溯解决N-后问题。

    """
    solutions = []
    # queens[row] = col 表示在第row行第col列放置了一个皇后
    queens = [-1] * n

    def is_safe(row, col):
        """
        检查在(row, col)位置放置皇后是否安全。
        只需检查当前行之前的所有行。
        """
        for r in range(row):
            # 检查是否在同一列
            if queens[r] == col:
                return False
            # 检查是否在同一对角线
            if abs(row - r) == abs(col - queens[r]):
                return False
        return True

    def solve(row):
        """
        递归地为从row行开始的棋盘布局寻找解。
        """
        # 基线条件：如果所有行都已成功放置皇后，则找到一个解
        if row == n:
            # 格式化解并存储
            solution = []
            for r in range(n):
                row_str = ['.'] * n
                row_str[queens[r]] = 'Q'
                solution.append("".join(row_str))
            solutions.append(solution)
            return

        # 尝试在当前行的每一列放置皇后
        for col in range(n):
            if is_safe(row, col):
                # 做出选择
                queens[row] = col
                # 进入下一行决策
                solve(row + 1)
                # 回溯在此实现中是隐式的，下一次循环会自动覆盖 queens[row]

    # 从第0行开始求解
    solve(0)
    return solutions

if __name__ == "__main__":
    # --- 测试 N=4 ---
    N4 = 4
    print(f"\n--- 测试 N = {N4} ---")
    solutions_4 = solve_n_queens_recursive(N4)
    print(f"共找到 {len(solutions_4)} 个解。")
    if solutions_4:
        print("其中一个解示例:")
        for row_str in solutions_4[0]:
            print(f"  {row_str}")

    # --- 测试 N=8 (标准测试) ---
    N8 = 8
    print(f"\n--- 测试 N = {N8} ---")
    solutions_8 = solve_n_queens_recursive(N8)
    print(f"共找到 {len(solutions_8)} 个解。")
```

#### 4.2 N-后问题: 迭代回溯法

```python
def solve_n_queens_iterative(n):
    """
    使用迭代回溯（非递归）解决N-后问题。
    """
    solutions = []
    # queens[row] = col 表示在第row行第col列放置了一个皇后
    queens = [-1] * n
    
    def is_safe(row, col):
        """
        检查在(row, col)位置放置皇后是否安全。
        """
        for r in range(row):
            if queens[r] == col or abs(row - r) == abs(col - queens[r]):
                return False
        return True
        
    row = 0
    while row >= 0:
        # 如果成功为所有行都找到了位置，说明找到一个完整解
        if row == n:
            # 格式化解并存储
            solution = []
            for r in range(n):
                row_str = ['.'] * n
                row_str[queens[r]] = 'Q'
                solution.append("".join(row_str))
            solutions.append(solution)
            # 回溯到上一行，继续寻找下一个可能的解
            row -= 1
            # continue关键字可以省略，因为循环会自然地继续
        
        # 为当前行寻找一个安全的位置
        # col的起始位置是关键：如果是新进入的行，从0开始；如果是回溯回来的行，从上一个位置的下一个开始
        start_col = queens[row] + 1 if queens[row] != -1 else 0
        
        found_safe_pos = False
        for col in range(start_col, n):
            if is_safe(row, col):
                # 做出选择
                queens[row] = col
                # 成功，移动到下一行
                row += 1
                found_safe_pos = True
                break # 找到了当前行的位置，跳出列循环，进入下一行
        
        # 如果当前行的所有列都尝试完毕，仍未找到安全位置
        if not found_safe_pos:
            queens[row] = -1 # 重置当前行的选择
            row -= 1       # 回溯到上一行

    return solutions


if __name__ == "__main__":
    # --- 测试 N=4 ---
    N4 = 4
    print(f"\n--- 测试 N = {N4} ---")
    solutions_4 = solve_n_queens_iterative(N4)
    print(f"共找到 {len(solutions_4)} 个解。")
    if solutions_4:
        print("其中一个解示例:")
        for row_str in solutions_4[0]:
            print(f"  {row_str}")

    # --- 测试 N=8 (标准测试) ---
    N8 = 8
    print(f"\n--- 测试 N = {N8} ---")
    solutions_8 = solve_n_queens_iterative(N8)
    print(f"共找到 {len(solutions_8)} 个解。")
```

#### 4.3 单源最短路径: 分支限界法

```python
import heapq

def branch_and_bound_sssp(graph, source):
    """
    使用分支限界法（Dijkstra算法）解决单源最短路径问题。
    """
    # 初始化距离数组，所有顶点距离为无穷大，源点为0
    distances = {vertex: float('inf') for vertex in graph}
    if source not in distances:
        raise KeyError(f"源点 {source} 不在图中！")
    distances[source] = 0
    
    # 优先队列，存储 (距离, 顶点)，距离越小优先级越高
    priority_queue = [(0, source)]
    
    while priority_queue:
        # 弹出当前距离最小的顶点（分支限界法的“限界”选择）
        current_distance, current_vertex = heapq.heappop(priority_queue)
        
        # 如果弹出的距离比记录的距离大，说明是旧的、较长的路径，跳过
        if current_distance > distances[current_vertex]:
            continue
            
        # 遍历当前顶点的所有邻居（分支过程）
        for neighbor, weight in graph.get(current_vertex, []):
            distance = current_distance + weight
            
            # 如果通过当前顶点到达邻居的路径更短（松弛操作）
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                # 将更新后的邻居加入优先队列
                heapq.heappush(priority_queue, (distance, neighbor))
                    
    return distances

if __name__ == "__main__":
    # --- 测试数据 1: 标准情况 ---
    graph1 = {
        'A': [('B', 1), ('C', 4)],
        'B': [('A', 1), ('C', 2), ('D', 5)],
        'C': [('A', 4), ('B', 2), ('D', 1)],
        'D': [('B', 5), ('C', 1)]
    }
    source1 = 'A'
    print(f"\n--- 测试1 ---")
    print(f"图结构: {graph1}")
    print(f"源点: {source1}")
    shortest_paths1 = branch_and_bound_sssp(graph1, source1)
    print(f"结果: 从'{source1}'出发的最短路径为 -> {shortest_paths1}")

    # --- 测试数据 2: 包含更长但权重更低的路径 ---
    graph2 = {
        'A': [('B', 10), ('C', 3)],
        'B': [('D', 2)],
        'C': [('B', 4), ('D', 8), ('E', 2)],
        'D': [('E', 7)],
        'E': []
    }
    source2 = 'A'
    print(f"\n--- 测试2 ---")
    print(f"图结构: {graph2}")
    print(f"源点: {source2}")
    shortest_paths2 = branch_and_bound_sssp(graph2, source2)
    print(f"结果: 从'{source2}'出发的最短路径为 -> {shortest_paths2}")
    print("分析: 到达'B'的最短路径是 A->C->B (3+4=7)，而非直接的 A->B (10)。")

    # --- 测试数据 3: 包含不连通的顶点 ---
    # 顶点4无法从0到达
    graph3_data = {
        0: [(1, 4), (2, 1)],
        1: [(3, 1)],
        2: [(1, 2), (3, 5)],
        3: [],
        4: [(0, 3)] 
    }
    # 确保图的定义中包含所有顶点，即使它们没有出边
    all_vertices = {0, 1, 2, 3, 4}
    graph3 = {v: graph3_data.get(v, []) for v in all_vertices}
    source3 = 0
    print(f"\n--- 测试3 ---")
    print(f"图结构: {graph3}")
    print(f"源点: {source3}")
    shortest_paths3 = branch_and_bound_sssp(graph3, source3)
    print(f"结果: 从'{source3}'出发的最短路径为 -> {shortest_paths3}")
    print("分析: 顶点4无法从源点0到达，其距离保持为无穷大(inf)。")
```