Как придет мой стек перезаписывается после казни для цикла?

Question

Я делаю алгоритм для поиска холма, и почему-то, по какой-то причине, стек, который я должен иметь в конце цикла, кажется, перезаписывается последней итерацией состояния, который генерировал петлю.

в основном, вот изложение того, что делает этот алгоритм:

Этот алгоритм используется для решения проблемы N Queens. Весь базовый код с государственным классом работает отлично. С помощью этого алгоритма оно итерации во всех возможных государствах преемника текущего состояния. Он хранит следующее состояние преемника в пределах соседней переменной (как видно в коде ниже). Если стоимость государства меньше текущей стоимости, она будет добавлять соседний уставившуюся новую низкую стоимость соседнего и хранить это в стек. Любые новые минимальные значения, которые обнаруживаются, вытесняют стек и вставьте новые минимальные узлы.

Я проделал несколько тестов в цикле, чтобы увидеть, как выглядят выходы от того, что вставляется в стек. Все они, кажется, правильно выводят. Тем не менее, когда я за пределами цикла и проверьте стек, все узлы в стеке имеют свои состояния, замененные в последнее созданное состояние преемника из цикла. Кажется, что в каждом узле, который содержит спасение соседства, каждый раз, когда обновления соседства, он также меняет все значения соседства узла. Я просто не могу найти способ исправить это, хотя.

Некоторые совет относительно того, как я могу починить, это будет очень оценено!

* ПРИМЕЧАНИЕ. Не обращайте внимания на код после наступления LOOP, начиная с оператора IF, как все еще неполное.

Вот код:

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;

.

Здесь, похоже, вы разделяете эти массивы между объектами. Не зная много о том, что делает программа, такая вещь, как правило, является причиной «общего обновления», которую вы наблюдали.

Так что обновление массива из возвращаемого преемника также изменит состояние объекта, который возвратил его (и так далее).

Есть пара легких способов скопировать массив, а именно Система # ArrayCopy , Массивы # CopyOf и клон . (Все массивы клонкованы.) Для 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;
}

.

Я не проводил много времени действительно разбирая код - есть много, чтобы пройти, извините - но я не вижу, что вы делаете копии где угодно, просто мутируя их, поэтому я бы поставил Моя ставка на это.