用Java编写的一个*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

(还有更多失败的测试，这仅仅是前三个)，因为当我使用第一个启发式时，它似乎对所有情况都有效，所以我猜第二个启发式是有问题的。下面是我的抽象“节点”类：

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;

下面是利用第二个启发式方法的节点类：

    //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类的hashcode函数来解决这个问题。

此外，在计算启发式时，我在计算中包括了洞，但不应将该孔包括在成本计算中。这与我所面临的问题无关，但为了其他读者的利益，我在这里讨论这个问题。