Java - 在广度优先搜索中获取路径的好方法？

Question

我已经为此工作了一整天，想不出一个好的解决方案。我要实现广度优先搜索算法以解决滑动难题。到目前为止，这是我的代码的相关部分。 (我还没有测试它是否有效，因为它不完整)至此，这段代码有望遍历所有的可能性，到达目标。但是，我想不出一种方法来记录从初始状态到目标状态的路径。

private void addToQueue(PuzzleState nextPS) {
    if (notVisitedAndNotNull(nextPS))
        queue.add(nextPS);
}

private void solveByBFS() {
    queue.clear();
    queue.add(this.initialState);
    long startTime = System.currentTimeMillis();

    while(!queue.isEmpty()) { //TODO create a way to backtrack and get a path
        if (queue.size() > maxQueueSize)
            maxQueueSize = queue.size();
        this.currentState = queue.poll();

        if (this.currentState.equals(finalState)) { //TODO check if cannot progress any further and terminate
            System.out.println("Successful! Ending Time: " + startTime);
            return;
        }
        visited.add(this.currentState);

        this.addToQueue(this.currentState.moveUp());
        this.addToQueue(this.currentState.moveDown());
        this.addToQueue(this.currentState.moveRight());
        this.addToQueue(this.currentState.moveLeft());

    }
    return;
}

所以我想要一种回溯的方法，从目标节点到初始状态，反转路径，然后打印出来在一个列表中。

这是我使用的数据结构:

public class SimplePuzzleState implements PuzzleState{

private int rowSz;
private int sz;
private int zeroPos;
private int[] gameState;

@Override
public void configureState(int[] gameState) {
    rowSz = (int) Math.sqrt(gameState.length);
    sz = gameState.length;
    zeroPos = PuzzlePropertyUtility.findZeroPosition(gameState); 
    this.gameState = gameState;
}

@Override
public PuzzleState moveUp() { 
    if (zeroPos <= rowSz - 1) {
        return null;
    }
    this.swap(zeroPos, zeroPos - rowSz);
    return this.createNewUpdatedState();
}

@Override
public PuzzleState moveDown() {
    if (zeroPos >= sz - rowSz) {
        return null;
    }
    this.swap(zeroPos, zeroPos + rowSz);
    return this.createNewUpdatedState();
}

@Override
public PuzzleState moveLeft() {
    if (zeroPos % rowSz <= 0) {
        return null;
    }
    this.swap(zeroPos, zeroPos - 1);
    return this.createNewUpdatedState();
}

@Override
public PuzzleState moveRight() {
    if (zeroPos % rowSz >= rowSz -1) {
        return null;
    }
    this.swap(zeroPos, zeroPos + 1);
    return this.createNewUpdatedState();
}

@Override
public boolean isEqual(PuzzleState other) { 
    if (other != null) {
        if (this.getStateArray() instanceof int[] && other.getStateArray() instanceof int[])
            return (Arrays.equals(this.getStateArray(), other.getStateArray()));
    }
    return false;
}

@Override
public int[] getStateArray() {
    return gameState;
}

private void swap(int pos1, int pos2) {
    int temp = this.gameState[pos1];
    this.gameState[pos1] = this.gameState[pos2];
    this.gameState[pos2] = temp;
}

private PuzzleState createNewUpdatedState() {
    PuzzleState newState = new SimplePuzzleState();
    newState.configureState(this.getStateArray());
    return newState;
}

这是 PuzzleState 接口(interface):

public interface PuzzleState {

public void configureState(int[] gameState);

PuzzleState moveUp();

PuzzleState moveDown();

PuzzleState moveLeft();

PuzzleState moveRight();



boolean isEqual(PuzzleState other);

int[] getStateArray();

我考虑过向 SimplePuzzleState 添加一个属性以包含父节点。但是，我无法修改它实现的接口(interface)，因为我的讲师不允许这样做。因此，我无法使用链表方法进行回溯。有什么聪明的方法可以记录正确的路径吗？最后，我的导师要我打印一个包含代表 Action 的枚举的列表。所以我必须弄清楚如何将枚举映射到函数 moveUp、moveDown 等。

提前致谢。对于发布这么多代码，我深表歉意，但我真的需要关于我应该朝哪个方向发展的建议。

Answer 1

你的想法是正确的。如果您不能将父指针添加到状态，则只需维护一个具有相同信息的 HashMap，称为 previous。当你创建四个子状态，添加从父到这四个的映射。

// A map to hold parent relations.   
HashMap<SimplePuzzleState, SimplePuzzleState> previous = new HashMap<>();

...

// Now change the add function.
private void addToQueue(PuzzleState parentPS, PuzzleState nextPS) {
    if (notVisitedAndNotNull(nextPS)) {
        queue.add(nextPS);
        previous.add(nextPS, parentPS);
        nextPS.updateParent(this); // and update where we got from
    }
}

// Then update the calls to match:
this.addToQueue(currentState, this.currentState.moveUp());
... 

当您找到目标时，就像使用父指针一样使用散列追溯至起点。

    if (this.currentState.equals(finalState)) { 
        System.out.println("Successful! Ending Time: " + startTime);
        System.out.println("Path back to start:");
        PuzzleState state = currentState;
        do {
          state.print();
          state = previous.get(state);
        } while (state != null);
    }