java - 如何为 N-Queen Hill Climbing 生成邻居

Question

我在生成用于实现爬山算法的邻居时遇到了问题。

这是我目前正在使用的代码。

public ArrayList<Board> generateNeighbors(){
    ArrayList<Board> neighborBoards = new ArrayList<Board>();

    HashMap<Integer, Integer> initialQueenLocations = this.queenLocations;


    for(int i = 0; i < queen; i++){

        int[][] neighborBoard = new int[queen][queen];
        HashMap<Integer, Integer> neighborQueenLocations = initialQueenLocations;

        for(int k = i; k < queen; k++){

            for(int j = 0; j < queen; j++){
                neighborBoard[j][initialQueenLocations.get(j)] = 1;
            }

            int initialLocation = initialQueenLocations.get(k);

            if(initialLocation > 0){

                neighborBoard[k][initialLocation] = 0;
                neighborBoard[k][initialLocation - 1] = 1;

                neighborQueenLocations.put(k, initialLocation - 1);

                neighborBoards.add(new Board(neighborBoard, neighborQueenLocations));
                break; 
            }

        }
    }
}

我遇到的问题是我生成的每个新棋盘都会保存最后一步，我希望每个相邻棋盘的步长为 1。这是(错误的)输出:

//initial
0|0|1|
0|1|0|
0|1|0|
//step 1
0|1|0|
0|1|0|
0|1|0|
//step 2
0|1|0|
1|0|0|
0|1|0|
//step 3
0|1|0|
1|0|0|
1|0|0|

这是我想要的输出。

//initial
0|0|1|
0|1|0|
0|1|0|
//step 1
0|1|0|
0|1|0|
0|1|0|
//step 2
0|0|1|
1|0|0|
0|1|0|
//step 3
0|0|1|
0|1|0|
1|0|0|

如您所见，它正在保存上一步的移动。有人可以帮忙吗？

Answer 1

您的问题是您覆盖了初始 HashMap 中的值。在将 neighborQueenLocations 设置为 initialQueenLocations 的地方，您基本上只是设置了对 initialQueenLocations HashMap 的引用。所以当你执行 neighborQueenLocations.put(k, initialLocation - 1); 时，你写入了由 initialQueenLocations 保留的内存，但是通过你的 neighborQueenLocations 变量。

    ...

    for(int i = 0; i < queen; i++){

        int[][] neighborBoard = new int[queen][queen];

        // Here you are setting a reference, not copying the values
        HashMap<Integer, Integer> neighborQueenLocations = initialQueenLocations;

    ...

稍后在您的代码中，您将覆盖 initialQueenLocations HashMap 中的值，因为 neighborQueenLocations 只是对您的 initialQueenLocations 的引用。

    ...
    neighborBoard[k][initialLocation] = 0;
    neighborBoard[k][initialLocation - 1] = 1;

    neighborQueenLocations.put(k, initialLocation - 1);
    ...

这就是它“记住”最后一步的原因。