방향이없는 그래프가 있습니다. 지금은 그래프가 완성되었다고 가정하십시오. 각 노드에는 이와 관련된 특정 값이 있습니다. 모든 가장자리는 양수입니다. 경로 노드와 연관된 값의 합이 최대이고 동시에 경로 길이가 주어진 임계 값 내에 있도록 주어진 2 노드 사이의 경로를 찾고 싶습니다. 솔루션은 "전역"이어야합니다. 즉, 얻은 경로가 모든 가능한 경로 중에서 최적이어야합니다. 선형 프로그래밍 방식을 시도했지만 올바르게 공식화 할 수는 없습니다. 제안이나 다른 해결 방법이 큰 도움이 될 것입니다.그래프에서 노드와 에지를 모두 고려한 경로 찾기 알고리즘
감사합니다.
이것은 완벽하지는 않지만 임계 값 (T)가 충분히 작 으면 O (n^3 T^2)에서 실행되는 간단한 알고리즘이 있습니다. Floyd-Warshall의 작은 수정판입니다.
d = int array with size n x n x (T + 1)
initialize all d[i][j][k] to -infty
for i in nodes:
d[i][i][0] = value[i]
for e:(u, v) in edges:
d[u][v][w(e)] = value[u] + value[v]
for t in 1 .. T
for k in nodes:
for t' in 1..t-1:
for i in nodes:
for j in nodes:
d[i][j][t] = max(d[i][j][t],
d[i][k][t'] + d[k][j][t-t'] - value[k])
The result is the pair (i, j) with the maximum d[i][j][t] for all t in 0..T
편집 : 이 그들이주기를 포함 할 수 있습니다, 경로는 간단하지가 될 수 있다고 가정합니다. EDIT2 : 또한 노드가 경로에 두 번 이상 나타날 경우이 노드는 두 번 이상 계산됩니다. 이것은 분명히 OP가 원했던 것이 아닙니다! 당신이 당신의 문제에 대한 해결책을 찾을 경우
이 둘의 관계는 무엇입니까? d [i] [k] [t '] + d [k] [j] [t-t']'? 'd [k] [j] [t-t ']'의 의미는 무엇입니까? –
@SaeedAmiri d [i] [j] [k]는 길이가 정확히 k 인 노드 i와 j 사이의 경로에있는 정점 레이블의 최대 합입니다. d [i] [k] [t '] + d [k] [j] [t-t']는 i에서 k까지 그리고 k에서 j까지의 두 경로이다. 첫 번째는 길이가 t이고 두 번째는 길이가 t-t '이고 함께 길이 t의 경로를 만듭니다. – aelguindy
당신이 일반적으로 그래프의 알고리즘을 찾는 경우가 문제가 NP-완료, 길이 임계 값 N-1이고, 각 정점 값 1을 가지고 경로를 가정, 당신은 말할 수 주어진 그래프는 해밀턴 경로를가집니다. 사실 최대화 된 정점 크기 경로의 값이 n 인 경우 해밀턴 경로가 있습니다. 나는 좋은 해결책을 찾기 위해 Held-Karp 이완과 같은 것을 사용할 수 있다고 생각합니다. 정점 V 달리 방문 및 0 경우 X V 1하자, 각 정점 V에 대한
:
경로가 단순하지 않을 경우 축소가 실패했다고 생각합니다. 나는 OP가 어떤 경로를 찾고 있는지 언급하지 않았지만,이 점이 당신의 대답에 명확 해지면 더 좋을 것이라고 생각합니다. – aelguindy
@aelguindy, 간단한 경로로 작성했지만, OP의 의견이 무엇인지 모르겠지만 일반적으로 그래프로 경로를 말할 때 간단한 경로에 대해 이야기합니다 (그래프로 된 모든 교과서를 참조하십시오). 이론, 처음 몇 페이지는 이것을 말한다). 또한 내 그래프는 일반적인 그래프이지만, OP는 그래프가 현재 완성되었다고합니다. 그래서 모든면을 알고 있습니다.하지만 OP가 선형 프로그래밍을 원한다고 생각합니다. 몇 가지 관련 정보를 소개하는 편이 낫다고 생각했습니다. 선형 프로그래밍. –
정수 프로그램 (이것은 좋은 아이디어 나 아마 할 수있다). 각각의 호 a에 대해서, 은을 호가 사용 된 횟수로 놓는다. s가 소스이고 t가 목적지가되도록하십시오. 목적은
가 ∑ V 값 (V) V X를 최대화한다.
제약은
∑ 값 (a) Y ≤ 임계 및 FORALL이고; V, ∑ A는 헤드 V을 가지고 Y -∑ A는 꼬리 V Y를 갖는다 a = {-1 인 경우 v = s; v = t 인 경우 1; 그렇지 않으면 0 (플로우 절약)
및 FORALL; V ≠ X, X V ≤ ∑ (방문 정점을 입력 함)
및 FORALL은 Y, A는 헤드 V있다; V, X V ≤ 1 V ∉ {S, t}, FORALL; FORALL
&를 (많아야 한번 각 정점을 참조) {S, t}에서 정점 V 분리 인하 S, X V ≤ ∑ 되도록 꼬리 (a) ∉ S ∧ head (a) ∈ Sy (격리 된 루프에없는 정점에서만 유익 함)
해결하려면 이완 값으로 분기하고 바인딩하십시오. 불행하게도 제약 조건의 마지막 그룹은 기하 급수적입니다. 따라서 편안한 이중화를 해결할 때는 열을 생성해야합니다. 일반적으로 연결 문제의 경우, min-cut 알고리즘을 반복적으로 사용하여 시행 할 가치가있는 상처를 찾습니다. 행운을 빕니다!
지금은 좋아 보인다. 나는 이것을 분석하여 의심이 있는지 알려주겠습니다. – arg
나가는 가장자리 가중치에 노드의 가중치를 추가하면 노드 가중치를 잊어 버릴 수 있습니다. 그런 다음 shortest path problem에 대한 표준 알고리즘 중 하나를 사용할 수 있습니다.
"선형 프로그래밍"이란 정확히 무엇을 의미합니까? – WeaselFox
@WeaselFox, [Wikipedia의 선형 프로그래밍] (http://en.wikipedia.org/wiki/Linear_programming) – svick
경로 길이가 임계 값 인 경우 루프를 사용할 수 있습니까? – harold