Modifier and Type | Class and Description |
---|---|
static class |
TspUtils.ProgressCounter
Referenz-Zaehler, der faktisch unendlich hohe Zahlen inkrementiert.
|
static class |
TspUtils.ProgressEvent |
static interface |
TspUtils.ProgressEventConsumer |
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.
|
static int |
MININ1 |
static int |
MININ2 |
static int |
MINOUT1 |
static int |
MINOUT2 |
Modifier and Type | Method and Description |
---|---|
static long[][] |
calcInOutMins12(long[][] mx) |
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[] |
create2poTour(long[][] mx) |
static int[] |
createBestGreedyRingTour(long[][] mx) |
static int[] |
createBestGreedyTour(long[][] mx,
boolean forRing) |
static int[][] |
createGreedyRingTours(long[][] mx,
boolean shift0ToLeft) |
static int[] |
createGreedyTour(long[][] mx) |
static int[] |
createGreedyTour(long[][] mx,
int[] initialTour) |
static int[] |
createInitialRingTour(long[][] mx) |
static int[] |
createInitialTour(long[][] mx,
boolean asRing) |
static int[] |
createInsertionTour(long[][] mx) |
static int[] |
createPermuteTour(long[][] mx) |
static int[] |
createSimulatedAnnealingTour(long[][] mx) |
static int[] |
createStarTour(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[] |
createTwoOptTour(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 |
isLastNTourOk(long[][] mx,
int[] tour,
int x1,
int n) |
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) |
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 int MINOUT1
public static final int MINOUT2
public static final int MININ1
public static final int MININ2
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 long[][] calcInOutMins12(long[][] mx)
public static boolean isLast5TourOptimal(long[][] mx, int[] tour, int x1)
x1
- int aktuelle Permutation-Tiefe. Pruefung erfolgt bis tour[x1] als gesetztes Ziel.mx
- long[][] Adjazenz-Matrixtour
- int[] aktuelle Tour-Reihenfolgepublic static boolean isLastNTourOk(long[][] mx, int[] tour, int x1, int n)
public static int[] createGreedyTour(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[] createStarTour(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-ReihenfolgecreateStarTour(long[][])
public static int[] createTwoOptTour(long[][] mx)
public static int[] improveTwoOpt(long[][] mx, int[] initialTour)
public static int[] createInsertionTour(long[][] mx)
public static int[] improveInsertion(long[][] mx, int[] initialTour)
public static int[] createSimulatedAnnealingTour(long[][] mx)
public static int[] improveSimulatedAnnealing(long[][] mx, int[] initialTour)
public static int[] create2poTour(long[][] mx)
public static int[] improve2po(long[][] mx, int[] initialTour)
public static int[] createPermuteTour(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)