Wenn zwei Kacheln tj und tk in einem linearen Konflikt sind, wenn tj und tk in derselben Zeile sind, sind die Zielpositionen von tj und tk beide in dieser Zeile, tj ist rechts von tk und Zielposition von tj ist links von der Zielposition von tk.Lineare Konflikte, die Zulässigkeit verletzen und mich verrückt machen
Der lineare Konflikt fügt der Manhattan-Distanz der beiden in Konflikt stehenden Kacheln mindestens zwei Züge hinzu, indem sie gezwungen werden, sich gegenseitig zu umgeben. Daher fügt die heuristische Funktion für jedes Paar in Konflikt stehender Kacheln Kosten von 2 Zügen hinzu. Die Linar-Konfliktheuristik ist zulässig, aber der Algorithmus, den ich verwende, verletzt manchmal die Zulässigkeit, was bedeutet, dass er pessimistisch ist und nicht unbedingt eine optimale Position findet.
Hier
ist der Code:
private int linearVerticalConflict(State s) {
int state[] = s.getState();
int dimension = (int) Math.sqrt(state.length);
int linearConflict = 0;
int count = 0;
for (int row = 0; row < dimension; row++) {
int max = -1;
for (int column = 0; column < dimension; column++) {
int cellValue = state[count];
count++;
//int cellValue = newState[row][column];
//is tile in its goal row ?
if (cellValue != 0 && (cellValue - 1)/dimension == row) {
if (cellValue > max) {
max = cellValue;
} else {
//linear conflict, one tile must move up or down to
// allow the other to pass by and then back up
//add two moves to the manhattan distance
linearConflict += 2;
}
}
}
}
return linearConflict;
}
private int linearHorizontalConflict(State s) {
int[] state = s.getState();
int dimension = (int) Math.sqrt(state.length);
int linearConflict = 0;
int count = 0;
for (int column = 0; column < dimension; column++) {
int max = -1;
for (int row = 0; row < dimension; row++) {
int cellValue = state[count];
count++;
//is tile in its goal row ?
if (cellValue != 0 && cellValue % dimension == column + 1) {
if (cellValue > max) {
max = cellValue;
} else {
//linear conflict, one tile must move left or right to allow the other to pass by and then back up
//add two moves to the manhattan distance
linearConflict += 2;
}
}
}
}
return linearConflict;
}
Der Algorithmus verletzt Zulässigkeit wenn: sagen, wir sind auf einer Reihe konzentrieren, die die Konfiguration [3, 1, 2]
Nehmen wir an, [1 , 2, 3] ist die Zielkonfiguration.
Die summierte Manhattan Entfernung für das Problem ist: 4 (3 Züge 2 mal, 1 Züge 1 Zeit und 2 Züge 1 Mal) Der lineare Konflikt für die Reihe ist: 4 (1 und 2 sind beide weniger als 3 so + 2 + 2)
, die in einer Gesamt heuristische Schätzung von 8. Ergebnisse [3, 1, 2] kann in 6 bewegt gelöst werden,