面向Brass Birmingham游戏AI的带约束最少建边路径求解问询

问题核心 #

需要在无向无权图中，找到从源节点到任意目标节点的连通方案，最小化需要新建的边数量，同时满足严格的边建造合法性约束。

约束拆解 #

1. 已建边规则：已建边（自身或其他玩家建造）可直接使用，且不可重复建造；连通方案可利用这些已建边的连通分量，无需额外建造。
2. 新建边合法性：
   • 初始合法边：边的一端属于自身拥有presence（已建有产业）的节点集合
   • 动态解锁边：边邻接自身已建造的边（随建造过程逐步解锁新的可建边）

相关技术术语 #

• 斯坦纳树问题（Steiner Tree Problem）：你的推测准确，该问题是斯坦纳树的变体，核心目标都是通过最少的边连接指定节点集，但增加了边的建造可达性约束（动态解锁规则），可检索关键词：带增量建造约束的最小斯坦纳树、动态可达边下的最小连通问题。
• 增量式图生成：对应动态解锁可建边的规则，每次操作会扩展可操作的边集合，属于这类问题的范畴。
• 状态空间搜索+剪枝：是解决这类带约束的最优路径问题的通用框架，结合优先队列可保证找到最优解。
• 并查集（Union-Find）：用于高效维护连通分量，减少状态表示的复杂度。

可行算法思路 #

1. 预处理阶段 #

• 用并查集标记所有已建边（自身+其他玩家）构成的连通分量，这些分量可视为无需额外建造的“连通块”。
• 筛选初始合法可建边：所有未建边中，一端属于自身presence节点集合的边。

2. 状态空间搜索（优先队列实现） #

• 状态表示：每个状态包含：当前已建造的边集合对应的连通分量（用并查集存储）、当前已解锁的可建边集合、已新建的边数量。
• 搜索策略：
  • 使用优先队列（按已新建边数量升序排序），保证首次找到的满足条件的状态就是最小边数的最优解。
  • 每次从队列中取出边数最少的状态，遍历当前所有合法可建边：
    1. 建造该边，更新并查集的连通分量。
    2. 解锁新的合法边：所有与该边邻接的未建边（未被其他玩家建造）。
    3. 检查源节点所在的连通分量是否包含任意目标节点，若是则返回当前边数作为最优解。
    4. 将新状态加入队列（需剪枝：若已有相同连通分量且边数更少的状态存在，则跳过）。

3. 剪枝优化 #

• 若当前状态的已建边数大于已找到的最优解，直接丢弃。
• 对于相同的连通分量状态，只保留边数最少的版本，避免重复搜索。

示例验证 #

针对题目中的场景：

• 初始合法可建边包括S-A（A为presence节点）、C-D（假设其满足初始合法条件）。
• 优先搜索边数为2的状态：
  • 建造S-A后，解锁A-B；再建造A-B，源节点S与目标节点T2所在的已建边连通分量合并，满足条件。
  • 建造C-D后，解锁D-T3；再建造D-T3，源节点S与目标节点T3连通，满足条件。
• 而S-A与D-T3的组合中，D-T3既不满足初始合法条件，建造S-A后也不与该边邻接，因此不会被纳入合法扩展路径。

内容的提问来源于stack exchange，提问作者Pwnosaurus