在for循环执行后，我的堆栈如何被覆盖？

Question

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

基本上，这里是一个什么这个算法做了概要：

正在使用该算法来解决N后问题。所有具有状态类的底层代码都可以很好地工作。使用该算法，它会遍历当前状态的所有可能的后继状态。它将下一个后继状态存储在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; 
} 

我并没有花太多时间真的解析代码 - 有很多经历，很抱歉 - 但我没有看到你在任何地方做一个副本，只是变异他们，所以我会把我的赌注放在这个。