Come mai il mio stack viene sovrascritto dopo un'esecuzione per loop?

Question

Sto facendo un algoritmo per una ricerca per arrampicata a collina, e per qualche ragione, lo stack che dovrei avere alla fine del ciclo sembra essere sovrascritto con l'ultima iterazione dello stato generato dal loop.

Fondamentalmente, ecco un rundown di ciò che questo algoritmo sta facendo:

Questo algoritmo viene utilizzato per risolvere il problema N Queens. Tutto il codice sottostante con la classe statale funziona perfettamente bene. Con questo algoritmo, itera attraverso tutti gli stati del successore possibili dello stato attuale. Memorizza il prossimo stato successivo della variabile neightale (come visto nel codice qui sotto). Se un costo dello stato è inferiore al costo corrente, aggiungerà il vicino con quel nuovo basso costo in un neighborborned e conservarlo in una pila. Eventuali nuovi valori minori che vengono rilevati puliranno lo stack e inseriscono i nuovi nodi minimi più bassi.

Ho fatto alcuni test all'interno del loop per vedere cosa assomigliano alle uscite da ciò che viene inserito nella pila. Tutti sembrano emettersi correttamente. Tuttavia, quando sono fuori dal loop e controlla la pila, tutti i nodi nella pila hanno i loro stati sostituiti all'ultimo stato del successore generato dal ciclo. Sembra che in ogni nodo che abbia memorizzato il vicino, ogni volta che gli aggiornamenti del vicino, cambia anche tutti i valori del neodo del nodo. Non riesco a trovare un modo per risolvere questo problema.

Alcuni consigli su come posso risolvere questo sarebbe molto apprezzato!

* Nota: ignorare il codice dopo il loop per l'avvio dell'istruzione IF, poiché è ancora incompleta.

Ecco il codice:

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

Se guardi successor, questo sembra sospetto a me:

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

.

Qui, sembra che tu stia condividendo questi array tra gli oggetti. Senza sapere molto su cosa sta facendo il programma, questo tipo di cosa è in genere la causa del comportamento "Aggiornamento condiviso" che hai osservato.

Quindi l'aggiornamento dell'array dal successore restituito cambierà anche lo stato dell'oggetto che è stato restituito (e così via).

Ci sono un paio di modi semplici per copiare un array, vale a dire sistema # arraycopycopy , arrays # copyof e clone . (Tutti gli array sono clonabili.) Per l'array 2D che potresti voler effettuare un metodo helper poiché probabilmente avresti dovuto creare una copia profonda. Qualcosa come:

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

.

Non ho passato un sacco di tempo analizzando il codice - c'è molto da passare, mi dispiace - ma non ti vedo fare una copia ovunque, basta mutandole, quindi avevo messo La mia scommessa su questo.