Berechnen Sie alle möglichen Routen zwischen Knoten, wo alle Knoten nur einmal berührt werden? (Reisender Verkäufer)

Question

Ich versuche, ein Travelling-Salesman-artiges Programm (in Java) zu entwickeln und versuche, die Logik für einen bestimmten Teil herauszufinden, einen Brute-Force-Ansatz zur Berechnung der effizientesten Route zwischen einem Knotensatz (Cities), bei dem jeder Knoten nur einmal berührt wird.

Ich habe eine City-Klasse mit den X/Y-Koordinaten definiert und habe ein Array von City-Instanzen und eine Gitterklasse, um das Gitter zu zeichnen. Städte sind auf einem Raster und nummeriert 0-i für ihren Index in der Stadt Array
(Im Beispiel Raster gibt es 4 Städte definiert):

· · · · · · · · · · · · · · · · 
· · · · · · · · · 1 · · · · · · 
· · 0 · · · · · · · · · · · · · 
· · · · · · · · · · · 3 · · · · 
· · · · · · 2 · · · · · · · · · 
· · · · · · · · · · · · · · · · 
· · · · · · · · · · · · · · · · 

Es gibt viele Wege sichtbar schon (ich glaube 4 ! = 24):

• 0-1-2-3
• 0-2-1-3
• 2-0-1-3
• 2-3-1-0
• etc ..

Gibt es eine einfache iterative/rekursive Methode jeden möglichen Weg zu erhalten, eine Reihe von Städten gegeben und ihre Koordinaten, die ich den Abstand bestimmen kann und die effizienteste Route Liste (s)?

Answer 1

es ist Faculty(n)/2 wenn Ihre Entfernungen ungerichtet sind oder Faculty(n) wenn Ihre Verbindungen gerichtet sind (dh: Abstand a -> b unterscheidet sich von b -> a). Es heißt Permutation

nicht vergessen 13! = 6227020800 und mehr als Integer.max_value, auch 13!/2 ist mehr!