Значение мусора в родительском узле
Я реализую поиск в ширину, чтобы решить 8 задач. Когда я пытаюсь создать новые узлы и указать на текущий узел, используя этот указатель родительский указатель возвращает значения мусора. Это из-за аннулирования итератора? Есть ли способ обойти эту проблему, возможно, используя контейнер, отличный от вектора?
код:
#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);
}
}
}
Решение
Копирование и ссылка / указатель — разные вещи. Давайте посмотрим на одну из проблем вашего кода. Вот проблемный код:
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);
}
}
}
Для простоты давайте предположим, что в openList есть только один узел, и давайте назовем его адрес oL0. Теперь давайте шаг за шагом посмотрим, что происходит:
Node currentNode = openList.front(); // creates copy of first element in queue
Как вы уже догадались, создание копии создает новый узел с таким же внутренним состоянием. Давайте назовем адрес currentNode cN0. Важно помнить, что адреса oL0 а также cN0 разные (это разные объекты). Давайте двигаться дальше:
closedList.push(currentNode); // creates COPY of currentNode in closedList
openList.pop(); // deletes Node at address oL0
Все очень просто — closedList имеет копию currentNode по адресу, который мы можем назвать CL0.
// do stuff with currentNode (address cN0)
currentNode.moveUp();
currentNode.moveDown();
currentNode.moveRight();
currentNode.moveLeft();
Здесь кроется одна проблема. Вы меняете переменную currentNode по адресу cN0 (НЕ значение хранится closedList). По мере продвижения по вашему коду в цикле for мы можем выяснить, в чем заключается вторая проблема, ваша проблема. Смысл этого цикла for состоит в том, чтобы поместить дочерние элементы currentNode в openList:
for (/* ... */) {
// ...
// same problem of creating copies
if (/* ... */)
openList.push(currentChild);
}
}
Эти дочерние элементы имеют родительский указатель на адрес currentNode (который cN0). В конце итерации цикла while вызываются деструкторы всех локальных переменных (переменных внутри области видимости), что приводит к уничтожению currentNode. Это означает, что каждый дочерний узел в openList имеет недопустимый адрес (значение мусора, которое вы указали) своему родителю. Остерегайтесь, эта же проблема появляется внутри цикла for.
Для идей, как решить эту проблему, я советую заглянуть в Рекомендации, или, например, используя очереди указателей …
Другие решения
Других решений пока нет …