Mobile versionIch habe eine einfache Implementierung in Java geschrieben, die einen Zustand des Problems hat, der durch eine Matrix gekennzeichnet ist, die die Fliesen darstellt. Ich kann auch die Grafik aller Staaten automatisch generieren, die den Startzustand geben. Auf der Grafik kann ich dann einen BFS durchführen, um den Pfad zum Zielzustand zu finden. > Ich habe es mit 2x2 Fliesen ausprobiert und es funktioniert. Auch mit 3x3 (es hängt vom Startzustand ab und wie viele Knoten im Diagramm sind). Im Allgemeinen ist dies nicht geeignet. Es funktioniert, aber es ist langsam (manchmal nach einigen Minuten ist es noch nicht beendet und ich beende das Programm). .
Ich kann das Diagramm nicht erstellen. Dies führt zu meinem Hauptproblem: Ich muss den A* -Algorithmus und den Pfadkosten (d. H. Für jeden Knoten den Abstand vom Startzustand) implementieren, aber ich denke, ich kann es zur Laufzeit nicht berechnen. Ich brauche das ganze Diagramm, oder? Weil A* nicht einer BFS -Erkundung des Diagramms folgt, weshalb ich nicht weiß, wie ich den Abstand für jeden Knoten schätzt. Daher weiß ich nicht, wie ich eine A* -Suche ausführt. Br />
Code: Select all
State:< /code> < /p>
private int[][] tiles;
private int pathDistance;
private int misplacedTiles;
private State parent;
public State(int[][] tiles) {
this.tiles = tiles;
pathDistance = 0;
misplacedTiles = estimateHammingDistance();
parent = null;
}
public ArrayList findNext() {
ArrayList next = new ArrayList();
int[] coordZero = findCoordinates(0);
int[][] copy;
if(coordZero[1] + 1 < Solver.SIZE) {
copy = copyTiles();
int[] newCoord = {coordZero[0], coordZero[1] + 1};
switchValues(copy, coordZero, newCoord);
State newState = checkNewState(copy);
if(newState != null)
next.add(newState);
}
if(coordZero[1] - 1 >= 0) {
copy = copyTiles();
int[] newCoord = {coordZero[0], coordZero[1] - 1};
switchValues(copy, coordZero, newCoord);
State newState = checkNewState(copy);
if(newState != null)
next.add(newState);
}
if(coordZero[0] + 1 < Solver.SIZE) {
copy = copyTiles();
int[] newCoord = {coordZero[0] + 1, coordZero[1]};
switchValues(copy, coordZero, newCoord);
State newState = checkNewState(copy);
if(newState != null)
next.add(newState);
}
if(coordZero[0] - 1 >= 0) {
copy = copyTiles();
int[] newCoord = {coordZero[0] - 1, coordZero[1]};
switchValues(copy, coordZero, newCoord);
State newState = checkNewState(copy);
if(newState != null)
next.add(newState);
}
return next;
}
private State checkNewState(int[][] tiles) {
State newState = new State(tiles);
for(State s : Solver.states)
if(s.equals(newState))
return null;
return newState;
}
@Override
public boolean equals(Object obj) {
if(this == null || obj == null)
return false;
if (obj.getClass().equals(this.getClass())) {
for(int r = 0; r < tiles.length; r++) {
for(int c = 0; c < tiles[r].length; c++) {
if (((State)obj).getTiles()[r][c] != tiles[r][c])
return false;
}
}
return true;
}
return false;
}
< /code>
< /p>
Solver:< /code> < /p>
public static final HashSet states = new HashSet();
public static void main(String[] args) {
solve(new State(selectStartingBoard()));
}
public static State solve(State initialState) {
TreeSet queue = new TreeSet(new Comparator1());
queue.add(initialState);
states.add(initialState);
while(!queue.isEmpty()) {
State current = queue.pollFirst();
for(State s : current.findNext()) {
if(s.goalCheck()) {
s.setParent(current);
return s;
}
if(!states.contains(s)) {
s.setPathDistance(current.getPathDistance() + 1);
s.setParent(current);
states.add(s);
queue.add(s);
}
}
}
return null;
}
< /code>
Grundsätzlich ist das, was ich tue:
- Solver < /code> löst < /code> hat einen sortEdSet < /code> hat . Elemente (States- Dequeue und Wiederholung. />- Ich behalte alle besuchten Zustände, damit ich nicht schleife. Z. B.: Wenn ich von A zu B und C gehen kann, und von B kann ich auch zu C gehen, wird es nicht die Kante B-> C geben (da die Pfadkosten für jede Kante 1 sind und A-> B billiger ist als A. -> b-> c).
Aber es funktioniert nicht. Oder zumindest kann es nach ein paar Minuten immer noch keine Lösung finden (und ich denke, in diesem Fall ist viel Zeit). Bevor ein*ausgeführt wird, habe ich das Speicher aufgebaut. Hier sind meine heuristischen Funktionen: < /p>
private int estimateManhattanDistance() {
int counter = 0;
int[] expectedCoord = new int[2];
int[] realCoord = new int[2];
for(int value = 1; value < Solver.SIZE * Solver.SIZE; value++) {
realCoord = findCoordinates(value);
expectedCoord[0] = (value - 1) / Solver.SIZE;
expectedCoord[1] = (value - 1) % Solver.SIZE;
counter += Math.abs(expectedCoord[0] - realCoord[0]) + Math.abs(expectedCoord[1] - realCoord[1]);
}
return counter;
}
private int estimateMisplacedTiles() {
int counter = 0;
int expectedTileValue = 1;
for(int i = 0; i < Solver.SIZE; i++)
for(int j = 0; j < Solver.SIZE; j++) {
if(tiles[j] != expectedTileValue)
if(expectedTileValue != Solver.ZERO)
counter++;
expectedTileValue++;
}
return counter;
}
< /code>
Wenn ich einen einfachen gierigen Algorithmus verwende, funktionieren beide (mit der Distanz von Manhattan in Manhattan sehr schnell (ca. 500 Iterationen, um eine Lösung ungefähr 10k Iterationen). Wenn ich ein* benutze (Bewertung auch den Pfadkost) ist es sehr langsam.public int compare(State o1, State o2) {
if(o1.getPathDistance() + o1.getManhattanDistance() >= o2.getPathDistance() + o2.getManhattanDistance())
return 1;
else
return -1;
}
< /code>
Bearbeiten 3 < /strong>
Es gab dort ein kleiner Fehler. Ich habe es behoben und jetzt funktioniert ein*. Oder zumindest für den 3x3, wenn die optimale Lösung mit nur 700 Iterationen findet. Für den 4x4 ist es immer noch zu langsam. Ich werde es mit IDA* versuchen, aber eine Frage: Wie lange könnte es mit einem* dauern, um die Lösung zu finden? Minuten? Std? Ich habe es 10 Minuten lang gelassen und es endete nicht.