算法 - 给定顶点约束的路径查找

Question

我将给出这个问题的一般情况，因为这是我第二次看到可以简化为这个的东西，而且我找不到比检查每条路径更好的方法。

假设我们有一个有向图 G，其顶点为 V，并且没有环和自边。此外，每个顶点都有一种颜色。找到从给定顶点开始的最长路径，使得该路径最多经过每种颜色的 1 个顶点。

我已经通过在递归步骤中删除所有添加顶点颜色的顶点来实现本质上是深度优先搜索，我想知道是否有更好的方法来做到这一点。我一直遇到的问题是，由于颜色限制，存储过去的结果很困难，因此像 Dijkstra 这样的最短路径算法不会给出正确的结果。

Answer 1

你的问题的答案是否。

如果您为每个顶点分配不同的颜色，您的问题将减少到 Hamiltonian path problem这是 NP 难的。