用 Java 编写的 A* 8 谜题不适用于某些初始状态

Question

我必须使用具有两种启发式算法的 A* 算法来实现一个 8 拼图求解器。第一个启发式只是错位瓦片的总和，第二个是所有瓦片与目标状态的曼哈顿距离之和，我们将其定义为：

0 1 2
3 4 5
6 7 8

我们给出了不同深度的样本测试。我使用第一个启发式的实现通过了所有这些情况，但是第二个启发式一旦达到 14 的深度就没有通过某些测试用例：

 (52) !Test Case failed! for initialState:
3 1 5 
6 0 7 
8 2 4
Expected depth of 14 but got 16

(12) !Test Case failed! for initialState:
4 1 5 
3 2 7 
0 8 6
Expected depth of 16 but got 18

(39) !Test Case failed! for initialState:
2 5 7 
3 4 1 
6 8 0
Expected depth of 16 but got 18

（还有更多失败的测试，这些只是前三个）因为当我使用第一个启发式时它似乎适用于所有情况，我猜第二个启发式有问题。这是我的摘要 "node" class:

public EightPuzzleState(int[] state, EightPuzzleState goalState, EightPuzzleState previousState) {
    this.state = new int[NUM_SPACES];
    try {   
        System.arraycopy(state, 0, this.state, 0, NUM_SPACES);
    }catch(ArrayIndexOutOfBoundsException e){
        e.printStackTrace();
    }
    this.previousState = previousState;
    setCost(goalState);

}
private void setCost(EightPuzzleState goalState) {
    if(goalState == null) {
        System.out.println("Cost is 0- no goal state defined");
        cost = 0;
    }
    else {
        cost = calcCost(goalState);  
    }
}

private int calcCost(EightPuzzleState goalState) {
    int sum = 0;
    for(int i = 0; i < NUM_SPACES; i++) {
        sum+=heuristic(goalState, i);
    }
    if(previousState == null) {
        //System.out.println("No previous parent defined, 0 pathCost");
        pathCost = 0;
    }
    else {
        pathCost = previousState.getPathCost()+1;
    }
    return sum + pathCost;

这里是使用第二个启发式的节点 class：

    //In EightPuzzleStateH2 class, which extends EightPuzzleState
    @Override
    protected int heuristic(EightPuzzleState goalState, int currentIndex) {
        int currentValue = this.getState()[currentIndex];
        int[] goalStateArray = goalState.getState();
        int i = 0;

        while(currentValue != goalStateArray[i]) { 
            i++;
        }

        return calcManhattenDistance(currentIndex,i);
    }

    private int calcManhattenDistance(int currentIndex, int goalIndex) {
        int xDistance = Math.abs((currentIndex % NUM_SPACES_PER_ROW) - (goalIndex % NUM_SPACES_PER_ROW));
        int yDistance = Math.abs((currentIndex / NUM_SPACES_PER_ROW) - (goalIndex / NUM_SPACES_PER_ROW));
        return (xDistance+yDistance);

    }

任何见解都会有所帮助 - 如果问题不在第二个启发式中，那么我真的会被难倒，因为第一个启发式完美无缺！

Answer 1

我能够通过修改我的 EightPuzzleState class 的哈希码函数来解决这个问题。

此外，在计算启发式时，我将漏洞包括在计算中，但该漏洞不应包含在成本计算中。这与我遇到的问题无关，但为了其他读者，我在这里解决它。

用 Java 编写的 A* 8 谜题不适用于某些初始状态

A* 8 puzzle written in Java not working for certain initial states

java

artificial-intelligence

a-star

sliding-tile-puzzle