4

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

我想找到（或编写）一个算法，给定一个V带有 property的顶点P，找到到某个顶点的最长路径，E这样所有all可能的路径上的顶点V都E包含 property 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的最长路径是-> 。请注意，其他路径，比如-> ，是“有效的”，因为它始终成立，但->是最长的。PV1V7V1V6PV1V7

示例 2

这个例子和上面一样，除了现在P不适用V3：

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

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

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

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

问题

是否有计算此类路径的标准算法？

4

1 回答 1

3

这个问题没有已知的有效解决方案，因为它很容易从哈密顿路径问题中减少，它说 - 给定一个图 - 是否有一条路径恰好穿过所有顶点一次？

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

另一种方法是使用蛮力搜索（最简单的形式是生成所有排列并选择最佳有效的排列）——但这对于大型图来说是不可能的。您可能还需要考虑使用启发式方法（找到“好的”解决方案，但不是最佳解决方案），例如遗传算法。
另一种可能的解决方案是将问题简化为Traveling Salesman Problem，并使用一些现有的 TSP 求解器。请注意，虽然这个问题也是 NP 难的，但由于它经过充分研究，对于中等大小的图有一些非常有效的解决方案。

此外，如果您的图碰巧有点“特殊”（例如DAG），您可能会利用一些智能技术来显着加快多项式时间，例如动态规划。

于 2014-09-17T14:29:15.090 回答