Heuristics: Minimal Spanning Tree 2: Unterschied zwischen den Versionen
[unmarkierte Version] | [unmarkierte Version] |
Cunin (Diskussion | Beiträge) (→Example) |
Cunin (Diskussion | Beiträge) (→Example) |
||
Zeile 1: | Zeile 1: | ||
− | |||
− | |||
+ | == Theory == | ||
+ | |||
+ | == Example == | ||
+ | I would like to visit some of my friends in France this summer. But the road aren’t free in this country. Here are the cities I’d like to go and the cost of the use of every path. | ||
+ | |||
+ | To select the minimal cost path to join all of these, the construction of a minimal spanning is a solution to my problem. | ||
+ | I can use either the kruskal's algorithm or the prim's algorithm to create it. Here is my solution with the minimal spanning tree. | ||
+ | (To see the contruction of a minimal spanning tree in detail, go to "Detailed solution process with explanation") | ||
+ | |||
+ | == '''Presentation of a problem''' == | ||
+ | |||
+ | Consider the following communications network (Distance as evaluation of the edges) | ||
[[Datei:Folie1.JPG]] | [[Datei:Folie1.JPG]] | ||
− | + | We want to connect every system (node) with the others in the way that the distance between every system is minimal and there is only one way to go from one to another system. To do that, we can use 2 algorithms that have been explain before : Kruskal's and Prim's algorithm. | |
+ | |||
+ | == Detailed solution process with explanation == | ||
'''Kruskal's algorithm''' : With the Kruskal‘s algorithm, we have to list the existing link of our network in increrasing order. | '''Kruskal's algorithm''' : With the Kruskal‘s algorithm, we have to list the existing link of our network in increrasing order. | ||
Zeile 24: | Zeile 36: | ||
[[Datei:Prim8.JPG]] | [[Datei:Prim8.JPG]] | ||
[[Datei:Prim9.JPG]] | [[Datei:Prim9.JPG]] | ||
+ | |||
+ | |||
+ | == Sources == | ||
+ | Radin, R. L. (1998): Optimization in Operations Research. New Jersey, Prentice Hall, pp 522-523. | ||
+ | |||
+ | W.Domschke,et al.,Übungen und Fallbeispiele zum Operations Research, 5th edition, 2005. |
Version vom 27. Juni 2013, 15:01 Uhr
Inhaltsverzeichnis
Theory
Example
I would like to visit some of my friends in France this summer. But the road aren’t free in this country. Here are the cities I’d like to go and the cost of the use of every path.
To select the minimal cost path to join all of these, the construction of a minimal spanning is a solution to my problem. I can use either the kruskal's algorithm or the prim's algorithm to create it. Here is my solution with the minimal spanning tree. (To see the contruction of a minimal spanning tree in detail, go to "Detailed solution process with explanation")
Presentation of a problem
Consider the following communications network (Distance as evaluation of the edges)
We want to connect every system (node) with the others in the way that the distance between every system is minimal and there is only one way to go from one to another system. To do that, we can use 2 algorithms that have been explain before : Kruskal's and Prim's algorithm.
Detailed solution process with explanation
Kruskal's algorithm : With the Kruskal‘s algorithm, we have to list the existing link of our network in increrasing order.
Sources
Radin, R. L. (1998): Optimization in Operations Research. New Jersey, Prentice Hall, pp 522-523.
W.Domschke,et al.,Übungen und Fallbeispiele zum Operations Research, 5th edition, 2005.