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

我並沒有花太多時間真的解析代碼 - 有很多經歷，很抱歉 - 但我沒有看到你在任何地方做一個副本，只是變異他們，所以我會把我的賭注放在這個。