|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectde.cm.osm2po.tsp.TspSolverBase
public abstract class TspSolverBase
Abstrakte Basisklasse zum Loesen eines osm2po-TSP,
genauer genommen, einer bestehenden Kostenmatrix.
Liefert vor allem wichtige Basisfunktionalitaeten
fuer init(TspMatrix, Properties, Log)
, so dass
im Prinzip nur TspSolver.solveTour(int[])
ueberschrieben
werden muss. Zudem bietet sie einige simple Loesungsansaetze
und erlaubt ein parametrisiertes Hintereinanderketten selbiger.
Field Summary | |
---|---|
protected static char |
CMD_BRUTEFORCE
|
protected static char |
CMD_GREEDY
|
protected static char |
CMD_MOVE
|
protected static char |
CMD_TWOOPT
|
protected Log |
log
|
protected java.util.Properties |
params
|
protected TspMatrix |
tspMatrix
|
Constructor Summary | |
---|---|
TspSolverBase()
|
Method Summary | |
---|---|
protected float |
calcPartialCosts(int[] tour,
int x)
Berechnet die Summe der Nachbarschafts-Kosten tour[x-1]->tour[x]->tour[x+1]. |
protected float |
calcPartialCosts(int a,
int b,
int c)
Berechnet die Summe der Nachbarschafts-Kosten station[a]->station[b]->station[c]. |
protected float |
calcPartialExtraCosts(int a,
int b,
int c)
Berechnet die absolute Verschlechterung (Umwegkosten) beim Einfuegen einer Station B zwischen A und C. |
protected float |
calcPartialTension(int a,
int b,
int c)
Berechnet die prozentuale Verschlechterung (Dehnung) beim Einfuegen einer Station B zwischen A und C. |
protected float |
calcTourCosts(int[] tour,
float costLimit)
Berechnet die Kosten einer Tour (Besuchsreihenfolge), bricht allerdings bereits mit Float.NaN
ab, sobald ein Kosten-Limit ueberschritten wurde. |
float |
calcTourCosts(int[] tour,
int x,
int y,
float costLimit)
Berechnet die Kosten einer SubTour (Besuchsreihenfolge), bricht allerdings bereits mit Float.NaN
ab, sobald ein Kosten-Limit erreicht wird und somit keine
Verbesserung eintritt. |
protected boolean |
improve(int[] tour,
char cmd)
Wendet eine von mehreren Strategien zum Verbessern einer Tour an. |
protected boolean |
improveBruteForce(int[] tour)
Permutiert ueber alle Kombinationen und ermittelt die kuerzeste Tour. |
protected boolean |
improveGreedy(int[] tour)
Erzeugt eine einfache Greedy-Tour. |
protected boolean |
improveMove(int[] tour)
Laesst jede Station einmal im Kreis wandern und schaut, ob etwas Besseres dabei herauskommt. |
protected boolean |
improveTwoOpt(int[] tour)
Fuehrt solange alle moeglichen 2-Opt-Schritte aus bis keine Verbesserung mehr moeglich ist. |
void |
init(TspMatrix tspMatrix,
java.util.Properties params,
Log log)
Quasi-Konstruktor. |
Methods inherited from class java.lang.Object |
---|
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
Methods inherited from interface de.cm.osm2po.tsp.TspSolver |
---|
solveTour |
Field Detail |
---|
protected static final char CMD_BRUTEFORCE
protected static final char CMD_TWOOPT
protected static final char CMD_GREEDY
protected static final char CMD_MOVE
protected Log log
protected java.util.Properties params
protected TspMatrix tspMatrix
Constructor Detail |
---|
public TspSolverBase()
Method Detail |
---|
public final void init(TspMatrix tspMatrix, java.util.Properties params, Log log)
TspSolver
init
in interface TspSolver
tspMatrix
- TspMatrix
params
- Properties
NULLABLElog
- Log
, NULLABLEprotected boolean improve(int[] tour, char cmd)
tour
- int[] zu modifierende Tour.cmd
- char z.B. CMD_BRUTEFORCE
, erweiterbar!
protected final float calcTourCosts(int[] tour, float costLimit)
Float.NaN
ab, sobald ein Kosten-Limit ueberschritten wurde.
Delegiert an TspMatrix.calcTourCosts(int[], int, int, float)
mit 0 und n-1.
tour
- int[] Besuchsreihenfolge.costLimit
- float Maximale Kosten, Abbruchkriterium.
Float.NaN
public final float calcTourCosts(int[] tour, int x, int y, float costLimit)
Float.NaN
ab, sobald ein Kosten-Limit erreicht wird und somit keine
Verbesserung eintritt.
Delegiert an TspMatrix.calcTourCosts(int[], int, int, float)
tour
- int[] Besuchsreihenfolge.x
- StartIndex innerhalb der Toury
- EndIndex der TourcostLimit
- float Maximale Kosten, Abbruchkriterium.
Float.NaN
protected final float calcPartialCosts(int[] tour, int x)
tour
- int[] Besuchsreihenfolge.x
- int Station
Float.NaN
protected final float calcPartialCosts(int a, int b, int c)
a
- Index der Station A in der Matrixb
- Index der Station Bc
- Index der Station C
Float.NaN
protected final float calcPartialTension(int a, int b, int c)
a
- Index der Station A in der Matrixb
- Index der Station Bc
- Index der Station C
Float.NaN
.protected final float calcPartialExtraCosts(int a, int b, int c)
a
- Index der Station A (0 ist erste Station)b
- Index der Station Bc
- Index der Station C
Float.NaN
.protected final boolean improveGreedy(int[] tour)
tour
- int[] zu modifierende Tour.
Moegliche Werte: [0,1,2,3, ... ,8,0], wenn Ring
aber auch [0,1,2, ... ,9] wenn kein Ring.
protected final boolean improveMove(int[] tour)
tour
- int[] zu modifierende Tour.
Moegliche Werte: [0,1,2,3, ... ,8,0], wenn Ring
aber auch [0,1,2, ... ,9] wenn kein Ring.
protected final boolean improveBruteForce(int[] tour)
tour
- int[] zu modifierende Tour.
Moegliche Werte: [0,1,2,3, ... ,8,0], wenn Ring
aber auch [0,1,2, ... ,9] wenn kein Ring.
protected final boolean improveTwoOpt(int[] tour)
tour
- int[] zu modifierende Tour
Moegliche Werte: [0,1,2,3, ... ,8,0], wenn Ring
aber auch [0,1,2, ... ,9] wenn kein Ring.
|
osm2po-core-5.0.0 (c) December 24 2014 Carsten Moeller - info@osm2po.de | ||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |