3

I'm having trouble generating neighbors for implementing hill climbing algorithms.

Here's the code I'm currently working with. 

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; 
            }

        }
    }
}

The problem I'm having is that each new board I generate saves the last move, I'd like each neighbor board to have a step size of one. Here is the (wrong) output: 

//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|

Here is the output I'd like. 

//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|

As you can see, it is saving the move from the previous step. Can anybody help?

4

1 回答 1

1

Your problem is that you overwrite your values in your initial HashMap. Where you set neighborQueenLocations to be initialQueenLocations, you basically just set a reference to your initialQueenLocations HashMap. So When you do neighborQueenLocations.put(k, initialLocation - 1);, you write to the memory which is reserved by the initialQueenLocations, but "accessing" it through your neighborQueenLocations variable. 

    ...

    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;

    ...

And later in your code, you are overwriting the value in your initialQueenLocations HashMap, since neighborQueenLocations is just reference to your initialQueenLocations. 

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

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

That's why it "remembers" the last step taken.

于 2013-12-05T19:17:56.143 回答