Anmerkungen und Erläuterungen


 

Zur Mindestkantenregel:

Das Ziel, bei der begrenzten Enumeration möglichst frühzeitig die Berechnung abbrechen zu können, wird dadurch verbessert, dass man nicht die Gesamtlänge der Kanten, sondern nur ihre Abweichungen, d.h. die Differenz von der kleinsten Kantenlänge betrachtet. Üblicherweise wird dazu jeder Zahlenwert der Ausgangsmatrix um die kleinste Kantenlänge aller Kanten reduziert.

Will man die Ausgangsmatrix nicht verändern, kann man auch bei jedem Zwischenergebnis für die noch ausstehenden Kanten jeweils die kleinste Kantenlänge hinzuzählen und erst dann das Ergebnis mit dem bereits früher gefundenen kleinsten Teilgraphen vergleichen. Ist das Ergebnis größer als dieser Teilgraph, dann kann an dieser Stelle die Berechnung abgebrochen werden. Im Beispiel ist die kleinste Kantenlänge 220 km lang, so dass für jede noch ausstehende Kante dieser Mindestwert hinzugerechnet werden kann.

Nachdem jetzt bei der hier vorgestellten Lösung jedem Kantenplatz die relevanten Kanten zugeordnet werden können, muss die minimale Kantenlänge nur noch aus diesen Kanten und nicht mehr aus allen Kanten ermittelt werden. Es werden also in diesem Beispiel nicht mehr generell für jede ausstehende Kante 220 km sondern individuell für jeden einzelnen Kantenplatz der Mindestwert der dort möglichen Kanten berücksichtigt. Dieser Wert ist zumindest für die wichtigen ersten Kantenplätze höher. 

Beide o.a. Verfahren zur Ermittlung des abzuziehenden Wertes sind "mit Zurücklegen". Besser sind Verfahren "ohne Zurücklegen", denn jede Kante kann zwar ggf. an mehreren Kantenplätzen stehen, innerhalb eines Teilgraphen jedoch immer nur an einem Platz. Ohne Zurücklegen und ohne Berücksichtigung des Kantenplatzes ist die Ermittlung des abzuziehenden Wertes einfach: Man zählt für jede noch ausstehende Kante die jeweils kleinsten Kantenlängen aller Knoten zusammen: 220 + 256 + 280 + 297 + 305 + 312 + 337 + 367 + 371+ 383 + 407+ 409 ........

Ohne Zurücklegen aber mit Berücksichtigung des Kantenplatzes (und damit implizit auch mit Berücksichtigung der Reihenfolgeregel, dass die Folgekante immer mit einer größeren Knoten-Nr. beginnen  muss) wird die bisher einfache Berechnung schwieriger. Der abzuziehende Wert muss für jeden Kantenplatz aus den kleinsten Kanten der noch ausstehenden Kantenplätzen getrennt berechnet werden. 

Diese ggf. manuell durchzuführende Berechnung bringt schon gute Werte Der optimalen Wert je Kantenplatz läßt sich in diesem Beispiel aber nur maschinell berechnen, weil bei der Berechnung nicht nur Kanten mit der kleinsten Kantenlängen je Knoten zu berücksichtigen sind.

 

 

Kantenplatz im Teilgraph

  1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13.
mit Zurückl.  
je 220 km 2640 2420 2200 1980 1760 1540 1320 1100 880 660 440 220 0
Platz einzeln 3642 3259 2682 2275 1868 1612 1356 1100 880 660 440 220 0
 
ohne Zurück.  
kl. Kanten 3944 3535 3128 2745 2374 2007 1670 1358 1053 756 476 220 0
Platz einzeln 4150 3767 3190 2781 2374 2007 1670 1358 1053 756 500 220 0
 
programmiert 5518 4869 4232 3464 2915 2403 1994 1542 1093 756 500 220 0