我有一个有向图(更具体地说，是一个控制流图)，每个顶点都有一组属性。
我想找到(或编写)一个算法，给定一个具有属性 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
这个例子和上面的一样，只是 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开始，P在所有可能路径中始终持有的最长路径是V1 -> V6。路径 V1 -> V7 无效，因为 V1 和 V7 之间存在路径，其中 P 不成立。
关于我的情况的进一步说明
- 图形可以是循环的。
- 图表将是“中小型”尺寸，可能有 1000 个或更少的顶点。
- 图表不一定总是一根一叶，就像我上面的例子。
问题
是否有计算此类路径的标准算法？
最佳答案
这个问题没有已知的有效解决方案，因为它很容易从 Hamiltonian Path Problem 减少，它说 - 给定一个图 - 是否有一条路径恰好通过所有顶点一次？
归约很简单 - 给定哈密顿路径问题，用 p 标记所有节点，并找到最长路径。由于哈密顿路径是 NP-Complete ，这个问题也是如此，而且没有已知的多项式解法。
另一种方法是使用 brute-force search (最简单的形式是生成所有排列并选择最有效的排列) - 但对于大图来说这将变得不可能。您可能还需要考虑使用启发式方法(找到“好的”解决方案，但不是最佳解决方案)，例如遗传算法。
另一种可能的解决方案是将问题减少到Traveling Salesman Problem。 ，并使用一些现有的 TSP 求解器。请注意，虽然这个问题也是 NP 难的，但由于它已得到充分研究，因此对于中等大小的图有一些非常有效的解决方案。
此外，如果您的图形碰巧有点“特殊”(例如 DAG)，您可以利用一些智能技术来显着加快多项式时间的速度，例如动态规划。
关于algorithm - 在图中，找到具有特定属性的最长路径？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/25891813/