我正在尝试使用两个指针队列来实现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(¤tChild);
}
}
}
这似乎是有问题的一点:
if (!contains(openList, currentChild) && !contains(closedList,
currentChild))
openList.push(¤tChild);
将一个或两个节点添加到打开列表后,程序崩溃。当我在打开的列表中打印出这个谜题时,我发现在开始时有一些垃圾值,然后是实际的傻瓜。
我将您的代码粘贴到我的IDE中并通过我的调试器运行它。我在这里看到的是当你在第二次迭代中经历你的while循环时;它打印出两行代码,它从openList弹出,它调用并执行moveUp()
但是当它进入moveDown()
时就崩溃了。
它崩溃了这条线:
std::swap( temp[zPos], temp[zPos+3] );
您可能希望在调试器中检查此行代码,同时单步执行while循环检查变量和容器,以查看它们是否具有有效信息;还要检查你是不是exceeding
你的bound
的container
。您可能还想检查memory
在上次调用swap
之后调用moveUp()
后是否仍然有效。
不是在第一次打电话给moveDown()
,但是第二次打电话是你设置temp
等于puzzle
的问题,这里的问题是puzzle
的值或大小为0
。因此,当你试图在std::swap
和temp[zPos]
上调用temp[zPos+3]
时,索引无效,因为temp
有size = 0
。
您的程序的主要问题是,您将指针推送到打开列表中的本地变量。一旦保留范围,变量currentChild
将被销毁(所以只要你进入循环的下一次迭代或离开循环),然后指针指向未使用/垃圾内存。
但是,您将在其他地方遇到类似的问题,因为您无法可靠地保存指向vector<Node>
列表中任何节点的指针。这是因为std::vector
类在第一次达到一定大小时会破坏/复制其中的所有内容,这将使任何指向其中任何内容的指针无效。所以要么你只保存指向所有投币器中的节点的指针(queue
和vector
,所以只有指针被销毁/复制),或者你不保存指向节点的任何指针,而只保存节点本身 - 无论你最好的套房。
我能够通过使子节点成为Node指针的向量来修复代码,如下所示:
vector<Node*> children;
每个孩子都有一个节点指针:
Node* child = new Node(temp, this);