具有可变边可用性和其他约束的最短路径问题

Question

我正在尝试制定一种算法，该算法将由 AI 代理用于名为 Brass 的棋盘游戏。

棋盘状态由节点（“城市”）和边的无向和未加权图表示。我有一个源节点和一组可能的目标节点。我的目标是找到一条从源节点到任何一个目标节点的路径。然而，有一些并发症：

图中的每条边都可以被认为处于“建成”或“未建成”状态。边缘可以由我或其他玩家建造。一旦边缘由一个玩家建造，其他玩家就无法建造。我想沿着“构建”边（由任何玩家构建）找到从源到目标的路径，该路径需要构建最少数量的新边。这可能意味着我的解决方案涉及构建两条或更多条彼此不相邻的边，因为它可能涉及连接图中已经由先前“构建”的边连接的各个组件。

还有一个转折点：我不允许“构建”网络中的每条边。如果它的一个端节点位于我“存在”的一组预定节点中（从主题上讲，这些是我之前建立工业的城市），或者如果该边缘与另一个边缘相邻，我只能建立边缘我建了。这意味着一些边缘只有在构建其他边缘时才有资格由我构建。

所以我的问题是：什么算法可以让我找到最少数量的必须构建的边，这些边将通过构建的边将我的源连接到我的任何一个目标。

即使您不知道完整的算法，我也非常希望知道是否有任何术语或词来描述此类问题，这可能会帮助我搜索现有的算法。例如，我认为这个问题可能与 Steiner Tree 问题有些相关，但是围绕哪些边可以“构建”的约束似乎有些不同。

考虑以下示例。我的源节点标记为“S”。我的三个目标节点是“T1”、“T2”和“T3”。灰色边是“未构建”的边。一个紫色的边缘被构建，但是由其他玩家之一构建的。绿色边缘是我构建的边缘。绿色节点（A 和 T1）是我“在场”的节点。

本例中的两个最优解如下：

• 边缘

  S-A

  和边缘

  A-B

  。此解决方案通过两个构建将我的源连接到 T2。请注意，这两条边从一开始就是合法构建，因为节点 A 在我之前已经建立“存在”的节点集中。
• 边缘

  C-D

  和边缘

  D-T3

  。此解决方案通过两个构建将我的源连接到 T3。请注意，一开始，边缘 D-T3 不是合法构建，但是一旦构建了 C-D，D-T3 就变得合法了。

此外，

S-A

和

D-T3

是not合法的解决方案，因为边缘

D-T3

对我来说永远不会合法地构建（它不与我的边缘之一或我拥有的节点之一相邻“存在”）