Значение мусора в родительском узле

Question

Значение мусора в родительском узле

Я реализую поиск в ширину, чтобы решить 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);
}
}
}

-1

8-puzzle breadth-first-search c++pointers this

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

Копирование и ссылка / указатель — разные вещи. Давайте посмотрим на одну из проблем вашего кода. Вот проблемный код:

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.

Для идей, как решить эту проблему, я советую заглянуть в Рекомендации, или, например, используя очереди указателей …

1