有序图中的最长路径 [英] Longest path in ordered graph
问题描述
让G =(V，E)是节点v_1，v_2，...，v_n的有向图.我们说G具有以下特性是有序图.
Let G = (V, E) be a directed graph with nodes v_1, v_2,..., v_n. We say that G is an ordered graph if it has the following properties.
- 每个边缘从索引较低的节点到索引较高的节点.即，每个有向边的形式为(v_i，v_j)，其中i ＜i.j.
- 除v_n之外的每个节点都有至少一个边保留.也就是说，对于每个节点v_i，至少有一个形式为(v_i，v_j)的边.
给出一种有效的算法，该算法采用有序图G并返回从v_1开始到v_n结束的最长路径的长度.
Give an efficient algorithm that takes an ordered graph G and returns the length of the longest path that begins at v_1 and ends at v_n.
如果您想查看漂亮的乳胶版本:这里
If you want to see the nice latex version: here
我的尝试:
动态编程.Opt(i)= max {Opt(j)} +1.对于所有j，这样的j都可以从i到达.
Dynamic programming. Opt(i) = max {Opt(j)} + 1. for all j such such j is reachable from i.
也许有更好的方法可以做到这一点?我认为即使有了记忆，我的算法仍将是指数级的.(这只是我在网上找到的一份旧的中期评论)
Is there perhaps a better way to do this? I think even with memoization my algorithm will still be exponential. (this is just from an old midterm review I found online)
推荐答案
您的方法正确，您将不得不做
Your approach is right, you will have to do
Opt(i) = max {Opt(j)} + 1} for all j such that j is reachable from i
但是，只有在没有备注的情况下运行它，它才是指数级的.使用备忘录，当您在节点i上时，您将获得每个节点j的备忘录最优值.
However, this is exponential only if you run it without memoization. With memoization, you will have the memoized optimal value for every node j, j > i, when you are on node i.
对于最坏的情况，让我们假设可以连接的每两个节点都已连接.这意味着 v_1 与(v_2，v_3，... v_n)连接； v_i 与(v_(i + 1)，v_(i + 2)，... v_n)连接.
For the worst case complexity, let us assume that every two nodes that could be connected are connected. This means, v_1 is connected with (v_2, v_3, ... v_n); v_i is connected with (v_(i+1), v_(i+2), ... v_n).
顶点数( V )= n
因此，边数( E )= n *(n + 1)/2 = O(V ^ 2)
让我们将注意力集中在顶点 v_k 上.对于这个顶点，我们必须遍历已经导出的(n-k)个节点的最优值.
Let us focus our attention on a vertex v_k. For this vertex, we have to go through the already derived optimal values of (n-k) nodes.
直接到达 v_k 的方式数=(k-1)
Number of ways of reaching v_k directly = (k-1)
因此，最坏情况下的时间复杂度=> sigma((k-1)*(nk))从k = 1到k = n ，这是幂2多项式的sigma.导致 O(n ^ 3)时间复杂度.
Hence worst case time complexity => sigma((k-1)*(n-k)) from k=1 to k=n, which is a sigma of power 2 polynomical, and hence will result in O(n^3) Time complexity.
简单地说，最差的时间复杂度是 O(n ^ 3)== O(V ^ 3)== O(E)* O(V)== O(EV).
Simplistically, the worst case time complexity is O(n^3) == O(V^3) == O(E) * O(V) == O(EV).
这篇关于有序图中的最长路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
