Kruskal 및 Prim 알고리즘의 응용

두 알고리즘의 응용 프로그램을 제공 할 수 있습니까? 어디서 어떤 응용 프로그램을 사용할 수 있습니까? 위키 백과 인용Kruskal 및 Prim 알고리즘의 응용

2011-09-06 vini

어딘가에 그들에 대한 언급이 유용 할 것입니다. – Julian

배선의 총 비용을 최소화하는 방식으로 전기 네트워크를 배치하는 방법에 대해 최소 스패닝 트리를 먼저 조사했습니다. 최소 스패닝 트리에서는 모든 노드 (주택)가 최소 비용과 중복성이있는 방식으로 전선으로 전력에 연결됩니다 (모든 전선을 절단하면 전력 그리드가 반드시 두 개로 절단됩니다).

그 이후이 문제는 잘 연구되어 왔고 더 복잡한 알고리즘에서 서브 루틴으로 자주 사용됩니다. 여행 세일즈맨 문제에 대한 근사 솔루션을 찾기위한 Christofides algorithm은 Steiner 트리를 찾는 알고리즘과 마찬가지로 중요한 단계에서이를 사용합니다.

최소 스패닝 트리도 generate mazes까지 사용되었습니다. Kruskal과 Prim의 알고리즘은 모두 이런 방식으로 사용되어 고품질의 미로를 만들어냅니다. 당신이 최소 스패닝 트리 문제, 그 응용, 그 알고리즘의 전체 역사에 관심이 있다면

은 진정으로 훌륭한 논문이 모두 포함 available here있다. 나는 그것을 강력하게 제안 할 것을 제안 할 것이다!

희망이 도움이됩니다. 미로

출처

2011-09-06 17:18:46 templatetypedef

한 예는 새로운 이웃에 케이블을 누워 케이블 TV 회사가 될 것입니다. 특정 경로를 따라 케이블을 매설하도록 제한되어있는 경우 해당 경로로 연결된 점을 나타내는 그래프가 표시됩니다. 이러한 경로 중 일부는 길이가 길거나 케이블을 더 깊게 묻어 야하기 때문에 더 비쌉니다. 이러한 경로는 더 큰 가중치를 갖는 에지로 표시됩니다. 그 그래프에 대한 스패닝 트리 (spanning tree)는주기가없고 모든 집에 연결되는 경로의 부분 집합입니다. 가능한 여러 스패닝 트리가있을 수 있습니다. 최소 스패닝 트리는 총 비용이 가장 적은 트리입니다.

출처 : http://en.wikipedia.org/wiki/Minimum_spanning_tree

출처

2011-09-06 13:20:27 Simone

먼저 당신이 모두 프림의와 크루스 칼의 알고리즘은 그래프에 Minimum spanning Tree을 찾는 데 유용 것을 이해해야합니다. 최소 스패닝 트리의 프로토 타입 응용 프로그램 중 하나는 같은 회사의 다른 사무실을 최소한의 비용으로 연결하는 것입니다.

출처

2011-09-06 13:27:10