최대 최소 무게로 경로 찾기
https://stackoverflow.com/questions/873126
-
22-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
방향성 그래프에서 경로를 찾는 알고리즘을 연구 중입니다.이는 일반적인 경로가 아니며 이와 같은 작업이 이미 수행되고 있다는 언급을 찾을 수 없습니다.
최대 최소 가중치를 갖는 경로를 찾고 싶습니다.
즉.가중치가 10->1->10 및 2->2->2인 두 경로가 있는 경우 최소 가중치(2)가 첫 번째 경로의 최소 가중치(1)보다 크기 때문에 두 번째 경로가 첫 번째 경로보다 더 나은 것으로 간주됩니다. ).
누구든지 이 작업을 수행할 수 있는 방법을 찾아내거나 참고 자료의 방향을 알려준다면 매우 유용할 것입니다. :)
편집하다::특정 꼭지점에서 다른 특정 꼭지점으로 이동하려고 한다는 사실을 언급하는 것을 잊어버린 것 같습니다.거기에 아주 중요한 점이 있습니다 :/
편집2::아래 누군가가 지적했듯이 가장자리 가중치는 음수가 아니라는 점을 강조해야 합니다.
다른 팁
나는 복사하고있다 이것 답변 및 추가 알고리즘에 대한 정확성 증명 추가 :
나는 몇 가지 변형을 사용할 것입니다 Dijkstra 's. Wikipedia에서 직접 의사 코드를 직접 가져 왔고 5 가지만 변경했습니다.
- 이름이 바뀌었다
dist에게width(3 행에서) - 각각 초기화
width에게-infinity(3 행) - 소스의 너비를 초기화했습니다
infinity(8 행) - 마무리 기준을 설정하십시오
-infinity(14 행) - 업데이트 기능 및 부호 수정 (20 + 21 행)
1 function Dijkstra(Graph, source):
2 for each vertex v in Graph: // Initializations
3 width[v] := -infinity ; // Unknown width function from
4 // source to v
5 previous[v] := undefined ; // Previous node in optimal path
6 end for // from source
7
8 width[source] := infinity ; // Width from source to source
9 Q := the set of all nodes in Graph ; // All nodes in the graph are
10 // unoptimized – thus are in Q
11 while Q is not empty: // The main loop
12 u := vertex in Q with largest width in width[] ; // Source node in first case
13 remove u from Q ;
14 if width[u] = -infinity:
15 break ; // all remaining vertices are
16 end if // inaccessible from source
17
18 for each neighbor v of u: // where v has not yet been
19 // removed from Q.
20 alt := max(width[v], min(width[u], width_between(u, v))) ;
21 if alt > width[v]: // Relax (u,v,a)
22 width[v] := alt ;
23 previous[v] := u ;
24 decrease-key v in Q; // Reorder v in the Queue
25 end if
26 end for
27 end while
28 return width;
29 endfunction
일부 (손으로 파는) 설명이 작동하는 이유 : 소스부터 시작합니다. 거기에서 당신은 그 자체로 무한한 능력을 가지고 있습니다. 이제 소스의 모든 이웃을 확인합니다. 가장자리가 모두 같은 용량을 가지고 있지 않다고 가정하십시오 (예에서는 예를 들어, (s, a) = 300). 그런 다음 더 나은 도달 방법은 없습니다 b 그런 다음 비아 (s, b), 당신은 최고의 사례 용량을 알고 있습니다 b. 당신은 모든 정점에 도달 할 때까지 알려진 정점 세트의 최고의 이웃으로 계속 가십시오.
알고리즘의 정확성 증명 :
알고리즘의 어느 시점에서나 2 개의 정점 a와 b 세트. A의 정점은 올바른 최대 최소 용량 경로가 발견 된 정점입니다. 그리고 세트 B에는 답을 찾지 못한 정점이 있습니다.
유도 가설: 모든 단계에서 세트 A의 모든 정점은 최대 최소 용량 경로의 올바른 값을 갖습니다. 즉, 이전의 모든 반복이 정확합니다.
기본 사례의 정확성: 세트 a에 정점 만있는 경우. 그런 다음 s에 대한 값은 무한대입니다.
현재 반복에서 우리는 설정합니다
val [w] = max (val [w], min (val [v], width_between (vw))))
유도 적 단계: W가 가장 큰 val [w]를 가진 세트 B의 정점이라고 가정 해 봅시다. 그리고 w는 대기열에서 탈취되고 w는 answer val [w]로 설정되었습니다.
이제 우리는 다른 모든 SW 경로에 너비가 <= val [w]를 가지고 있음을 보여 주어야합니다. W에 도달하는 다른 모든 방법은 세트 B에서 다른 정점 (x 호출)을 통과하기 때문에 항상 사실입니다.
그리고 세트 b의 다른 모든 정점 x, val [x] <= val [w
따라서 w 로의 다른 경로는 Val [x]에 의해 제한 될 것이며, 이는 Val [w]보다 크지 않습니다.
따라서 Val [W]의 현재 추정치는 최적이므로 알고리즘은 모든 정점에 대한 올바른 값을 계산합니다.
"답변의 이진 검색"패러다임을 사용할 수도 있습니다. 즉, 무게를 검색하고 각 체중에 대한 테스트를 수행합니다. w 무게의 가장자리 만 사용하여 그래프에서 경로를 찾을 수 있는지 여부 w.
가장 큰 w 이진 검색을 통해 찾을 수있는 경우 답변을 제공합니다. 경로가 존재하는지 확인하면되므로 가장 짧은 경로가 아닌 O (| e |) 너비 우선/깊이 우선 검색 만 확인하십시오. 그래서 O(|E|*log(max W)) 대체로 Dijkstra/Kruskal/Prim의 것과 비슷합니다. O(|E|log |V|) (그리고 나는 그것들의 증거도 즉시 볼 수 없습니다).
이것은 BFS 스타일 알고리즘을 사용하여 해결할 수 있지만 두 가지 변형이 필요합니다.
- 각 노드를 "방문한"것으로 표시하는 대신, 당신은 당신이 도달하기 위해 취한 경로를 따라 최소 무게로 표시합니다.
예를 들어, I와 J가 이웃 인 경우 값 W1을 가지고 있고, 그들 사이의 가장자리의 무게는 w2, j = min (w1, w2)입니다.
- W1 값이있는 표시된 노드에 도달하면 새 값 W2 (및 W2> W1)를 할당하면 다시 설명하고 처리해야 할 수도 있습니다. 최대 최소값을 얻으려면 필요합니다.
예를 들어, I와 J가 이웃 인 경우 값 W1, j는 값 W2를 가지고 있고, 그들 사이의 가장자리의 무게는 w3이고, Min (W2, W3)> w1이면 J를 비시하고 이웃을 처리해야합니다. 다시.
프리 프림이 여기서 작동 할 것이라고 확신하지 못합니다. 이 반례를 취하십시오.
V = {1, 2, 3, 4}
E = {(1, 2), (2, 3), (1, 4), (4, 2)}
weight function w:
w((1,2)) = .1,
w((2,3)) = .3
w((1,4)) = .2
w((4,2)) = .25
1에서 3까지의 Maxmin 경로를 찾기 위해 Prim을 적용하면 1부터 시작하여 1 --> 2 --> 3 경로, 최대 미세 거리는 4를 통과하는 경로에 대해 달성됩니다.
좋아, 여기에 내 자신의 질문에 대답하면서 여기에 게시하기 전에 내가 한 잠정적 인 솔루션에 대해 약간의 피드백을 얻으려고 노력하고 있습니다.
각 노드는 "경로 조각"을 저장합니다. 이것은 지금까지 그 자체로가는 전체 경로입니다.
0) 현재 정점을 시작 정점으로 설정하십시오
1)이 정점에서 모든 경로 조각을 생성하여 우선 순위 대기열에 추가하십시오.
2) 우선 순위 대기열에서 파편을 맨 위에서 벗고 현재 정점을 그 경로의 끝 정점으로 설정합니다.
3) 현재 정점이 대상 정점 인 경우 경로를 반환합니다.
4) GOTO 1
나는 이것이 가장 좋은 길을 찾을 것이라고 확신하지 못한다. 나는 3 단계의 출구 조건이 약간 야심적이라고 생각한다. 이 알고리즘은 정점을 닫지 않기 때문에 더 나은 종료 조건을 생각할 수는 없습니다 (정점은 원하는만큼 많은 경로 조각에서 참조 할 수 있습니다). 예시)
Dijkstra를 계속 사용할 수 있습니다!
+를 사용하는 대신 min() 연산자를 사용하십시오.
또한 가장 큰 항목이 맨 위에 오도록 heap/priority_queue의 방향을 지정하는 것이 좋습니다.
다음과 같이 작동해야 합니다.(아마 일부 구현 세부 사항을 놓쳤을 것입니다)
let pq = priority queue of <node, minimum edge>, sorted by min. edge descending
push (start, infinity) on queue
mark start as visited
while !queue.empty:
current = pq.top()
pq.pop()
for all neighbors of current.node:
if neighbor has not been visited
pq.decrease_key(neighbor, min(current.weight, edge.weight))
노드에 도달할 때마다 최적의 경로를 따른다는 것이 보장됩니다(모든 가능성을 내림차순으로 찾고 가장자리를 추가하여 경로를 개선할 수 없기 때문입니다).
시간 범위는 Dijkstra의 - O(Vlog(E))와 동일합니다.
편집하다:아 잠깐만요, 이게 기본적으로 당신이 게시한 내용이에요.ㅋㅋㅋ.
