1

我必须使用具有两个启发式的 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);

    }

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

4

1 回答 1

0

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

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

于 2018-04-20T16:34:00.613 回答