Я работаю над заданием по программированию (в Java), чтобы решить вещь из пятнадцати загадок . Первая часть - использовать поиск в глубину, чтобы найти решение. Я хочу, чтобы он мог решить сколь угодно большую загадку, чтобы весь граф пространства состояний не умещался в памяти. Вместо этого алгоритм будет хранить список исследованных состояний, чтобы проверить будущие состояния. Алгоритм выглядит примерно так:
Если мы находимся в состоянии цели, значит, мы закончили.
Если нет, то для каждого соседа, которого нет в исследуемом списке, добавьте его в исследуемый список и сначала выполните рекурсивный поиск в глубине.
Однако, это не работает должным образом. Я провел несколько тестов и считаю, что проблема в том, что когда я вставляю состояние в исследуемый список, он фактически вставляет тот же объект , так что когда я изменяю состояние позже, исследуемый список также изменяется. Из-за этого программе никогда не кажется, что состояние не было исследовано.
Я попытался написать метод для копирования состояний и передачи копии в исследуемый список; но та же проблема сохраняется. Однако, когда я протестировал метод копирования независимо, он, кажется, успешно копирует состояния. Я полностью сбит с толку относительно того, в чем проблема.
Здесь задействовано много кода, и я не уверен, в чем проблема, но вот код для поиска в глубину:
this class we're in is the puzzle class, and this is the depth first search
'state' keeps track of the current state we're in
'explored' is a linked list of explored states
public String depthFirst(){
state.clearPath(); // state keeps track of the path taken
explored = new LLNode(state); // create explored list with starting state
this.dfs(); // depth first search
return state.path();
}
private boolean dfs(){
if(state.equals(goal)) // if we're in the goal state, then done
return true;
char[] directions = {'n', 'e', 's', 'w'};
for(char dir : directions){ // otherwise, for each direction
if(state.move(dir)){ // if we can move in that direction, then do
if(!explored.contains(state)){ // if the new state is unexplored
explored = explored.insert(state.copy());
if(this.dfs()) // add it to explored and recurse
return true;
}
switch(dir){ // if search failed, move back and
// search the next direction
case 'n': state.move('s');
case 'e': state.move('w');
case 's': state.move('n');
case 'w': state.move('e');
}
}
}
return false; // indicates failure
}
Вот вставка и содержит методы для explored:
public LLNode insert(Node gameState){
if(state == null){ // if this list node doesn't have a state
state = gameState; // then give it this one
return this;
} // otherwise tack it on the front of the list
return new LLNode(gameState, this); // and return the new head
}
public boolean contains(Node gameState){
// I had a test here that printed a message if (state == gameState)
// which was triggered when I ran the program, suggesting the problem
// I explained above
if(state.equals(gameState))
return true;
else if(next == null)
return false;
else
return next.contains(gameState);
}
Вот функция копирования для класса Node
public Node copy(){
int[][] newState = new int[state.length][state[0].length];
for(int i = 0; i < state.length; ++i)
for(int j = 0; j < state[0].length; ++j)
newState[i][j] = state[i][j];
return new Node(newState);
}
Спасибо за любые идеи!