I am doing an algorithm for a hill climbing search, and for some reason, the stack that I'm supposed to have at the end of the loop seems to be overwritten with the last iteration of the state that the loop generated.
Basically, here is a rundown of what this algorithm is doing:
This algorithm is being used to solve the N queens problem. All of the underlying code with the state class works perfectly fine. With this algorithm, it iterates through all possible successor states of the current state. It stores the next successor state within the neighborState variable (as seen in the code below). If a state cost is less than the current cost, it will add the neighborState with that new low cost into a neighborNode and store that into a stack. Any new min values that get detected will wipe the stack and insert the new lowest minimum nodes.
I've done a few tests within the loop to see what the outputs look like from what is being inserted into the stack. All of them seem to be correctly outputting. However, when I am outside the loop and check the stack, all the nodes in the stack have their states replaced to the last generated successor state from the loop. It seems that in every node that has the neighborState stored, each time the neighborState updates, it changes all the node neighborState values as well. I just can't seem to find a way to fix this though.
Some advice as to how I can fix this would be greatly appreciated!
*Note: Disregard the code after the for loop starting at the if statement, as it is still incomplete.
Here is the code:
import java.util.Random;
import java.util.Stack;
public class HillClimber {
private LocalSearchNode _current;
private int _shoulderSearchStepsAllowed;
// may need more instance variables
public HillClimber(LocalSearchNode initial, int searchShoulder) {
_current = initial;
_shoulderSearchStepsAllowed = searchShoulder;
}
public LocalSearchNode findSolution() {
LocalSearchNode neighborNode = null;
//Stack <LocalSearchNode> nodeStack;
State currentState = null;
//State neighborState = null;
Double val = 0.0;
boolean start = true;
while (true) {
currentState = _current.getState();
Stack<LocalSearchNode> nodeStack = new Stack<LocalSearchNode>();
// finds the highest valued successor of current
for (String s : currentState.actions()) {
State neighborState = currentState.successor(s);
Double cost = neighborState.estimatedDistance(neighborState);
// execute this for the first successor found
if (start) {
val = cost;
System.out.println("Started with " + val);
neighborNode = new LocalSearchNode(neighborState,
s, val, 0);
nodeStack.push(neighborNode);
start = false;
((QState) nodeStack.peek().getState()).test();
System.out.println(nodeStack.size());
}
// resets node array if new min found and adds it to the array
else if (cost < val) {
System.out.println("Reset " + val + " with " + cost);
val = cost;
nodeStack = new Stack<LocalSearchNode>();
neighborNode= new LocalSearchNode(neighborState,
s, val, 0);
nodeStack.push(neighborNode);
((QState) nodeStack.peek().getState()).test();
System.out.println(nodeStack.size());
}
// if cost is the same as current min val, add it to the array
else if (cost.equals(val)) {
val = cost;
System.out.println("Added " + val);
neighborNode = new LocalSearchNode(neighborState,
s, val, 0);
nodeStack.push(neighborNode);
((QState) nodeStack.peek().getState()).test();
System.out.println(nodeStack.size());
}
}
System.out.println("Final min " + val);
System.out.println(nodeStack.size());
((QState) nodeStack.elementAt(0).getState()).test();
((QState) nodeStack.elementAt(1).getState()).test();
// returns current state if no better state found
if (_current.getValue() < val) {
// System.out.println(val);
// ((QState) _current.getState()).test();
return _current;
} else {
if (nodeStack.size() > 1) {
Random generator = new Random();
int i = generator.nextInt(nodeStack.size());
_current = nodeStack.elementAt(i);
} else {
_current = nodeStack.firstElement();
}
start = true;
}
}
}
}
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class QState implements State {
private List<String> _list;
private int[][] _state;
private int[] _qlist;
/**
* Constructor takes in the board and row index value corresponding to the
* queens at their respective column index
*
* @param state
* @param queens
*/
public QState(int[][] state, int[] queens) {
_state = state;
_qlist = queens;
_list = new ArrayList<String>();
// generates a list of all possible actions for this state
for (int i = 0; i < _qlist.length; i++) {
for (int j = 0; j < _qlist.length; j++) {
if (_state[i][j] != -1) {
_list.add("Move queen " + j + " to row " + i);
}
}
}
}
/**
* Returns a list of N * (N - 1) actions
*/
public List<String> actions() {
return _list;
}
/**
* Returns the matrix board configuration of this state
*
* @return
*/
public int[][] getMatrix() {
return _state;
}
/**
* Returns the array of queens row index for the board configuration
*
* @return
*/
public int[] getQList() {
return _qlist;
}
/**
* Parses the action and moves the queen to the new board location
*/
public State successor(String action) {
State temp = null;
int[][] newState = _state;
int[] newQList = _qlist;
String[] vals = action.split("\\s");
int i = Integer.parseInt(vals[5]); // parses the row index
int j = Integer.parseInt(vals[2]); // parses the column index
newState[_qlist[j]][j] = 0; // clears the old queen
newState[i][j] = -1; // sets the new queen
newQList[j] = i; // adds the new queen to the list
temp = new QState(newState, newQList);
return temp;
};
/**
* Returns the default step cost of 1.0
*/
public Double stepCost(String action) {
return 1.0;
}
// overrides the built-in Java equals method
@Override
public boolean equals(Object s) {
if (s == null) {
return false;
}
if (this.getClass() != s.getClass()) {
return false;
}
if (!Arrays.equals(this.getMatrix(), ((QState) s).getMatrix())) {
return false;
}
return true;
}
/**
* Returns the queen conflicts for the particular board
*/
public Double estimatedDistance(State s) {
double conflicts = 0.0;
int col = 0;
int row = 0;
for (int j = 0; j < _qlist.length; j++) {
row = _qlist[j] - 1;
col = j + 1;
// checks the upper right diagonal for queen conflicts
while (row >= 0 && col < _qlist.length) {
if (_state[row][col] == -1) {
conflicts++;
}
row--;
col++;
}
row = _qlist[j] + 1;
col = j + 1;
// checks the lower right diagonal for queen conflicts
while (row < _qlist.length && col < _qlist.length) {
if (_state[row][col] == -1) {
conflicts++;
}
row++;
col++;
}
row = _qlist[j];
col = j + 1;
// checks the sideways right for queen conflicts
while (col < _qlist.length) {
if (_state[row][col] == -1) {
conflicts++;
}
col++;
}
}
// test();
return conflicts;
}
public void test() {
for (int i = 0; i < _qlist.length; i++) {
for (int j = 0; j < _qlist.length; j++) {
if (_state[i][j] == -1) {
System.out.print("Q");
} else {
System.out.print("-");
}
}
System.out.println("");
}
System.out.println("\n");
}
}