n 단계 내에서 유향 그래프에서 얻은 최대 값을 계산하는 좋은 알고리즘

Question

문제는 다음과 같습니다. 각 꼭지점은 i 번째 단계에서 값 [i] 값을가집니다.
는

  +----+-----+------+------+-----+-----+-----+----+-----+---- +------+-------+ 
      | |  |  |  |  |  |  | |  | |  |  | 
Value for V1| 2 | 1 | 6 | 4 | 3| 4 | 5 | 1 | 9 | 1 | 10 | 2 | 
      | |  |  |  |  |  |  | |  | |  |  | 
      +----+-----+------+------+-----+-----+-----+----+-----+----+------+-------+ 

이 단계는 글로벌 단계 (이 그래프는 늦어도 계산의 예와 관련된 단지 데모이다). 그래서 1 단계에서 2 단계로 갈 때, 배열의 모든 꼭지점의 값 인덱스가 움직입니다.

목적은 N 개의 단계로 최대 값을 얻을 수있는 최대 경로를 찾는 것입니다. 1,4,5,2,3

B 값 어레이 : 2,1,1 우리는 A, B, C

값이 정점 어레이

예 : 그래서

, 5,4

C 값 어레이 3,2,9,6,1

그래프 : A -> B; B → C; C ->를

N : 5 (당신이 단계)

최적 경로 : (A 항상부터 시작)

A-> B-> C-> C->은

값 : 우리가 할 경우는 20

무슨 일이있다

A-> B-> C-> C-> C 값이 18 만

된다

때문에 이 좋은 알고리즘이 일을?

Dijkstra가 여기에 적합하지 않은 것 같습니다.

Answer 1

모든 단계에서 특정 정점에서 끝나는 최적의 하위 경로를 찾을 수 있습니다.

첫 번째 단계에서 모든 정점에 대해이 정점에서 끝나고 최대 값을 유도하는 부분 경로를 찾습니다. 다음 단계에서 이전 값으로 시작하여 반복하십시오. 각 버텍스의 선행 작업을 저장하면 하위 경로 (및 값)를 쉽게 찾을 수 있습니다. 최대 값을 가진 선행 작업을 선택하기 만하면됩니다. 사용자의 입력 (그리고 반사적 인 에지)와

예 :

A max : 5 (subpath A->A) 
B max : 2 (subpath A->B) 
C max : 0 (no subpath) 

번째 단계 :

A max : 10 (subpath A->A->A) <- the predecessors of A are A and C, 
            and the previous max value of A 
            is greater than that of C. 
B max : 5 (subpath A->A->B) 
C max : 11 (subpath A->B->C) 

A values : 1, 4, 5, 2, 3 
B values : 2, 1, 1, 5, 4 
C values : 3, 2, 9, 6, 1 
A successors : A, B 
B successors : B, C 
C successors : A, C 
A predecessors : A, C 
B predecessors : A, B 
C predecessors : B, C 

는에서 시작 값 1은 첫 번째 단계에 이르게

제 3 단계 :

A max : 13 (subpath A->B->C->A) 
B max : 15 (subpath A->A->A->B) 
C max : 17 (subpath A->B->C->C) 

마지막 네 번째 단계 :

A max : 20 (path A->B->C->C->A) 
B max : 19 (path A->A->A->B->B) 
C max : 18 (path A->B->C->C->C)