Hallo Zusammen!
Ich habe folgendes Problem:
Gegeben ist eine beliebige n x m-Matrix, mit n,m > 1, bestehend aus natürlichen Zahlen von einschließlich 1 bis einschließlich 7, oder gar keinem Wert. Beispielsweise sei folgende Matrix gegeben:
1 1 1
2 2 2
Man kann einen der Einträge in der Matrix um zwei Erhöhen bzw. verringern, wodurch sich alle direkten horizontalen und vertikalen Nachbarn um einen erhöhen bzw. verringern. Beispielsweise kann ein Zug wie folgt aussehen:
3 2 1
3 2 2
Das Ziel ist es, alle Werte in der Matrix gleich zu kriegen. Beim einem anderen Beispiel wären dies folgende zwei Züge:
1 3 5 ->
3 4 5 -> 5 5 5
Erlaubt sind dabei beliebig viele Züge. Sollte der Wert selber oder einer der Nachbar-Werte bei einem Zug über 7 oder unter 1 kommen, ist der Zug ungültig und es passiert nichts mit den Werten.
Ich möchte nun gerne einen "Löser" für diese Regeln implementieren und dabei die minimale Anzahl an Züge zum lösen und die hierbei benötigten Züge herausfinden und setze dabei auf einfaches ausprobieren aller Möglichkeit. Schnell stellte ich fest, dass mit steigender "maximalen Suchtiefe" die Anzahl der Durchläufe schnell wächst und bereits nach einer maximalen Suchtiefe von 7 Zügen und einem 2x3 Feld, etwa 19. Millionen Durchgänge benötigt werden. Dabei habe ich schon optimiert, dass auf dem selben Feld nicht hintereinander erhöht/verringert werden kann, da dies ja den vorherigen Zug irrelevant macht. Der Code sieht folgendermaßen aus:
|
Java-Quelltext
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
|
public void solve() {
int currentDepth = 0;
GridSolution solution = new GridSolution();
for (int newY = 0; newY < gridCells.length; newY++) {
for (int newX = 0; newX < gridCells[newY].length; newX++) {
if (gridCells[newY][newX].getType() == GridCell.Type.NONE) continue;
_solve(gridCells, newX, newY, Direction.INCREASE, currentDepth, solution);
_solve(gridCells, newX, newY, Direction.DECREASE, currentDepth, solution);
}
}
Collections.sort(solutions);
}
private void _solve(GridCell[][] grid, int x, int y, Direction direction, int depth, GridSolution solution) {
this.iterations++;
GridCell[][] copy = Grid.CopyGrid(grid);
GridSolution copySolution = new GridSolution(solution);
if (Grid.checkSolved(grid)) {
solutions.add(copySolution);
return;
}
if (direction == Direction.INCREASE) {
if(!Grid.increase(copy, x, y)) {
return;
}
} else {
if(!Grid.decrease(copy, x, y)) {
return;
}
}
copySolution.AddTurn(new GridTurn(x, y, direction));
depth += 1;
if (depth > MAX_DEPTH) {
return;
}
for (int newY = 0; newY < gridCells.length; newY++) {
for (int newX = 0; newX < gridCells[newY].length; newX++) {
if (gridCells[newY][newX].getType() == GridCell.Type.NONE) continue;
if (newY != y && newX != x && direction != Direction.DECREASE) {
} else {
_solve(copy, newX, newY, Direction.INCREASE, depth, copySolution);
}
if (newY != y && newX != x && direction != Direction.INCREASE) {
} else {
_solve(copy, newX, newY, Direction.DECREASE, depth, copySolution);
}
}
}
}
|
Was ich mir nun als nächstes dachte ist, dass ich ja einfach alle "Zustände", die bereits einmal gelöst worden sind, speichern kann und diese in Zukunft ignorieren. Das sollte dann ja einen Schneeballeffekt haben und die Anzahl der Durchgänge drastisch verringern und vor allem den exponentiellen Anstieg der Durchgänge mit erhöhter Suchtiefe stoppen. Implementieren wollte ich das ganze durch folgenden Code am Anfang der _solve-Methode
|
Java-Quelltext
|
1
2
3
4
5
6
7
8
9
10
11
|
//"Hash", to prevent deep copy comparing
String hash = direction.toString() + Grid.createGridCellHash(grid);
//Check if this state was already parsed
for (String parsedGridHash : parsedStatesHashes) {
if (parsedGridHash != "" && parsedGridHash.equals(hash))
return;
}
//After completely parsing this state, add it to parsed states
parsedStatesHashes.add(hash);
|
Die Anzahl der Durchgänge ist so von 19.000.000 auf gerade einmal 8 gesunken. Jedoch wird die richtige Lösung auch nicht mehr erkannt. Das lag dann natürlich daran, dass ich Zustände bereits als gelöst gespeichert habe, bevor sie tatsächlich gelöst wurden. Also packte ich das "parsedStatesHashes.add(hash)" an das Ende der _solve Methode. Nun sind es 48 Durchläufe, was mir logisch erscheint. Jedoch ist wieder keine Lösung dabei, obwohl bei der selben Matrix unoptimiert die perfekte Lösung gefunden wird.
Mir erscheint nun selber kein Logikfehler mehr, der mir unterlaufen ist. Filtere ich unabsichtlich nun zu früh eventuell korrekte Lösungen oder übersehe ich irgendeinen Denkfehler in meinem Code? Ich weiß, dass das viele Objekt-Erstellen sehr unperformant ist, jedoch fällt mir jedoch hierzu momentan keine Lösung ein. Außerdem hat das Überprüfen mit Profilern ergeben, dass dies nicht der Bottleneck ist, sondern tatsächlich das Milliardenfache durchlaufen.
Ich hoffe, dass jemand mir einen Tipp geben kann, der meine Lösung performanter und realistisch einsetzbar macht.