Zitat:

P.S. Diese Lösung ist schnell, aber nicht perfekt Annahme: Schiff B steht näher zu Schiff X als Schiff A. Schiff A sucht und findet Weg zu Schiff X als kürzesten Weg. Schiff B sucht seinen kürzesten Weg. Der Weg zu Schiff B wird aber nicht gefunden, da Schiff A den Weg zu Schiff X bereits für sich als Lösung reserviert hat. Wenn Schiff B seinen kürzesten Weg sucht, steht Schiff X nicht mehr zur Auswahl. Eventuell kannst Du aber mit diesem Nachteil leben, da insgesamt betrachtet zwar keine optimale aber eine noch eine gute Lösung gefunden wird. Wenn Du nicht mit diesem Nachteil leben kannst oder willst, dann musst Du im ersten Durchlauf für [u]jedes Schiff den kürzesten Weg finden und untersuchen, ob es Überschneidungen gibt (also, ob ein Zielschiff von zwei oder mehr Schiffen als kürzeste Lösung gefunden wird). Aus den Überschneidungen wiederum wählst Du die Variante mit dem kürzesten Weg. Das ist dann Deine Lösung für das erste Schiff (also in obigem Beispiel B und nicht A). Erst dann reduzierst Du die Gesamtmenge um die gefundene Lösung. Im nächsten Lauf dann das gleiche nochmal usw. Diese Lösung wäre dann optimal. Gruß, Michael

Zitat:

ob es Überschneidungen gibt (also, ob ein Zielschiff von zwei oder mehr Schiffen als kürzeste Lösung gefunden wird). Aus den Überschneidungen wiederum wählst Du die Variante mit dem kürzesten Weg.

Zitat:

Erst dann reduzierst Du die Gesamtmenge um die gefundene Lösung.