Bearbeiten von: Abschnitt [Änderungshistorie]
  Zeilenumbrüche automatisch mache ich selbst mit HTML    

Ich möchte eine Mail an , nachdem mein Vorschlag bearbeitet ist.
  Nachricht zur Änderung:

Input assistance tools (JavaScript): [Link extern intern] [MathML?] [$$?]
[fed-area] [LaTeX-inline] [LaTeX-display] [Tikz] [hide-area][show-area] [Source code [num.]][?]
[Link zurück zum Artikelabschnitt]

Vorschau:
Neuer Abschnitt in Lösen eines Rundreiseproblems durch 9

3 Startheuristiken für symmetrische Rundreiseprobleme angewendet auf ein Problem mit 96 französischen Städten

Startheuristiken werden üblicherweise angewendet, wenn in kurzer Zeit(bei TSP96 in weniger als 1 Sekunde) eine recht gute Lösung gefunden werden soll. Ich habe mit 3 Startheuristiken gearbeitet. Dies sind "Nearest Insertion" (den am nächsten gelegenen Punkt einfügen), "Random Insertion" (einen Zufälligen Punkt einfügen) und "Farthest Insertion" (einen möglichst weit weg von der Route liegenden Punkt einfügen).
Heuristik 1: "Nearest Insertion" liefert bei TSP96 ein ff = 7295. Dies liegt 8.1 % über dem von mir berechneten besten Funktionswert. Die Grafik ist für den Bereich um Paris noch einmal vergrößert dargestellt, da dort viele Städte auf engem Raum sind. Aus 96 Routen wird die Beste ausgewählt. Es wird eine Startstadt gewählt. Dann wird jeweils die von der bisherigen Route am wenigsten entfernte Stadt eingefügt und zwar an der Stelle in der Route, die die geringste Verlängerung der Route ergibt. Dies solange bis alle 96 Städte in der Rundreise liegen.
Heuristik 2 "Random Insertion" liefert bei TSP96 ein ff = 6955 (bei jedem Lauf ein anderer Wert). Dies liegt 3.1 % über dem von mir berechneten besten Funktionswert. Dazu wird aus 96 Routen die Beste ausgewählt. Es wird eine Startstadt gewählt. Dann wird jeweils die von der bisherigen Route eine zufällige Stadt eingefügt und zwar an der Stelle in der Route, die die geringste Verlängerung der Route ergibt. Dies solange bis alle 96 Städte in der Rundreise liegen.
Heuristik 3 "Farthest Insertion" liefert bei TSP96 ein ff = 6928. Dies liegt 2.7 % über dem von mir berechneten besten Funktionswert. Dazu wird aus 96 Routen die Beste ausgewählt. Es wird eine Startstadt gewählt. Dann wird jeweils die von der bisherigen Route am weitesten entfernte Stadt eingefügt und zwar an der Stelle in der Route, die die geringste Verlängerung der Route ergibt. Dies solange bis alle 96 Städte in der Rundreise liegen. Links: de.wikipedia.org/wiki/Farthest-Insertion-Heuristik de.wikipedia.org/wiki/Nearest-Insertion-Heuristik
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2022 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]