algorithm - 是否存在仅通过每种颜色一次的路径？

Question

我有一个有向彩色图(每个节点都有一种颜色)，我想查找是否存在从节点 A 到节点 B 的路径，使得该路径最多一次通过每种颜色。

我认为这个问题可以用网络流来表述。如果节点重复，可以以某种方式对相同颜色的节点施加惩罚，使流为 0 或无穷大。

谢谢!

Answer 1

这是 NP-hard 通过从“禁止对路径”问题的特殊情况减少，其中所有禁止对都需要不相交。只需为每个禁止对分配一些颜色。 “带禁止对的路径”是一个众所周知的 NP 难问题(即使在不相交的对的情况下它仍然是 NP 难问题)。在 Garey 和 Johnson 的书中它有标识符“GT54”。

但如果非唯一颜色的数量 ( k) 是一个小常数，您可以应用时间复杂度为 O(|E| * 2 ^2*k) 的改进 BFS 算法。

这里我解释一下这个BFS算法(从简化版开始):

路径访问过的所有节点的颜色应该被编码成位集，例如，如果我们有 3 种可用颜色(红色、绿色、蓝色)和访问绿色节点的路径，则编码为 010 ;这条路径也访问了red节点后，编码为011 .路径颜色与最后访问的节点一起存储在 BFS 队列中。

每个节点都应该为每种颜色组合存储一些“已访问”标志。假设具有三种颜色的示例，每个未访问的节点将存储 8 个具有“false”值的 bool 值。使用红色/绿色路径访问该节点后，其“已访问”标志应更改为以下内容:

index.bool  index.dec  visited_flag
       000          0         false
       001          1         false
       010          2         false
       011          3          true
       100          4         false
       101          5         false
       110          6         false
       111          7         false

如果算法在处理具有相同颜色组合的路径时遇到相同的节点，它应该忽略它，因为“真”访问标志。

BFS算法主循环的伪代码可以重写为:

 while Q is not empty:

     (u, c) = Q.dequeue()

     for each node n that is adjacent to u:
         if (c & n.color) == 0 && n.visited[c] == false:
             n.visited[c] = true
             Q.enqueue((n, c | n.color))

算法像往常一样终止:到达目的地(路径存在)或 BFS 队列变空(路径不存在)。

该算法的最坏情况时间复杂度为 O(|E| * 2 ^k)。它仍然在做很多多余的工作。由于在 BFS 算法中，较短(且色彩较少)的路径比较长的路径更早被认为，因此很可能首先使用红色路径访问某个节点，然后使用绿色路径，然后使用红色/绿色路径。在这种情况下，处理这条红/绿路径不会带来任何改善。这意味着我们可以通过在处理绿色路径时将红色/绿色标记为“已访问”来加速算法。这种优化不是免费的:它需要在处理每个路径/节点组合时标记多个标志，并且它会将最坏情况的时间复杂度增加到 O(|E| * 2 ^2*k)。但是所有额外的工作都是在本地节点内完成的。此外，如果所有 2^k 标志都适合单个 CPU 寄存器，则所有这些工作都可以通过按位逻辑运算并行完成。