최단 경로 문제에 대해 최대 비용 값을 어떻게 할당 할 수 있는지 궁금합니다. 내 문제는 노드와 관련된 위험이 있습니다. 그래서 위험을 최소화하고 싶습니다만, 제한된 수의 노드로 솔루션을 찾고 싶습니다. (예를 들어 노드 A에서 노드 B까지의 최소 위험을 찾아 솔루션이 n 개의 노드를 초과하지 않도록하십시오.) 감사합니다. 많이.최대 비용으로 최단 경로 - 다이크 스트라 알고리즘을 제한하는 방법은 무엇입니까?
Dijkstra는 Best First Search입니다. 즉, 최상의 노드까지의 거리가 결코 좋지 않을 것입니다. 그것은 비 - 부정 가장자리와 최소 Dijkstra 작동합니다. 일반적으로 Ford-Bellman을 사용할 수 있습니다. 당신이 n 개 이상의 정점을 사용하고 싶다면 복잡성 O (| V | * n) 상태와 메모리 및 O (| E | * n) 시간을 갖는 동적 프로그래밍 dp [vertex] [used_vertex_count]를 제안 할 수 있습니다. 또는 그래프의 인접 행렬을 주 대각선 및 무한대의 영점에 0을두고 생성하고 계산은 n 지수입니다. a_ {ij}는 n 개 이상의 정점을 사용하여 i에서 j까지의 최소 경로가됩니다.
휴리스틱과 관련된 알고리즘이 가장 적합 할 것입니다. 휴리스틱은 각 단계에있는 목표에 "근접"하고 목표에 더 가까워 질 것입니다. 이것이 없다면, 우리는 최악의 경우에 지수 알고리즘을 실행할 필요가 있다고 생각합니다. (단지 n 개의 노드를 사용하여 목표에 도달 할 수없는 경우입니다.)이 경우, 결론을 내리기 전에 n 개의 노드를 사용하는 모든 경로를 살펴볼 것입니다. 문제는 해결 될 수 없다).
비 휴리스틱 알고리즘을 사용하는 한 가지 예는 다음과 같습니다. Dijkstra를 정기적으로 실행하여 위험이 가장 적은 노드를 선택합니다. 길을 따라 방문한 노드의 수를 추적하십시오. 노드 수가 n 이상인 경우 현재 경로를 포기하고 이전 노드로 되돌아가 다음 위험이 가장 낮은 노드를 사용하십시오. 당연히 목표가 다음 레벨에 있다면 선택되었을 것이므로 n 위의 한 수준 만 되돌릴 수는 없습니다. 따라서 레벨 n-2으로 되돌아 가서 계속 진행하십시오. 이것은 또한 모든 경로를 검사하지 않고 존재하지 않는 것을 결정하는 실제 방법이 없기 때문에 기하 급수적 일 것입니다.
내가 누락 된 항목이 될 수도 있습니다.
주어진 그래프에서 모든 최소 스패닝 트리를 찾기 때문에 Prim의 알고리즘을 사용하려고합니다. 그런 다음 원하는 제약 조건을 사용하여 mst를 쉽게 선택할 수 있습니다.