java - 为什么在 for 循环执行后我的堆栈会被覆盖？

Question

我正在为爬山搜索做一个算法，由于某种原因，我应该在循环结束时拥有的堆栈似乎被循环生成的状态的最后一次迭代覆盖。

基本上，这里是这个算法正在做的事情的概要:

该算法用于解决 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");
}

Answer 1

如果您查看 successor，我觉得这很可疑:

int[][] newState = _state;
int[] newQList = _qlist;

在这里，您似乎在对象之间共享这些数组。在不太了解程序正在做什么的情况下，这种事情通常是您观察到的“共享更新”行为的原因。

因此从返回的后继者更新数组也会改变返回它的对象的状态(依此类推)。

有几种简单的方法可以复制数组，即 System#arraycopy , Arrays#copyOf和 clone . (所有数组都是可克隆的。)对于 2D 数组，您可能想要创建一个辅助方法，因为您可能需要进行深度复制。像这样的东西:

static int[][] copyState(int[][] toCopy) {
    int[][] copy = new int[toCopy.length][];
    for(int i = 0; i < copy.length; i++) {

        // or   = Arrays.copyOf(toCopy[i], toCopy[i].length);
        copy[i] = toCopy[i].clone();
    }

    return copy;
}

我并没有花很多时间来真正解析代码——还有很多事情要做，抱歉——但我没有看到你在任何地方制作副本，只是改变它们，所以我会把我敢打赌。