Мобильная версияЯ написал простую реализацию на Java, состояние которой характеризуется матрицей, представляющей плитки. Я также могу автоматически создать график всех состояний, дающих начальное состояние. Тогда на графе я могу выполнить BFS, чтобы найти путь к целевому состоянию.
Но проблема в том, что у меня заканчивается память, и я даже не могу создать весь граф.
Я попробовал с плитками 2x2, и это работает. Также с некоторыми 3x3 (это зависит от начального состояния и количества узлов в графе). Но в целом этот способ не подходит.
Поэтому я попробовал генерировать узлы во время выполнения во время поиска. Это работает, но медленно (иногда через несколько минут оно все еще не закончилось, и я закрываю программу).
Кстати: я даю в качестве стартового состояния только решаемые конфигурации и не создаю дублированные состояния .
Поэтому я не могу построить график. Это приводит к моей основной проблеме: мне нужно реализовать алгоритм A*, и мне нужна стоимость пути (т. е. для каждого узла расстояние от начального состояния), но я думаю, что не могу вычислить его во время выполнения. Мне нужен весь график, верно? Поскольку A* не следует исследованию графа BFS, поэтому я не знаю, как оценить расстояние для каждого узла. Следовательно, я не знаю, как выполнить поиск A*.
Есть предложения?
ИЗМЕНИТЬ
Код: Выделить всё
State:Код: Выделить всё
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;
}
Код: Выделить всё
Solver:Код: Выделить всё
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;
}
- Решение имеет SortedSet . Элементы (
Код: Выделить всё
States- Даю стартовую конфигурацию и ищу всех преемников.
- Если преемник еще не посещался (т.е. если он не находится в глобальном наборе состояний) я добавляю его в очередь и в состояния, устанавливая текущее состояние в качестве его родителя и путь к родительскому элементу + 1< /code> в качестве стоимости пути.
- Извлеките из очереди и повторите.
Я думаю, это должно сработать, потому что:
- Я сохраняю все посещенные состояния, поэтому не зацикливаюсь.
- Кроме того, не будет никаких бесполезных ребер, потому что я сразу сохраняю преемников текущего узла. Например: если из A я могу пойти в B и C, а из B я также могу пойти в C, ребра B->C не будет (поскольку стоимость пути равна 1 для каждого ребра и A->B дешевле, чем A ->B->C).
- Каждый раз я выбираю расширение пути с минимальным f(n) в соответствии с A*.
Но это не работает. Или, по крайней мере, через несколько минут он все еще не может найти решение (и я думаю, что в этом случае это много времени).
Если я попытаюсь создать древовидную структуру перед выполнением A* мне не хватает памяти для его построения.
РЕДАКТИРОВАТЬ 2
Вот мои эвристические функции:
Код: Выделить всё
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[i][j] != expectedTileValue)
if(expectedTileValue != Solver.ZERO)
counter++;
expectedTileValue++;
}
return counter;
}
Компараторы такие:
Код: Выделить всё
public int compare(State o1, State o2) {
if(o1.getPathDistance() + o1.getManhattanDistance() >= o2.getPathDistance() + o2.getManhattanDistance())
return 1;
else
return -1;
}
Было небольшая ошибка. Я исправил это, и теперь A* работает. Или, по крайней мере, для 3x3 if находит оптимальное решение всего за 700 итераций. Для 4x4 это все еще слишком медленно. Я попробую с IDA*, но один вопрос: сколько времени понадобится с A*, чтобы найти решение? Минуты? Часы? Я оставил это на 10 минут, и это не закончилось.
Подробнее здесь: https://stackoverflow.com/questions/120 ... le-in-java
