在一个图中，找出具有某种属性的最长路径？

Question

在一个图中，找出具有某种属性的最长路径？

algorithmgraphgraph-theorylongest-path

4

我有一个有向图（更具体地说是控制流程图），每个顶点都有一组属性。

我想要找到（或编写）一个算法，给定一个带有属性P的顶点V，可以找到到某个顶点E的最长路径，使得从V到E的所有可能路径上的所有顶点都包含属性P。

示例1

假设我有以下图形。（请原谅糟糕的ASCII图。）

                    +----+            
           +--------+P   +--------+   
           |        +----+        |   
           |         V1           |   
           |                      |   
           |                      |   
        +--v--+                   |   
   +----+P    ++                  |   
   |    +-----++               +--v--+
   |           |          +----+P    |
   |           |          |    +-----+
+--v--+     +--v--+       |           
|P    +-+ +-+P    |       |           
+-----+ | | +-----+       |           
        | |               |           
        | |               |           
       +v-v--+            |           
  V6   |P    +---------+  |           
       +-----+         |  |           
                       |  |           
                       |  |           
                       |  |           
                       |  |           
                     +-v--v-+         
                V7   |P     |         
                     +---+--+         
                         |            
                         |            
                     +---v--+         
                V8   |!P    |         
                     +------+

从V1开始，所有可能路径上P一直成立的最长路径是V1 -> V7。请注意，其他路径，如V1 -> V6，虽然P总是成立的，但V1 -> V7是最长的。

示例2

这个例子与上面相同，只是现在V3中P不成立:

                    +----+            
           +--------+P   +--------+   
           |        +----+        |   
           |         V1           |   
           |                      |   
           |                      |   
        +--v--+                   |   
   +----+P    ++                  |   
   |    +-----++               +--v--+
   |           |          +----+!P   |  V3
   |           |          |    +-----+
+--v--+     +--v--+       |           
|P    +-+ +-+P    |       |           
+-----+ | | +-----+       |           
        | |               |           
        | |               |           
       +v-v--+            |           
  V6   |P    +---------+  |           
       +-----+         |  |           
                       |  |           
                       |  |           
                       |  |           
                       |  |           
                     +-v--v-+         
                V7   |P     |         
                     +---+--+         
                         |            
                         |            
                     +---v--+         
                V8   |!P    |         
                     +------+

在这种情况下，从V1开始，在所有可能的路径中，P始终保持的最长路径是V1 -> V6。路径V1 -> V7无效，因为在V1和V7之间存在一条路径，其中P不成立。

关于我的情况的进一步说明

图可以是循环的。
图将是“小到中等”的大小，可能有1000个或更少的顶点。
图不一定总是有一个根和一个叶子，就像上面的例子一样。

问题

是否有一种标准算法来计算这样的路径？

- stepthom

我对你的第二个例子有点困惑。你是说你想要从顶点 S 到某个顶点 E 的最长路径，使得 P 在连接 S 和 E 之间的所有路径上的所有顶点上都成立吗？这似乎是一个非常严格的限制... - Vincent van der Weele

1

这个编程问题没有简单的解决方案，因为它可以轻松地从哈密顿路径问题中简化出来（给定哈密顿路径问题，将所有节点标记为 p，并找到最长路径）。由于哈密顿路径是 NP-完全问题，所以这个问题也是 NP-完全问题，并且目前没有已知的多项式解决方案。 - amit

@doofuslarge 你能澄清一下吗：

起始顶点是否总是固定的细节？
图形是否总是具有一个根和一个叶子？
图形是否总是无环的？

- Christian Convey

@user1990169：我猜你指的是例子2。在那种情况下，“V7”不是“有效”的，因为存在一条从“V1”到“V7”的路径，其中“P”不成立，即包含“V3”的路径。 - stepthom

@ChristianConvey：问题已更新，提供了更多细节。 - stepthom

显示剩余5条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- amit · Accepted Answer

问题没有已知的高效解决方案，因为它可以很容易地从哈密顿路径问题简化得到，该问题是指 - 给定一个图形 - 是否有一条路径仅恰好通过所有顶点？

简化很简单 - 给定哈密顿路径问题，用p标记所有节点，并找到最长的路径。由于哈密顿路径是 NP-Complete，所以这个问题也是如此，并且没有已知的多项式解决方案。

另一种选择是使用暴力搜索（最简单的形式是生成所有排列并选择最佳的有效解）-但对于大型图形来说这将变得不可能。您可能还需要考虑使用一种启发式方法（找到“好”的解决方案，而不是最优解），例如遗传算法。
另一个可能的解决方案是将问题简化为旅行商问题，并使用一些现有的TSP求解器。请注意，虽然这个问题也是NP难问题，但由于它已经得到了广泛研究，因此有一些相当高效的解决方案适用于中等规模的图形。

此外，如果您的图形某种程度上是“特殊的”（例如DAG），您可以利用一些聪明的技巧来实现显着的速度提升到多项式时间，例如动态规划。