具有唯一顶点权重的有向无环图的最长路径

Question

给定一个顶点加权 DAG（具有非唯一的顶点权重）、一个起始节点和一个结束节点，找到从起始到结束的最长路径 P，其中 P 中的每个顶点都有唯一的顶点权重。

我意识到重量有点用词不当，它更像是一个ID，因为我们关心的是唯一性，而不是最小化或最大化成本之和等。

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

这个问题是另一个问题的简化（尽管不同的问题可能更简单一些），我对这个问题的疑问与对上述问题的疑问相同： 给定一个非唯一字符串数组 A。找到一个最大长度的数组 A'，其中 A' 包含唯一元素。允许将 A 转换为 A' 的唯一操作是连接 A 中的任何相邻元素。（此操作可以根据需要应用多次）。

Answer 1

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

Start by putting 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
              Add current path to output
        Backtrack along path to vertex adjacent to vertex on top of stack, marking vertices as unvisited