algorithm - 求所有节点到一个节点的最短指令串的长度

Question

我们有一组连接成一个圆圈的节点，从一个节点到另一个节点有一个额外的单向连接。指令集由 F(顺时针方向走一个节点)、B(逆时针方向走一个节点)和 P(通过一个节点)组成-方式连接。

每个节点都有一个单向连接到一个节点(可以是它自己)。每个连接都可以在与之前节点的连接相同的节点上进行，或者更远(节点和连接另一侧的节点顺序相同)。我需要找到可以移动到第一个节点的最短指令集的长度，无论起始节点是什么。

我已经尝试寻找以连接到自身的节点结束的连接链，因为它是一切都应该收敛的地方，但在第一次收敛之后我还没有找到任何优化的方法来确定到下一个的最短路径“最佳”收敛。我在互联网上没有找到任何关于此的信息，而且我缺乏想法。我认为这背后有一个数学定理，但我找不到。

我已经看过最小生成树 (Find the minimal common path from any nodes to one node)，但这些不适合，因为我有一套说明。

编辑:一个例子。

假设我们有以下数据:0 1 0 0(这意味着第一个节点的连接前进 0 个节点，第二个节点前进 1 个节点，依此类推)。这可以这样画(我省略了每个节点之间的链接):

o--o
|  | <------------ Those are "dead" nodes
|  V
o--1     2
         |
         V    <--- This is a "convergence chain"
o--4     3--o
|  ^     ^  |
|  |     |  |
o--o     o--o

在这里，解决方案是PBPBPFF(或PBPBPBB)。这里我们以收敛链为手段对它们进行分组，然后将它们转移到第一个节点。

Answer 1

假设圆的长度为 N。在输入中，我们还有一个数组 C[N]。对一个位置 P 有 3 种可能的操作:

a) p = (p - 1) % N
b) p = (p + 1) % N
c) p = (p + C[p]) % N

让我们试着分解一下这个问题。首先，让我们尝试找到一条链，将位置 P、Q 带到相同的位置 R。

我们很快就会发现，让两个位置彼此“更近”的步骤不会超过 O(N) 步。如果我们执行 N 步并且两个位置仍然保持相同的距离，我们应该使用简单的旋转，最多需要 N/2 步。从这个观察来看，如果可能的话，一个简单的 BFS 在 O(N^2) 中找到一个解决方案。如果在 N^2 步中找不到解决方案，则该解决方案不存在。现在，使用这个链，移动所有输入位置，选择另外两个并为它们找到解决方案。最后，我们得到一个单一的位置，将其转​​换为初始位置是微不足道的。因此，如果问题有任何解决方案，该算法将在

O(
   N - n positions 
   * 
   (N^2 - merge two positions to one
    + 
    N * N^2 - recalculate the positions with chain we've just found
   )
 )

，最多 N^3 个命令(每个应用 N 次)。

现在，我们可以简单地对所有可能组合的图进行 BFS。

从 ("", [0..n]) 开始，我们可以遍历队列并根据我们的命令推送新的三个项目(如果尚未找到位置):

(commands, [p1, p2, ... pn]) ->
    (commands + "F", [(p1 + 1) % N, ... (pn + 1) % N])
    (commands + "B", [(p1 - 1) % N, ... (pn - 1) % N])
    (commands + "P", [(p1 + C[p1]) % N, ... (pn + C[pn]) % N])

我们会在向量中填满零或执行了足够多的步骤以致无法找到解决方案时终止。边界可能会得到改善，但应该清楚我提到的这些是有效的。