3

我有一个有向的彩色图（每个节点都有一种颜色），我想找出从节点 A 到节点 B 的路径是否存在，使得路径在 MOST 处通过每种颜色一次。

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

谢谢！

4

3 回答 3

1

假设您想使用搜索算法来执行此操作，您很可能会使用深度优先和回溯，从图中删除（或标记为已访问）您访问的每个节点

将为访问的颜色保留一个哈希表，以快速检查您发现的每种新颜色是否已知（或者检查图表上从 A 到 C [=当前] 或从 C 到 A [无关紧要] 的访问路径，如果你不能使用单独的结构，只能在图表上附加属性）。

对于回溯，您可以在从导致死路（无法到达 B）的传出链接回溯到节点后检查下一个传出链接。这假设链接具有一些隐式排序（即可以要求下一个链接 - 并检查它是否是传出链接或要求下一个直到没有更多可用时 - 当您有一个节点和它的其他传出链接时回溯时回来））

但是，应该有更好的算法对图形进行一些（可并行化）预处理并在节点和/或链接上附加值，以帮助从给定颜色或任何颜色进行搜索

于 2015-11-08T01:03:01.747 回答
1

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

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

这里我解释一下这个BFS算法（从简化版开始）：

路径访问的所有节点的颜色都应该被编码到 bitset 中，例如，如果我们有 3 种可用颜色（红色、绿色、蓝色）和访问绿色节点的路径，则将其编码为010; 在这条路径也访问红色节点之后，它被编码为011。路径颜色与上次访问的节点一起存储在 BFS 队列中。

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

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

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

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 寄存器，所有这些工作都可以通过按位逻辑运算并行完成。

于 2015-11-08T12:37:21.270 回答
1

只做普通的 DFS，但也要保留一个颜色列表和一个布尔值。如果你要访问一个带有某种颜色的节点，而对应的布尔值是false，设置为true并访问它；否则不要访问该节点并继续递归。如果你没有到达 B 就终止了，那么显然没有路径。

编辑：如果某些选择的路径不起作用，并且递归回溯，请重置与您回溯过去的节点的颜色相关的布尔值。

于 2015-11-08T00:46:56.913 回答