|
|
| (34 dazwischenliegende Versionen von 2 Benutzern werden nicht angezeigt) |
| Zeile 1: |
Zeile 1: |
| − | == Example ==
| + | Anmerkung: Diese Seite wurde nur als Zwischenspeicher genutzt, kann jederzeit von einer anderen Gruppe in Anspruch genommen werden. |
| − | | + | |
| − | | + | |
| − | === Initial state ===
| + | |
| − | | + | |
| − | | + | |
| − | Here we have a classic (strongly simplified) Traveling Salesman Problem which we want to solve or rather which we want to simplify by using the nearest neighbor heuristic. As the nearest neighbor heuristic is just an opening procedure, we will not get a particularly good value of the objective function and therefore no particularly good travelling route itself. But the solution we are going to find will be a more or less good foundation from which one could further improve the solution by using improving procedures. There are no weights on the edges between the nodes shown yet despite them existing already.
| + | |
| − | | + | |
| − | {|
| + | |
| − | |[[Datei:Tsp_neighborhoods_initial_situation.png|mini|initial situation]]
| + | |
| − | |}
| + | |
| − | | + | |
| − | | + | |
| − | === Iteration steps ===
| + | |
| − | | + | |
| − | Here, we randomly pick on of the nodes (in this case node E) to be our starting node from which we will iterate further. The edges from E to any other node is now presented by the lines and the weights are shown as numbers above them. As you can see, the weights differ from edge to edge and because we want to find a preferably short route through all the edges we choose the edge with the smalles weight from E to another node.
| + | |
| − | We are confronted by a ''special case'' of the nearest neighbor heuristic: ''Two edges share the smallest weight''. As the algorithm is not particularly foreshadowing we can now choose randomly between the two smallest edges.
| + | |
| − | | + | |
| − | {|
| + | |
| − | |[[Datei:Tsp_neighborhoods_1.png|mini|after choosing the first node]]
| + | |
| − | |}
| + | |
| − | | + | |
| − | | + | |
| − | We chose node C and are now confronted by new edges between C and all other nodes we have not been to yet. The shortest route beginning from C would now be to A.
| + | |
| − | {|
| + | |
| − | |[[Datei:Tsp_neighborhoods_2.png|mini|iteration 2]]
| + | |
| − | |}
| + | |
| − | | + | |
| − | | + | |
| − | | + | |
| − | Iterate the last steps:
| + | |
| − | | + | |
| − | {|
| + | |
| − | |[[Datei:Tsp_neighborhoods_3.png|mini|iteration 3]]||[[Datei:Tsp_neighborhoods_4.png|mini|iteration 4]]
| + | |
| − | |-
| + | |
| − | |[[Datei:Tsp_neighborhoods_5.png|mini|iteration 5]]||[[Datei:Tsp_neighborhoods_6.png|mini|iteration 6]]
| + | |
| − | |}
| + | |
| − | | + | |
| − | | + | |
| − | This goes on until we reach the final node that has not been visited yet, in this case node F. Now, as we have a Travelling Salesman Problem, we just need to close the cycle by connecting the last node with the start node.
| + | |
| − | | + | |
| − | {|
| + | |
| − | |[[Datei:Tsp_neighborhoods_final_solution.png|mini|final solution]]
| + | |
| − | |}
| + | |
| − | | + | |
| − | === Summary ===
| + | |
| − | | + | |
| − | | + | |
| − | With this, the algorithm from the nearest neighbor heuristic has ended and we found an opening travelling route from which we can further improve our route. The last step would now be the accumulation of the weights on the travelled edges and we got the value of our route.
| + | |
| − | | + | |
| − | In this case: 2+2+3+5+1+6 = 19
| + | |
| − | | + | |
| − | The solution we want to present is: '''E-C-A-B-D-F-E'''
| + | |
Anmerkung: Diese Seite wurde nur als Zwischenspeicher genutzt, kann jederzeit von einer anderen Gruppe in Anspruch genommen werden.
