我需要实现一个使用A*算法的8拼图求解器，使用两种启发式方法。第一种启发式方法是计算不在正确位置的瓷砖的总和，第二种是计算所有瓷砖从目标状态的曼哈顿距离之和，我们定义的目标状态是：

0 1 23 4 56 7 8

我们被提供了一些不同深度的样本测试。我使用第一种启发式方法的实现通过了所有这些测试用例，但第二种启发式方法在达到深度14时未能通过某些测试用例：

 (52) !测试用例失败! 初始状态:3 1 5 6 0 7 8 2 4预期深度为14但得到16(12) !测试用例失败! 初始状态:4 1 5 3 2 7 0 8 6预期深度为16但得到18(39) !测试用例失败! 初始状态:2 5 7 3 4 1 6 8 0预期深度为16但得到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;

以下是使用第二种启发式方法的节点类：

    //在扩展自EightPuzzleState的EightPuzzleStateH2类中    @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);    }

任何见解都会有所帮助——如果问题不在第二种启发式方法中，那么我真的会很困惑，因为第一种启发式方法运行得非常完美！

回答：

我通过修改我的EightPuzzleState类的哈希码函数解决了这个问题。

此外，在计算启发式方法时，我将空位包括在计算中，但空位不应该包括在成本计算中。这与我遇到的问题无关，但为了其他读者的利益，我在这里提及这一点。