-1

我正在实施广度优先搜索来解决 8 难题。当我尝试使用this指针创建新节点并指向当前节点时，父指针返回垃圾值。这是由于迭代器无效吗？有没有办法绕过这个问题，也许是通过使用与向量不同的容器？

代码：

#include <iostream>
#include <string>
#include <iostream>     
#include <algorithm>    
#include <vector>       
#include <queue>
using namespace std;
class Node {
public:

vector<Node> children;
vector<int> puzzle;
vector<int> goal = {1, 2, 3, 4, 5, 6, 7, 8, 0};
Node *parent;
Node(vector<int> _puzzle, Node *_parent){
    puzzle=_puzzle;
    parent=_parent;
}

void printPuzzle() {
    int count = 0;
    for (auto i: puzzle) {
    if ( count % 3 == 0)
    std::cout << std::endl;
    std::cout << i << ' ';
    count++;   
}
}

int findZero(){
    std::vector<int>::iterator it;
    it = find (puzzle.begin(), puzzle.end(), 0);
    auto z = std::distance(puzzle.begin(), it);
    return (int)z;
}

bool isGoal(){
    bool goalFound = false;
    if(puzzle == goal)
    goalFound = true;
    return goalFound;
}

void moveUp(){
    int zPos = findZero();
    vector<int> temp = puzzle;
    if ( zPos != 0 && zPos != 1 && zPos != 2 )
    std::swap(temp[zPos], temp[zPos-3]);
    Node child = Node(temp, this);
    children.push_back(child);

}

void moveDown(){
    int zPos = findZero();
    vector<int> temp = puzzle;
    if ( zPos != 6 && zPos != 7 && zPos != 8 )
    std::swap(temp[zPos], temp[zPos+3]);
    Node child = Node(temp, this);
    children.push_back(child); 
}

void moveRight(){
    int zPos = findZero();
    vector<int> temp = puzzle;
    if ( zPos != 2 && zPos != 5 && zPos != 8 )
    std::swap(temp[zPos], temp[zPos+1]);
    Node child = Node(temp, this);
    children.push_back(child);
}

void moveLeft(){ 
    int zPos = findZero();
    vector<int> temp = puzzle;
    if ( zPos != 0 && zPos != 3 && zPos != 6 )
    std::swap(temp[zPos], temp[zPos-1]);
    Node child = Node(temp, this);
    children.push_back(child); 
}
};

bool contains(std::queue<Node> q, Node n){
    std::queue<Node> tempQ = q;
    bool exist = false;
    while (!tempQ.empty()){
        if (tempQ.front().puzzle == n.puzzle)
        exist = true;
        tempQ.pop();
    }
    return exist;
 }

int main()
{
std::vector<int> initial;
initial.push_back(3);
initial.push_back(5);
initial.push_back(8);
initial.push_back(1);
initial.push_back(0);
initial.push_back(4);
initial.push_back(2);
initial.push_back(7);
initial.push_back(6);
Node init = Node(initial, NULL);
std::queue<Node> openList;
std::queue<Node> closedList;
openList.push(init);
bool goalFound = false;
while(!openList.empty() && !goalFound){
    Node currentNode = openList.front();
    closedList.push(currentNode);
    openList.pop();       
    currentNode.moveUp();
    currentNode.moveDown();
    currentNode.moveRight();
    currentNode.moveLeft();

    for (auto i: currentNode.children){
        Node currentChild = i;
        if (currentChild.isGoal()){
            std::cout << "Goal Found." << endl;
            goalFound = true;


        }
        if (!contains(openList, currentChild) && !contains(closedList, 
 currentChild))
            openList.push(currentChild); 
    }   
}
}
4

1 回答 1

1

Copy and reference/pointer are different things. Let's look at one of the problems of your code. Here's problematic code:

while(!openList.empty() && !goalFound){
    Node currentNode = openList.front();
    closedList.push(currentNode);
    openList.pop();       
    currentNode.moveUp();
    currentNode.moveDown();
    currentNode.moveRight();
    currentNode.moveLeft();

    for (auto i: currentNode.children){
        Node currentChild = i;
        if (currentChild.isGoal()){
            std::cout << "Goal Found." << endl;
            goalFound = true;
        }
        if (!contains(openList, currentChild) && !contains(closedList,currentChild))
            openList.push(currentChild); 
        }   
    }
}

For simplicity let's assume that there's only one Node in openList, and let's call its address oL0. Now lets step line by line and see what's happening:

Node currentNode = openList.front(); // creates copy of first element in queue

As you could've guessed creating copy creates new Node with same inner state. Let's call the address of the currentNode cN0. Important thing to remember is that addresses oL0 and cN0 are different(they are different objects). Let's move on:

closedList.push(currentNode); // creates COPY of currentNode in closedList
openList.pop(); // deletes Node at address oL0

Quite simple - closedList has copy of currentNode at address, which we may call cL0.

// do stuff with currentNode (address cN0)
currentNode.moveUp();
currentNode.moveDown();
currentNode.moveRight();
currentNode.moveLeft();

Here lies one the problems. You are changing variable currentNode at address cN0 (NOT the value stored closedList). As we move bit further through your code, into the for loop, we can find out where 2nd problem, your problem, lies. Point of this for loop is to push children of currentNode into openList:

for (/* ... */) {
    // ...
    // same problem of creating copies
    if (/* ... */)
        openList.push(currentChild); 
    }
}

These children have their parent pointer set to address of an currentNode(which is cN0). At the end of iteration of while loop destructors of all local variables (variables inside while scope) get called, which results in currentNode being destroyed. Meaning that every child Node in openList has invalid address (garbage value you reffered) to its parent. Beware that same problem appears inside of the for loop.

For ideas how to solve this, I advise looking into references, or for example using queues of pointers...

于 2018-02-20T09:51:56.390 回答