Heuristics: Representation of Search Space and Neighborhoods 5: Unterschied zwischen den Versionen
| [unmarkierte Version] | [unmarkierte Version] |
| Zeile 29: | Zeile 29: | ||
Reiterate the last steps: | Reiterate the last steps: | ||
| − | + | [[Datei:Tsp_neighborhoods_3.png|mini|iteration 3]]<div class="tright" style="clear:none">[[Datei:Tsp_neighborhoods_4.png|mini|iteration 4]]</div><div class="tright" style="clear:none">[[Datei:Tsp_neighborhoods_5.png|mini|iteration 5]]</div><div class="tright" style="clear:none">[[Datei:Tsp_neighborhoods_6.png|mini|iteration 6]]</div> | |
Version vom 29. Juni 2013, 14:20 Uhr
Inhaltsverzeichnis
example
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.
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.
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.
Reiterate the last steps:
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.
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
