Modifier and Type | Class and Description |
---|---|
static class |
TspUtils.Random
Partielle Kopie von
TspUtils.Random ohne AtomicLong . |
Modifier and Type | Field and Description |
---|---|
static java.text.DateFormat |
DF |
static long |
FINITY |
static int |
FINITY_BITS |
static long |
INFINITY
Konvention fuer den Wert INFINITY.
|
Modifier and Type | Method and Description |
---|---|
static long |
calcSubTourCosts(int[] ts,
long[][] mx,
int x1,
int x2) |
static long |
calcTourCosts(int[] ts,
long[][] mx) |
static long |
calcTourCosts(int[] ts,
long[][] mx,
long limit) |
static long[][] |
copyMatrix(long[][] mx) |
static int[] |
create2poRingTour(long[][] mx) |
static int[] |
createBestGreedyRingTour(long[][] mx) |
static int[] |
createBestGreedyTour(long[][] mx,
boolean forRing) |
static int[] |
createGreedyRingTour(long[][] mx) |
static int[][] |
createGreedyRingTours(long[][] mx,
boolean shift0ToLeft) |
static int[] |
createGreedyTour(long[][] mx,
int[] initialTour) |
static int[] |
createInitialRingTour(long[][] mx) |
static int[] |
createInitialTour(long[][] mx,
boolean asRing) |
static int[] |
createInsertionRingTour(long[][] mx) |
static int[] |
createPermuteRingTour(long[][] mx) |
static int[] |
createSimulatedAnnealingRingTour(long[][] mx) |
static int[] |
createStarRingTour(long[][] mx)
Erzeugt eine Sternen-Ring-Tour auf Grundlage einer Adjazenz-Matrix.
|
static int[] |
createStarTour(long[][] mx,
int[] initialTour)
Erzeugt eine Tour mit Zwischenstationen sortiert nach
dem Abstand von Start und Ziel.
|
static int[] |
createSubTour(int[] tour,
int x1,
int x2,
boolean makeRing,
boolean startAt0)
Erzeugt aus einer Tour eine Sub-Tour.
|
static int[] |
createTwoOptRingTour(long[][] mx) |
static long |
findMaxValue(long[] arr) |
static long |
findMaxValue(long[][] arr) |
static int[] |
improve2po(long[][] mx,
int[] initialTour) |
static int[] |
improveInsertion(long[][] mx,
int[] initialTour) |
static int[] |
improvePermute10(long[][] mx,
int[] initialTour) |
static int[] |
improveSimulatedAnnealing(long[][] mx,
int[] initialTour) |
static int[] |
improveTwoOpt(long[][] mx,
int[] initialTour) |
static boolean |
isInfinite(long v) |
static boolean |
isLast5TourOptimal(long[][] mx,
int[] tour,
int x1)
Schnellpruefung, ob die letzten 0-1234-5 Stationen ueber 1234 permutiert (4!)
|
static boolean |
isSubTourOptimal(long[][] mx,
int[] tour,
int x1,
int x2) |
static boolean |
isSymmetryGiven(long[][] mx)
Berechnet, ob die Matrix symmetrisch ist.
|
static boolean |
isTriangleInequalityGiven(long[][] mx)
Berechnet ob die Dreiecksungleichung dieser Matrix erfuellt ist.
|
static int[] |
optimizePermuteTour(long[][] mx,
int[] tour)
Optimiert eine Tour mittels naiver Permuation.
|
static java.lang.String |
prettyPrintArray(int[] arr,
int colwidth) |
static java.lang.String |
prettyPrintArray(long[] arr,
int colwidth) |
static java.lang.String |
prettyPrintMatrix(long[][] mx) |
static int[] |
sortStationsByDistanceFrom(long[][] mx,
int source) |
public static final java.text.DateFormat DF
public static final int FINITY_BITS
public static final long INFINITY
public static final long FINITY
public static final boolean isInfinite(long v)
public static long[][] copyMatrix(long[][] mx)
public static int[] createInitialTour(long[][] mx, boolean asRing)
public static int[] createInitialRingTour(long[][] mx)
public static long calcTourCosts(int[] ts, long[][] mx)
public static long calcTourCosts(int[] ts, long[][] mx, long limit)
public static long calcSubTourCosts(int[] ts, long[][] mx, int x1, int x2)
public static boolean isTriangleInequalityGiven(long[][] mx)
mx
- long[][] Matrix-Kosten. PRE: Anzahl Zeilen gleich Spalten!public static boolean isSymmetryGiven(long[][] mx)
mx
- long[][] Matrix-Kosten. PRE: Anzahl Zeilen gleich Spalten!public static int[] createSubTour(int[] tour, int x1, int x2, boolean makeRing, boolean startAt0)
tour
- int[] Tourx1
- int Start-Index der Tourx2
- int End-Index der Tour (inklusive)makeRing
- boolean true: Ziel gleich Start setzenstartAt0
- boolean true: Start bleibt Index[0] der Originaltour
Beispielsweise liefert die Tour 0,1,2,3,4,5,0
bei Aufruf mit x1=2 und x2=4 die folgenden Resultate fuer
makeRing
und startAt0
public static boolean isLast5TourOptimal(long[][] mx, int[] tour, int x1)
TspS
mit Greedy als Start-Tour fuer Fri26 wird hiemit sogar um Faktor 5 beschleunigt.x1
- int aktuelle Permutation-Tiefe. Pruefung erfolgt bis tour[x1] als gesetztes Ziel.mx
- long[][] Adjazenz-Matrixtour
- int[] aktuelle Tour-Reihenfolgepublic static int[] createGreedyRingTour(long[][] mx)
public static int[] createGreedyTour(long[][] mx, int[] initialTour)
public static int[] createBestGreedyRingTour(long[][] mx)
public static int[] createBestGreedyTour(long[][] mx, boolean forRing)
public static int[] createStarRingTour(long[][] mx)
mx
- long[][] Adjazenz-Matrix (Diagonale: 0, Nicht erreichbar: INFINITY
)createStarTour(long[][], int[])
public static int[] createStarTour(long[][] mx, int[] initialTour)
mx
- long[][] Adjazenz-Matrix (Diagonale: 0, Nicht erreichbar: INFINITY
)initialTour
- int[] aktuelle Tour-ReihenfolgecreateStarRingTour(long[][])
public static int[] sortStationsByDistanceFrom(long[][] mx, int source)
public static int[] createTwoOptRingTour(long[][] mx)
public static int[] improveTwoOpt(long[][] mx, int[] initialTour)
public static int[] createInsertionRingTour(long[][] mx)
public static int[] improveInsertion(long[][] mx, int[] initialTour)
public static int[] createSimulatedAnnealingRingTour(long[][] mx)
public static int[] improveSimulatedAnnealing(long[][] mx, int[] initialTour)
public static int[] create2poRingTour(long[][] mx)
public static int[] improve2po(long[][] mx, int[] initialTour)
public static int[] createPermuteRingTour(long[][] mx)
public static int[] optimizePermuteTour(long[][] mx, int[] tour)
mx
- long[][] Adjazenz-Matrix (Diagonale: 0, Nicht erreichbar: INFINITY
)tour
- int[] aktuelle Tour-Reihenfolgenull
wenn bereits optimal.public static boolean isSubTourOptimal(long[][] mx, int[] tour, int x1, int x2)
public static int[] improvePermute10(long[][] mx, int[] initialTour)
public static java.lang.String prettyPrintArray(long[] arr, int colwidth)
public static java.lang.String prettyPrintArray(int[] arr, int colwidth)
public static java.lang.String prettyPrintMatrix(long[][] mx)
public static long findMaxValue(long[][] arr)
public static long findMaxValue(long[] arr)
public static int[][] createGreedyRingTours(long[][] mx, boolean shift0ToLeft)