Попытка выполнить поиск A* с помощью эвристики, но состояния не записываются
Итак, я работаю над этой игрой 3х3, где вам дано текущее состояние, например:
1 5 6
3 7 б
2 8 4
и вы хотите достичь цели состояния:
б 1 2
3 4 5
6 7 8
Итак, я написал все другие методы в своем коде, который я разместил ниже. Проблема, с которой я сейчас сталкиваюсь, заключается в моем настоящем поиске A*. Я хочу использовать две эвристики, одна из которых проверяет, сколько фигур находится в неправильном месте (так, например, эвристическая функция покажет, что текущее состояние имеет H=8 штук в неправильном месте), а другая эвристика, которая вычислит, как далеко общая сумма кусков равна (так что для моего текущего состояния, часть 1 находится на расстоянии 1 шага, часть 2 - на расстоянии 3 шага и т. д., и сумма всего, что будет моим значением H). Итак, я записываю gameBoard в массиве строк.
Так что теперь к моей актуальной проблеме. Все, кроме моего A*, работает прямо сейчас, как показано ниже.
Сначала я звоню setFinalGoalState() который делает переменную finalGoalState так что я могу сравнить свое текущее состояние с целевым состоянием.
Тогда я делаю priorityQueue который должен быть ArrayList из Nodes, где каждый узел будет иметь значение G (G - это расстояние до дерева), значение H, ссылку на родителя и текущее состояние.
Итак, сначала я называю начальный huesticOneHValue() чтобы получить значение H моего первого состояния. Затем я запускаю if утверждение для "h1" (это просто мой первый эвристический метод, как я уже сказал, я добавлю еще один позже). Затем он должен сделать начальный узел Root который будет моим первым узлом в дереве, и добавьте его в очередь приоритетов.
Затем он должен пройти через очередь приоритетов. Это будет текущий узел в качестве первого элемента в priorityQueue, а затем удалите его из очереди. Это устанавливает мой фактический gameBoard как то же состояние gameBoard что текущий узел Тогда это создает ArrayList возможных ходов (это звонки isValidMoves(), который проверяет, действительно ли вы можете двигаться вверх, вниз, влево или вправо, а затем помещает его в список). Затем я делаю цикл for, чтобы пройти через размер моих возможных ходов, а затем я делаю фактическое перемещение, вызывая move() метод (поэтому первый вызов для int i = 0 будет называть движение "вверх", так как вы можете переместить б вверх в моем текущем состоянии) Затем он должен создать Node ребенок, содержащий gValue где я (это должно быть равно 1), новое значение H (в некоторых случаях это может остаться прежним, но оно должно работать в направлении снижения значений H), его родитель (который, я думаю, должен быть просто currentNode?), а затем состояние currentNode (как выглядит доска).
Затем следующий цикл проверяет, чтобы увидеть, где он должен поместить его в очередь приоритетов. Узлы с меньшими g+h значения должны идти впереди очереди, потому что мы хотим сначала проверить их, чтобы увидеть, достигают ли они целевого состояния. Поэтому я устанавливаю начальное условие, если очередь пуста, чтобы добавить ее вперед, иначе она проверяет, priorityQueue в j больше g+h чем потомки, и если это так, то потомок добавляется в индекс j (и все остальное должно измениться, я думаю?) Наконец, после того, как все ходы сделаны, он проверяет, priorityQueueСостояние переднего узла s равно нашему целевому состоянию, и если его нет, он возвращается к началу цикла while и запускается снова.
Я думаю, что в конечном итоге я что-то испортил своими узлами. Когда я запустил отладку, я обнаружил, что каждый раз, когда я делаю ребенка, состояние родительского узла обновляется до состояния дочерних элементов, что не должно происходить, потому что дочерний элемент должен быть определенным движением родителей (вверх, вниз, влево, или право). Я думаю, что испортил что-то, создавая класс моего узла или способ, которым я создаю узлы и добавляю их в очередь. Я также получаю indexOutOfBounds, когда пытаюсь добавить своего ребенка в priorityQueue в
else if((priorityQueue.get(j).getG()+priorityQueue.get(j).getH()) > (child.getG()+child.getH())){
Остальная часть моего кода ниже:
EightPuzzle Class
public class EightPuzzle{
static String[][] gameBoard = new String[3][3];
static String[][] finalGoalState = new String[3][3];
static int[] bLocation = new int[2];
String board;
String dir;
/*public void ReadFromTxt(String file) throws FileNotFoundException, IOException {
String read;
FileReader f = new FileReader(file);
int i = 0;
int j;
BufferedReader b = new BufferedReader(f);
System.out.println("Loading puzzle from file...");
while((read = b.readLine())!=null){
if(read.length()==3){
for(j=0;j<3;j++){
board[i][j] = (int)(read.charAt(j)-48);
}
}
i++;
}
b.close();
System.out.println("Puzzle loaded!");
}*/
public void setState(String board){
gameBoard[0][0] = board.substring(0,1);
gameBoard[0][1] = board.substring(1,2);
gameBoard[0][2] = board.substring(2,3);
gameBoard[1][0] = board.substring(4,5);
gameBoard[1][1] = board.substring(5,6);
gameBoard[1][2] = board.substring(6,7);
gameBoard[2][0] = board.substring(8,9);
gameBoard[2][1] = board.substring(9,10);
gameBoard[2][2] = board.substring(10,11);
System.out.println(Arrays.deepToString(gameBoard));
}
public static void setFinalGoalState(){
finalGoalState[0][0] = "b";
finalGoalState[0][1] = "1";
finalGoalState[0][2] = "2";
finalGoalState[1][0] = "3";
finalGoalState[1][1] = "4";
finalGoalState[1][2] = "5";
finalGoalState[2][0] = "6";
finalGoalState[2][1] = "7";
finalGoalState[2][2] = "8";
}
public static void setGoalState(){
gameBoard[0][0] = "b";
gameBoard[0][1] = "1";
gameBoard[0][2] = "2";
gameBoard[1][0] = "3";
gameBoard[1][1] = "4";
gameBoard[1][2] = "5";
gameBoard[2][0] = "6";
gameBoard[2][1] = "7";
gameBoard[2][2] = "8";
bLocation[0] = 0;
bLocation[1] = 0;
}
public void randomizeState(int numMoves){
setGoalState();
for(int i=0;i<numMoves;i++){
ArrayList<String> validMoves3 = isValidMove();
Random r = new Random();
int mIndex = r.nextInt(validMoves3.size());
String choice = validMoves3.get(mIndex);
move(choice);
System.out.println(Arrays.deepToString(gameBoard));
}
}
public ArrayList<String> isValidMove(){
ArrayList<String> validMoves = new ArrayList<String>();
if(bLocation[0] != 0){
//can move up
validMoves.add("up");
}
if(bLocation[0] != 2){
//can move down
validMoves.add("down");
}
if(bLocation[1] != 0){
//can move left
validMoves.add("left");
}
if(bLocation[1] != 2){
//can move right
validMoves.add("right");
}
return validMoves;
}
public void move(String dir){
ArrayList<String> validMoves2 = isValidMove();
if(validMoves2.contains("up") && dir.equals("up")){
String temp1 = new String();
temp1 = gameBoard[bLocation[0]-1][bLocation[1]];
gameBoard[bLocation[0]][bLocation[1]] = temp1;
gameBoard[bLocation[0]-1][bLocation[1]] = "b";
bLocation[0] = bLocation[0]-1;
}
else if(validMoves2.contains("down") && dir.equals("down")){
String temp2 = new String();
temp2 = gameBoard[bLocation[0]+1][bLocation[1]];
gameBoard[bLocation[0]][bLocation[1]] = temp2;
gameBoard[bLocation[0]+1][bLocation[1]] = "b";
bLocation[0] = bLocation[0]+1;
}
else if(validMoves2.contains("left") && dir.equals("left")){
String temp3 = new String();
temp3 = gameBoard[bLocation[0]][bLocation[1]-1];
gameBoard[bLocation[0]][bLocation[1]] = temp3;
gameBoard[bLocation[0]][bLocation[1]-1] = "b";
bLocation[1] = bLocation[1]-1;
}
else if(validMoves2.contains("right") && dir.equals("right")){
String temp4 = new String();
temp4 = gameBoard[bLocation[0]][bLocation[1]+1];
gameBoard[bLocation[0]][bLocation[1]] = temp4;
gameBoard[bLocation[0]][bLocation[1]+1] = "b";
bLocation[1] = bLocation[1]+1;
}
}
public static void printState(){
System.out.println(Arrays.deepToString(gameBoard));
}
public void getbLocation(){
for(int i=0; i<gameBoard.length; i++){
for(int j=0; j<gameBoard[i].length; j++){
if(gameBoard[i][j].equals("b"))
{
bLocation[0] = i;
bLocation[1] = j;
break;
}
}
}
System.out.println(Arrays.toString(bLocation));
}
public int heuristicOneHValue(){
int hValue = 0;
if(!gameBoard[0][0].equals("b")){
hValue++;
}
if(!gameBoard[0][1].equals("1")){
hValue++;
}
if(!gameBoard[0][2].equals("2")){
hValue++;
}
if(!gameBoard[1][0].equals("3")){
hValue++;
}
if(!gameBoard[1][1].equals("4")){
hValue++;
}
if(!gameBoard[1][2].equals("5")){
hValue++;
}
if(!gameBoard[2][0].equals("6")){
hValue++;
}
if(!gameBoard[2][1].equals("7")){
hValue++;
}
if(!gameBoard[2][2].equals("8")){
hValue++;
}
return hValue;
}
public void solveAstar(String heuristic){
setFinalGoalState();
ArrayList<Node> priorityQueue = new ArrayList<Node>();
int h = heuristicOneHValue();
if(heuristic.equalsIgnoreCase("h1"))
{
Node root = new Node(0,h,null,gameBoard);
priorityQueue.add(root);
while(priorityQueue != null){
Node currentNode = priorityQueue.get(0);
priorityQueue.remove(0);
gameBoard = currentNode.state;
ArrayList<String> moves = isValidMove();
for(int i = 0; i < moves.size(); i++){
move(moves.get(i));
Node child = new Node(currentNode.getG(),heuristicOneHValue(),currentNode,currentNode.getState());
for(int j = 0; j <= priorityQueue.size(); j++){
if(priorityQueue.size() == 0){
priorityQueue.add(0, child);
}
else if((priorityQueue.get(j).getG()+priorityQueue.get(j).getH()) > (child.getG()+child.getH())){
priorityQueue.add(j, child);
}
}
}
if(priorityQueue.get(0).getState() == finalGoalState){
priorityQueue = null;
}
}
}
//h2 here
}
public static void main (String[]args){
EightPuzzle b1=new EightPuzzle();
b1.setState("156 37b 284");
b1.getbLocation();
b1.solveAstar("h1");
}
}
Класс узла
class Node {
public String[][] state;
public Node parent;
public int g;
public int h;
public Node(int g, int h, Node parent, String[][] state){
this.g = g;
this.h = h;
this.parent = parent;
this.state = state;
}
public String[][] getState(){
return state;
}
public int getG(){;
return g;
}
public int getH(){
return h;
}
public Node getParent(){
return parent;
}
public void setState(String[][] state){
this.state = state;
}
public void setG(int g){
this.g = g;
}
public void setH(int h){
this.h = h;
}
public void setParent(Node parent){
this.parent = parent;
}
}
1 ответ
Прежде всего, я не знаю, полностью ли я понял вашу проблему, но если я прав, вы говорите, что состояния узлов между ними не различаются.
Если это так, то ваша проблема в этой строке:
Node child = new Node(currentNode.getG(),heuristicOneHValue(),currentNode,currentNode.getState());
Вы разделяете указатель на объект состояния между различными узлами, поэтому вместо этого вам нужно работать с копией состояния. Метод getState в классе Node, по моему мнению, будет лучшим местом для создания копии, поэтому вы избежите дальнейших проблем, когда другие объекты изменят состояние.
Пример:
public String[][] getState(){
String[][] returnState = new String[this.state.length][this.state[0].length];
for (int i = 0; i < this.state.length; i++) {
for (int j = 0; j < this.state[0].length; j++) {
returnState[i][j] = this.state[i][j];
}
}
return returnState;
}