山登り検索のアルゴリズムを実行していますが、何らかの理由で、ループの最後にあるはずのスタックが、ループが生成した状態の最後の反復で上書きされているようです。
基本的に、このアルゴリズムが行っていることの概要は次のとおりです。
このアルゴリズムは、N クイーン問題を解決するために使用されています。状態クラスの基になるコードはすべて完全に正常に動作します。このアルゴリズムでは、現在の状態のすべての可能な後続状態を反復処理します。次の後続の状態は、neighborState 変数内に格納されます (以下のコードを参照)。状態のコストが現在のコストよりも小さい場合、その新しい低コストの neighborState を neighborNode に追加し、それをスタックに格納します。新しい最小値が検出されると、スタックが消去され、新しい最小最小ノードが挿入されます。
スタックに挿入されているものからの出力がどのように見えるかを確認するために、ループ内でいくつかのテストを行いました。いずれも正しく出力されているようです。ただし、ループの外にいてスタックをチェックすると、スタック内のすべてのノードの状態が、ループから最後に生成された後続の状態に置き換えられます。neighborState が保存されているすべてのノードで、neighborState が更新されるたびに、すべてのノードの neighborState 値も変更されるようです。私はこれを修正する方法を見つけることができないようです。
これをどのように修正できるかについてのアドバイスをいただければ幸いです。
*注意: if ステートメントで始まる for ループの後のコードは、まだ不完全なので無視してください。
コードは次のとおりです。
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");
}
}