具有独特颜色的有向无环图的最长路径

Question

给定一个彩色 DAG（具有非唯一颜色）、一个起始节点和一个结束节点，找到从开始到结束的最长路径 P，其中 P 中没有 2 个顶点具有相同的颜色。

我想知道是否有一个多项式时间算法可以解决这个问题，或者它是否是已知的 NP-HARD，或者在某些类别的非多项式问题中。如果没有是否有什么好的近似技术或启发式搜索思路。

Answer 1

这是查找具有唯一顶点“权重”的两个顶点之间最长路径的算法

Set saved path with length zero
Put the start vertex on top of a stack.
LOOP
    IF stack empty, STOP
    Take the top vertex of the stack and add it to the visited list and the current path
    Add adjacent vertices which aren't in the visited list to the top of the stack.
    If the destination has been reached
        IF current path has all unique weighted vertices
            IF current path is longer than saved path
                Save current path to output
        Backtrack along path to vertex adjacent to vertex on top of stack, marking vertices as unvisited
Output saved path