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

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

---

약 100 개의 노드와 약 200 개의 에지가있는 무 방향 그래프가 있습니다. 하나의 노드는 '시작', 하나는 '끝', 'mustpass'라는 레이블이 붙은 약 12 ​​개가 있습니다.

이 그래프를 통해 '시작'에서 시작하고 '끝'에서 끝나고 모든 '반드시 통과'노드를 통과 하는 최단 경로를 찾아야합니다 .

( http://3e.org/local/maize-graph.png / http://3e.org/local/maize-graph.dot.txt 는 해당 그래프입니다. 펜실베니아 주 랭커스터의 옥수수 미로를 나타냅니다)

---

이것을 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)은 실제로 제한적인 제약이없는 한 사실상 땅콩입니다.]

---

Djikstra의 알고리즘 을 실행 하여 모든 중요 노드 (start, end, must-pass) 사이의 최단 경로를 찾은 다음, depth-first traversal은 모든 노드 start에 닿는 결과 하위 그래프를 통해 최단 경로를 알려줍니다. . mustpasses ... 끝

---

사실 당신이 게시 한 문제는 여행하는 세일즈맨과 비슷하지만 단순한 길 찾기 문제에 더 가깝다고 생각합니다. 각각의 모든 노드를 방문 할 필요없이 가능한 가장 짧은 시간 (거리)에 특정 노드 집합을 방문하기 만하면됩니다.

그 이유는 여행하는 세일즈맨 문제와 달리 옥수수 미로는지도의 한 지점에서 다른 지점으로 이동하기 위해 다른 노드를 통과 할 필요없이 직접 이동할 수 없기 때문입니다.

실제로 고려할 기술로 A * 길 찾기를 권장합니다. 다른 노드에 직접 액세스 할 수있는 노드와 특정 노드의 각 홉에 대한 "비용"을 결정하여이를 설정합니다. 이 경우 노드가 비교적 가까운 간격으로 보이기 때문에 각 "홉"의 비용이 동일 할 수 있습니다. A *는이 정보를 사용하여 두 지점 간의 최저 비용 경로를 찾을 수 있습니다. A 지점에서 B 지점으로 이동하여 약 12 ​​명 사이에 방문해야하므로 길 찾기를 사용하는 무차별 대입 접근 방식도 전혀 문제가되지 않습니다.

고려할 대안입니다. 여행하는 세일즈맨 문제와 매우 비슷해 보이며 읽어보기에 좋은 문서이지만 자세히 살펴보면 그 문제가 지나치게 복잡하다는 것을 알 수 있습니다. ^ _ ^ 이전에 이런 일을 해본 적이있는 비디오 게임 프로그래머의 마음에서 나온 것입니다.

---

이것은 두 가지 문제입니다. Steven Lowe는 이것을 지적했지만 문제의 후반부에 대해서는 충분히 존중하지 않았습니다.

먼저 모든 중요 노드 (start, end, mustpass) 사이의 최단 경로를 찾아야합니다. 이러한 경로가 발견되면 단순화 된 그래프를 구성 할 수 있습니다. 여기서 새 그래프의 각 에지는 원래 그래프의 한 중요 노드에서 다른 노드로의 경로입니다. 여기에서 최단 경로를 찾는 데 사용할 수있는 경로 찾기 알고리즘이 많이 있습니다.

하지만이 새 그래프가 있으면 출장 영업 사원 문제가 발생합니다 (거의 ... 시작 지점으로 돌아갈 필요가 없습니다). 위에서 언급 한 이와 관련된 모든 게시물이 적용됩니다.

---

Andrew Top은 올바른 아이디어를 가지고 있습니다.

1) Djikstra의 알고리즘 2) 일부 TSP 휴리스틱.

Lin-Kernighan 휴리스틱을 추천합니다. NP Complete 문제에 대해 가장 잘 알려진 것 중 하나입니다. 기억해야 할 또 다른 사항은 2 단계 이후에 그래프를 다시 확장 한 후 확장 된 경로에 루프가있을 수 있으므로이를 단락시켜야한다는 것입니다 (경로를 따라있는 정점의 정도를 확인).

이 솔루션이 최적에 비해 얼마나 좋은지 실제로는 잘 모르겠습니다. 단락과 관련된 병리학적인 경우가있을 수 있습니다. 결국,이 문제는 Steiner Tree : http://en.wikipedia.org/wiki/Steiner_tree 와 매우 비슷해 보이며 그래프를 축소하고 예를 들어 Kruskal을 실행하는 것만으로는 Steiner Tree를 근사화 할 수 없습니다.

---

입니다 하지 원래의 질문이 노드가 한 번만 방문하는 것을 반드시 통과를 필요로하지 않기 때문에 TSP 문제와 NP-어려운 일이 아니다. 이것은 Dijkstra의 알고리즘을 통해 모든 필수 통과 노드 사이의 최단 경로 목록을 컴파일 한 후 무차별 대입에 대한 대답을 훨씬 간단하게 만듭니다. 더 나은 방법이있을 수 있지만 간단한 방법은 단순히 이진 트리를 거꾸로 작업하는 것입니다. 노드 목록 [start, a, b, c, end]를 상상해보십시오. 간단한 거리 [start-> a-> b-> c-> end]를 더합니다. 이것은 이길 새로운 목표 거리입니다. 이제 [start-> a-> c-> b-> end]를 시도하고 그게 더 낫다면 대상으로 설정하십시오 (그리고 노드의 패턴에서 나왔음을 기억하십시오). 순열에 대해 거꾸로 작업하십시오.

• [시작-> a-> b-> c-> 끝]
• [시작-> a-> c-> b-> 끝]
• [시작-> b-> a-> c-> 끝]
• [start->b->c->a->end]
• [start->c->a->b->end]
• [start->c->b->a->end]

One of those will be shortest.

(where are the 'visited multiple times' nodes, if any? They're just hidden in the shortest-path initialization step. The shortest path between a and b may contain c or even the end point. You don't need to care)

---

Considering the amount of nodes and edges is relatively finite, you can probably calculate every possible path and take the shortest one.

Generally this known as the travelling salesman problem, and has a non-deterministic polynomial runtime, no matter what the algorithm you use.

http://en.wikipedia.org/wiki/Traveling_salesman_problem

---

How about using brute force on the dozen 'must visit' nodes. You can cover all the possible combinations of 12 nodes easily enough, and this leaves you with an optimal circuit you can follow to cover them.

Now your problem is simplified to one of finding optimal routes from the start node to the circuit, which you then follow around until you've covered them, and then find the route from that to the end.

Final path is composed of :

start -> path to circuit* -> circuit of must visit nodes -> path to end* -> end

You find the paths I marked with * like this

Do an A* search from the start node to every point on the circuit for each of these do an A* search from the next and previous node on the circuit to the end (because you can follow the circuit round in either direction) What you end up with is a lot of search paths, and you can choose the one with the lowest cost.

There's lots of room for optimization by caching the searches, but I think this will generate good solutions.

It doesn't go anywhere near looking for an optimal solution though, because that could involve leaving the must visit circuit within the search.

---

One thing that is not mentioned anywhere, is whether it is ok for the same vertex to be visited more than once in the path. Most of the answers here assume that it's ok to visit the same edge multiple times, but my take given the question (a path should not visit the same vertex more than once!) is that it is not ok to visit the same vertex twice.

So a brute force approach would still apply, but you'd have to remove vertices already used when you attempt to calculate each subset of the path.

참고URL : https://stackoverflow.com/questions/222413/find-the-shortest-path-in-a-graph-which-visits-certain-nodes