实现指针队列

问题描述 投票:0回答:3

我正在尝试使用两个指针队列来实现8-puzzle(BFS)。我无法将未分类的节点添加到打开的列表中。我哪里错了?

#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 isSamePuzzle(vector<int> p){
        bool samePuzzle = false;
        if(puzzle == p)
        samePuzzle =  true;
        return samePuzzle;

    }
};


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

int main()
{
    std::vector<int> initial;
    initial.push_back(2);
    initial.push_back(1);
    initial.push_back(3);
    initial.push_back(4);
    initial.push_back(0);
    initial.push_back(6);
    initial.push_back(7);
    initial.push_back(5);
    initial.push_back(8);
    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);
        cout << "open list size " << openList.size() <<endl;
        cout << "closed list size " << closedList.size() <<endl;
        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);             
        }
    }
}

这似乎是有问题的一点:

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

将一个或两个节点添加到打开列表后,程序崩溃。当我在打开的列表中打印出这个谜题时,我发现在开始时有一些垃圾值,然后是实际的傻瓜。

c++ pointers queue
3个回答
0
投票

我将您的代码粘贴到我的IDE中并通过我的调试器运行它。我在这里看到的是当你在第二次迭代中经历你的while循环时;它打印出两行代码,它从openList弹出,它调用并执行moveUp()但是当它进入moveDown()时就崩溃了。

它崩溃了这条线:

std::swap( temp[zPos], temp[zPos+3] );

您可能希望在调试器中检查此行代码,同时单步执行while循环检查变量和容器,以查看它们是否具有有效信息;还要检查你是不是exceeding你的boundcontainer。您可能还想检查memory在上次调用swap之后调用moveUp()后是否仍然有效。

不是在第一次打电话给moveDown(),但是第二次打电话是你设置temp等于puzzle的问题,这里的问题是puzzle的值或大小为0。因此,当你试图在std::swaptemp[zPos]上调用temp[zPos+3]时,索引无效,因为tempsize = 0


0
投票

您的程序的主要问题是,您将指针推送到打开列表中的本地变量。一旦保留范围,变量currentChild将被销毁(所以只要你进入循环的下一次迭代或离开循环),然后指针指向未使用/垃圾内存。

但是,您将在其他地方遇到类似的问题,因为您无法可靠地保存指向vector<Node>列表中任何节点的指针。这是因为std::vector类在第一次达到一定大小时会破坏/复制其中的所有内容,这将使任何指向其中任何内容的指针无效。所以要么你只保存指向所有投币器中的节点的指针(queuevector,所以只有指针被销毁/复制),或者你不保存指向节点的任何指针,而只保存节点本身 - 无论你最好的套房。


0
投票

我能够通过使子节点成为Node指针的向量来修复代码,如下所示:

vector<Node*> children;

每个孩子都有一个节点指针:

Node* child = new Node(temp, this);
© www.soinside.com 2019 - 2024. All rights reserved.