Мобильная версияЯ написал простую реализацию в Java, которая имеет состояние проблемы, характеризующуюся матрицей, представляющей плитки. Я также могу автоматически генерировать график всех состояний, дающих начальное состояние. На графике я могу сделать BFS, чтобы найти путь к состоянию цели. Также с около 3x3 (это зависит от начального состояния и сколько узлов находится на графике). Но в целом этот путь не подходит.
, поэтому я попытался генерировать узлы во время выполнения во время поиска. Это работает, но это медленное (иногда через несколько минут он все еще не закончился, и я заканчиваю программу).
BTW: я даю только начальные конфигурации и не создаю дублированные состояния.
Так что я не могу создать график. Это приводит к моей основной проблеме: я должен реализовать алгоритм A*, и мне нужна стоимость пути (то есть для каждого узла расстояние от начального состояния), но я думаю, что я не могу рассчитать его во время выполнения. Мне нужен весь график, верно? Потому что* не следует за изучением графа BFS, поэтому я не знаю, как оценить расстояние для каждого узла. Следовательно, я не знаю, как выполнить поиск a*.
Есть предложения?
Код: Выделить всё
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>
По сути, вот что я делаю:
- Solver < /code> Solve < /code> имеет сортируемый шаг < /code>. Элементы (States- I даю начальную конфигурацию и просматривает все успешные. Уже побывал (то есть, если он не находится в глобальных состояниях набора < /code>), я добавляю его в очередь и в состояния < /code>, устанавливая текущее состояние как его путь родителя и родителя + 1 < /code> как его путь. Цикл. E.g.: if from A I can go to B and C, and from B I could also go to C, there won't be the edge B->C (since path cost is 1 for each edge and A->B is cheaper than A->B->C).
- Each time I choose to expand the path with the minimum f(n), accordin to A*.
But it does не работать. Или, по крайней мере, через несколько минут он все еще не может найти решение (и я думаю, что в этом случае много времени).
, если я пытаюсь создать структуру дерева, прежде чем выполнять*, у меня все накапливается. />
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>
Если я использую простой жадный алгоритм, они оба работают (с использованием манхэттенского расстояния действительно быстро (около 500 итераций, чтобы найти решение), в то время как с количеством неуместных плиток он занимает около 10 тысяч итераций). Если я использую* (оценку также стоимость пути), это действительно медленно.
компараторы такие: < /p>
public int compare(State o1, State o2) {
if(o1.getPathDistance() + o1.getManhattanDistance() >= o2.getPathDistance() + o2.getManhattanDistance())
return 1;
else
return -1;
}
< /code>
edit 3 < /strong>
Была небольшая ошибка. Я исправил это, а теперь* работает. Или, по крайней мере, для 3x3, если находит оптимальное решение только с 700 итерациями. Для 4x4 это все еще слишком медленно. Я попробую с Ida*, но один вопрос: сколько времени может потребоваться с*, чтобы найти решение? Минуты? Часы? Я оставил его на 10 минут, и это не закончилось.
Подробнее здесь: https://stackoverflow.com/questions/120 ... le-in-java
