Doubly-Linked 列表 Parent 指针改变

Question

实施贪婪的解决方案来解决 8 拼图

Greedy.h:

class Greedy {
    const string Goal = "12345678_";
    State current;
    string startState;
    int nodesCreated, nodesExpanded;
    priority_queue<State> greedyQueue;
    set<string> visited;
    stack<string> solutionStack;    
public:
    Greedy(const string start);
    ~Greedy();    
    void doGreedy();
};

Greedy.cpp:

tuple<int, int> getTarget(int n);


Greedy::Greedy(const string start) : startState(start), nodesCreated(0), nodesExpanded(0) {}

Greedy::~Greedy() {}    

void Greedy::doGreedy() {
    greedyQueue.emplace(startState, "");
    while (!greedyQueue.empty()) {
        current = greedyQueue.top();
        greedyQueue.pop();
        if (visited.find(current.stateString) == visited.end()) {
            visited.insert(current.stateString);
            if (current.stateString == Goal) {  //end has been reached, calculate path, print out stats, and end.
                cout << "Solution Found!" << endl;
                //solutionStack.push(current.moveFromParent);
                State* tempParent = current.parent;
                while ( solutionStack.size() < 20 && tempParent != NULL) {
                    solutionStack.push(tempParent->moveFromParent);
                    tempParent = tempParent->parent;
                }
                break;
            }
            vector<State> childrenFound = current.expandNode();
            for (int i = 0; i < childrenFound.size(); ++i) {    // for each child found, add it to the priority queue, set its parent, and set it as a child of parent
                State temp = childrenFound[i];
                if (visited.find(temp.stateString) == visited.end()) {  // We haven't been here before, put it in the queue
                    greedyQueue.push(temp);
                }
            }
        }
    }
    cout << "Last 20 moves:" << endl;
    while (!solutionStack.empty()) {
        cout << solutionStack.top() << endl;
        solutionStack.pop();
    }
}

State.h:

class State {
public:
    string moveFromParent;
    State* parent;
    string stateString;
    int distance;
    State();
    State(const string str, State * _parent, string _moveFromParent);
    State (const string str, string _moveFromParent);
    State(const string str, int dist, State * _parent, string _moveFromParent);
    ~State();

    bool operator<(const State & state) const;
    bool operator==(const State & state) const;
    int findBlank();
    vector<State> expandNode();
};

State.cpp:

int manhattan(const string str);
tuple<int, int> getTarget(int n);

State::State() {}

State::State(const string str, State * _parent, string _moveFromParent) : stateString(str), moveFromParent(_moveFromParent) {
    parent = _parent;
}

State::State(const string str, string _moveFromParent) : stateString(str), moveFromParent(_moveFromParent) {
    parent = NULL;
    distance = manhattan(stateString);
}

State::State(const string str, int dist, State* _parent, string _moveFromParent) : stateString(str), distance(dist), moveFromParent(_moveFromParent) {
    parent = _parent;
    distance = manhattan(stateString);
}

State::~State() {}

bool State::operator<(const State & state) const {
    return distance > state.distance;
}

bool State::operator==(const State & state) const {
    return ((stateString == state.stateString));
}

int State::findBlank() {
    for (int i = 0; i < stateString.length(); ++i) {
        if (stateString[i] == '_') {
            return i;
        }
    }
}

vector<State> State::expandNode() {
    vector<State> returnStates;
    int blank = findBlank();
    if (blank % 3 > 0) { // can move left
        string newState = stateString;
        newState[blank] = newState[blank - 1];
        newState[blank - 1] = '_';
        int heuristic = manhattan(newState);
        State * childsParent = this;
        string move = "left";
        State temp = State(newState, heuristic, childsParent, move);
        returnStates.push_back(temp);
    }
    if (blank % 3 < 2) { //can move right
        string newState = stateString;
        newState[blank] = newState[blank + 1];
        newState[blank + 1] = '_';
        int heuristic = manhattan(newState);
        State * childsParent = this;
        string move = "right";
        State temp = State(newState, heuristic, childsParent, move);
        returnStates.push_back(temp);
    }
    if (blank / 3 > 0) { //can move up
        string newState = stateString;
        newState[blank] = newState[blank - 3];
        newState[blank - 3] = '_';
        int heuristic = manhattan(newState);
        State * childsParent = this;
        string move = "up";
        State temp = State(newState, heuristic, childsParent, move);
        returnStates.push_back(temp);
    }
    if (blank / 3 < 2) { // can move down
        string newState = stateString;
        newState[blank] = newState[blank + 3];
        newState[blank + 3] = '_';
        int heuristic = manhattan(newState);
        State * childsParent = this;
        string move = "down";
        State temp = State(newState, heuristic, childsParent, move);
        returnStates.push_back(temp);
    }
    return returnStates;
}

int manhattan(const string str) {
    int distance = 0;
    for (int i = 0, length = str.length(); i != length; ++i) {
        tuple<int, int> target;
        if (str[i] == '_') {
            target = { 2, 2 };
        }
        else {
            int temp = str[i] - '0';
            target = getTarget(temp);
        }
        tuple<int, int> current = getTarget(i + 1);
        int localSum = abs(get<0>(current) - get<0>(target)) + abs(get<1>(current) - get<1>(target));
        distance += localSum;
    }
    return distance;
}

tuple<int, int> getTarget(int n) {
    return { (n - 1) / 3, (n - 1) % 3 };
}

我遇到一个问题，当我扩展更多节点时，指向 State 成员 parent 的指针正在改变。

State有一个成员变量State * parent。用于求解后遍历回到起点，从而得到解的走法。

展开第一个节点后，优先级队列正常，所有节点的parent为根节点，其parent为NULL。然而，在第二个节点之后，我的优先级队列中的节点都指向刚刚扩展的节点！这些应该指向它们各自的 parents，并且不应捆绑在一起。我似乎找不到我哪里出错了，任何帮助将不胜感激。谢谢！

Answer 1

问题出在 Greedy::doGreedy 和您对 current 的使用。

赋值 current = greedyQueue.top(); 创建队列顶部对象的副本。稍后，当您调用 vector<State> childrenFound = current.expandNode(); 时，所有返回的状态都有指向 current 的父指针。在下一个循环迭代中，您再次对 current 进行赋值，更改所有返回状态指向的父对象。

您的代码无法轻松修复。您需要重新考虑如何存储 State 对象，以便父对象保持不变。通常这种事情是用堆栈或列表完成的，将每个节点添加到末尾并将它们弹出以向上移动到父节点。

Doubly-Linked 列表 Parent 指针改变

Doubly-Linked list Parent pointer changing

c++

pointers

greedy

sliding-tile-puzzle