[algorithm] 특정 노드를 방문하는 그래프에서 최단 경로 찾기

이것을 Traveling Salesman Problem과 비교하는 다른 사람들은 아마 당신의 질문을주의 깊게 읽지 않았을 것입니다. TSP에서 목표는 모든 정점 을 방문하는 가장 짧은주기 (해밀턴주기)를 찾는 것입니다. 이는 모든 노드가 ‘mustpass’라는 레이블 을 갖는 것에 해당합니다 .

귀하의 경우에는 ‘mustpass’라는 레이블이 붙은 약 12 ​​개만 가지고 있고 그 12 개가 주어졌습니다! 다소 작습니다 (479001600). ‘mustpass’노드의 모든 순열 만 시도하고 ‘mustpass’노드를 순서대로 방문하는 ‘start’에서 ‘end’까지의 최단 경로를 살펴볼 수 있습니다. 해당 목록에있는 두 개의 연속 노드 사이의 최단 경로 연결입니다.

즉, 먼저 각 정점 쌍 사이의 최단 거리를 찾으십시오 (Dijkstra의 알고리즘 또는 다른 알고리즘을 사용할 수 있지만이 작은 수 (100 개 노드)를 사용하면 가장 간단한 코드화 Floyd-Warshall 알고리즘 도 시간 내에 실행됩니다). 그런 다음 테이블에 이것을 가지고 있으면 ‘mustpass’노드의 모든 순열을 시도하고 나머지는 시도하십시오.

이 같은:

//Precomputation: Find all pairs shortest paths, e.g. using Floyd-Warshall
n = number of nodes
for i=1 to n: for j=1 to n: d[i][j]=INF
for k=1 to n:
    for i=1 to n:
        for j=1 to n:
            d[i][j] = min(d[i][j], d[i][k] + d[k][j])
//That *really* gives the shortest distance between every pair of nodes! :-)

//Now try all permutations
shortest = INF
for each permutation a[1],a[2],...a[k] of the 'mustpass' nodes:
    shortest = min(shortest, d['start'][a[1]]+d[a[1]][a[2]]+...+d[a[k]]['end'])
print shortest

(물론 실제 코드가 아니며 실제 경로를 원한다면 가장 짧은 거리를 제공하는 순열과 모든 쌍의 최단 경로가 무엇인지 추적해야하지만 아이디어를 얻을 수 있습니다.)

합리적인 언어에서 최대 몇 초 안에 실행됩니다. 🙂
[n 개의 노드와 k 개의 ‘mustpass’노드가있는 경우 실행 시간은 Floyd-Warshall 부분의 경우 O (n ³ )이고 O (k! n ) 모든 순열 부분에 대해, 100 ^ 3 + (12!) (100)은 실제로 제한적인 제약이없는 한 사실상 땅콩입니다.]