Closest Points Algorithmus - Teilfelder bei divide und conquer

[topf]

Hallo,

ich habe einen rekursiven Divide-and-Conquer Algorithmus erstellt, der mir soweit so gut die kürzeste euklidische Distanz zwischen zwei oder drei Punkten in einem Teilfeld von einem n-beliebig Großen Feld berechnet.

Nun zu meinem Problem:

Grenzübergreifend kann ja ein Punkt mit einem anderen Punkt verknüpft werden, sodass dadurch die Distanz doch noch kürzer wird.
Nur, wie stell ich das an? Ich habe ja keine wirklichen Grenzen, sondern nur zwei Teilfelder vom Typ ArrayList?
Ich glaube diesen Algorithmus gibts in x-beliebig viel Sprachen bereits fertig, aber ich will nicht stumpf kopieren, sonst versteh ich das ja doch nicht.

Irgendeine Denkhilfe?

 

[tim staeglich]

Hi,

erinnert etwas an das Travelling Salesman problem.

Als eigene Lösung würde ich eine Map anlegen, welche als Value
eine Liste mit Pfad & Distanz enthält.

Da wir hier nicht sortieren, sondern
die kürzeste Strecke suchen, ist der kürzeste aller Pfade das Ziel.

Beispiel:

Pfad1, [ A (2 km)- B (3 km) - C (1 km) - F (Ziel) ] = 6 km
Pfad2, [ A (2 km)- D (1 km) - C (1 km) - F (Ziel) ] = 4 km

Am Schluss nimmst Du die kürzeste Strecke.
Als Maß die Gewichtung der Pfade bis zum Ziel.
Als Orientierung die Knotenpunkte.

Das ist aus dem Ärmel geschossen eine Variante.

Grüße,

Tim