Burkifa23/ids-visualizer

# 迭代加深搜索 (IDS) 可视化工具 本文档详细介绍了**迭代加深搜索 (IDS)** 的技术原理，该算法已在 **`ids-visualizer.html`** 中实现，用于解决加纳路线查找问题。 ## 什么是迭代加深搜索？ **迭代加深搜索 (IDS)** 是一种无信息搜索策略，它结合了**深度优先搜索 (DFS)** 和**广度优先搜索 (BFS)** 的优点： 1. **类似 DFS 的空间效率**：它运行深度受限搜索 (DLS)，使用栈结构，使内存消耗相对于深度保持线性。 2. **类似 BFS 的完备性与最优性**：通过系统地增加深度限制 ($L$)（即 $0, 1, 2, \dots$），它可以保证首先找到最浅的目标节点（边数最少），这使其在无权重步长成本下具备完备性和最优性。 ## 算法分步运行机制 在每次迭代中，算法会从根节点开始，以当前限制 $L$ 执行一次全新的深度受限搜索： 1. **初始化限制**：从深度限制 $L = 0$ 开始。 2. **运行深度受限搜索 (DLS)**： * 使用 DFS 探索状态空间。 * 如果节点深度等于 $L$，**则不扩展其子节点**（这是一个 `⊘ CUTOFF` 事件）。 * 如果找到目标，则终止并返回路径。 3. **分析截断**： * 如果 DLS 结束但未找到目标： * 如果至少有一个节点因达到深度限制而被剪枝（发生了截断），则将限制增加到 $L + 1$ 并从头重新开始 DLS。 * 如果未发生截断，说明整个图都已被搜索，且不存在解决方案（失败）。 ## 使用 IDS 可视化加纳公路网 在可视化工具中，您可以选择一个**起始城市**（例如 **Tamale**）和一个**目的地城市**（例如 **Korle Bu**）。 以下是分步执行的过程： * **$L = 0$**：DLS 从 **Tamale** 开始。由于深度 ($0$) 等于限制 ($0$)，Tamale 立即触发了截断。DLS 结束。 * **$L = 1$**：DLS 从 **Tamale** 重新开始，并扩展其邻居：**Wa, Bolgatanga, Yendi, Kintampo, Techiman**（深度为 1）。由于深度 ($1$) 等于限制 ($1$)，所有这些节点都触发了截断。DLS 结束。 * **$L = 2$**：DLS 重新开始并扩展 Tamale $\to$ Wa $\to$ Wa 的邻居（深度为 2 的 **Bolgatanga, Sunyani**，发生截断）$\to$ Tamale 的其他邻居。此过程持续进行，直到搜索空间达到深度 2。 * **$L = \dots$**：每次迭代时深度限制都会增加，直到搜索路径到达目的地城市。 ## 复杂度分析 ### 1. 时间复杂度 由于 IDS 会重复对上层节点进行 DLS 探索，它似乎浪费了对节点的重复评估。然而，在分支因子相对较高的树结构中，底层节点的数量主导了总节点的数量。 时间复杂度为： \[O(b^d)\] 其中： * $b$：平均分支因子（每个城市的公路连接数，在加纳约为 $3$ 到 $5$）。 * $d$：最浅解的深度。 重新访问节点带来的额外开销比例非常低： \[\frac{(d+1) \cdot b^0 + d \cdot b^1 + (d-1) \cdot b^2 + \dots + 1 \cdot b^d}{b^0 + b^1 + b^2 + \dots + b^d} \approx \frac{b}{b - 1}\] 对于分支因子 $b = 3$ 的情况，其开销仅比标准 DFS 多约 $50\%$，这使得它非常具有实用价值。 ### 2. 空间复杂度 由于它在 DLS 期间使用深度优先的栈结构，最大内存使用量被限制在活动路径分支及其兄弟节点上： \[O(b \cdot d)\] 与空间复杂度为 $O(b^d)$ 的 BFS 相比，这是一个巨大的改进。 ## 🎨 可视化状态系统 可视化工具实时显示 IDS 的活动执行状态： * 🔘 **板岩灰 (`#cbd5e1`)** — 未访问的城市。 * 🟡 **琥珀金 (`#d97706`)** — 当前活动的 DFS 搜索分支。 * 🔴 **深红色 (`#ef4444`)** — 限制截断节点（位于最大深度 $L$ 且搜索被剪枝的节点）。 * 🟢 **翠绿色 (`#10b981`)** — 以最少步数解析出的最终路径。 * **执行日志** — 实时记录 DFS 的出栈、扩展、截断限制和重新开始过程。

标签：前端工具, 后端开发, 图论, 多模态安全, 寻路算法, 搜索算法, 数据可视化, 算法可视化