정렬 된 그래프에서 가장 긴 경로

Question

G = (V, E)를 노드 v_1, v_2, ..., v_n을 갖는 방향성 그래프라고합시다. G는 다음과 같은 특성을 갖는다면 G가 정렬 된 그래프라고합니다.

• 각 에지는 색인이 낮은 노드에서 색인이 더 높은 노드로 이동합니다. 즉, 모든 지향 에지는 i < j의 형식 (v_i, v_j)을 갖습니다.
• v_n을 제외한 각 노드에는 적어도 하나의 가장자리가 있습니다. 즉, 모든 노드 v_i에 대해 하나 이상의 양식 (v_i, v_j) 가장자리가 있습니다.

정렬 된 그래프 G를 취하고 v_1에서 시작하여 v_n에서 끝나는 가장 긴 경로의 길이를 반환하는 효율적인 알고리즘을 제공하십시오.

당신이 좋은 라텍스 버전을 확인하려면 다음 here

내 시도 :

동적 프로그래밍. j와 같은 모든 j에 대해 Opt (i) = max {Opt (j)} + 1. i로부터 도달 가능하다.

아마도 더 좋은 방법이 있을까요? 메모를해도 알고리즘은 여전히 ​​지수적일 것입니다. (이것은 온라인에서 발견 된 오래된 중기 리뷰에서 나온 것임)

Answer 1

접근 방식이 옳다, 당신은 그러나

Opt(i) = max {Opt(j)} + 1} for all j such that j is reachable from i 

---

을해야 할 것, 이것은 당신이 메모이 제이션없이 실행하는 경우에만 지수입니다. 메모를 사용하면 노드 i에있을 때 모든 노드 j, j> i에 대해 메모 된 최적 값을 갖게됩니다.

최악의 경우 복잡성을 위해 연결될 수있는 두 개의 노드가 모두 연결되어 있다고 가정합시다. 즉, v_1은 (v_2, v_3, ... v_n)으로 연결됩니다. v_i은 (v_(i+1), v_(i+2), ... v_n)으로 연결됩니다.

정점의 수 (V) = N

따라서, 가장자리 (E) = n*(n+1)/2 = O(V^2)

우리가 정점 v_k에 우리의 관심을 집중하자의 수. 이 버텍스의 경우 이미 파생 된 최적 값인 (n-k) 개 노드를 통과해야합니다.O(n^3) 시간 복잡도 될 것이다 따라서 파워 2 polynomical의 시그마이고 v_k 직접 = (K-1)

따라서 최악의 경우의 시간 복잡도 =>sigma((k-1)*(n-k)) from k=1 to k=n을 도달 방법

번호.

간단히, 최악의 경우의 시간 복잡도는 O(n^3) == O(V^3) == O(E) * O(V) == O(EV)입니다.

Answer 2

첫 번째 속성 덕분에이 문제는 O (V^2) 또는 O (E)로 해결할 수 있습니다. 여기서 V는 정점의 수이고 E는 모서리의 수입니다. 실제로, 동적 프로그래밍 방식을 사용합니다. 동적 프로그래밍 방식은 사용자가 제공하는 것과 비슷한 조용한 방식입니다. opt [i]를 v_1에서 v_i까지의 가장 긴 경로의 길이 라하자. 그런 다음

opt[i] = max(opt[j]) + 1 where j < i and we v_i and v_j is connected, 
         using this equation, it can be solved in O(V^2). 

더 나은 방법으로이를 다른 순서로 해결할 수 있습니다.

int LongestPath() { 
    for (int v = 1; v <= V; ++v) opt[v] = -1; 
    opt[1] = 0; 
    for (int v = 1; v <= V; ++v) { 
    if (opt[v] >= 0) { 
    /* Each edge can be visited at most once, 
     thus the runtime time is bounded by |E|. 
     */ 
     for_each(v' can be reached from v) 
     opt[v'] = max(opt[v]+1, opt[v']); 
    } 
    } 
return opt[V]; 

}