Двойно-связанный список. Изменение родительского указателя.

реализация жадного решения и 8-головоломок

Greedy.h:

class Greedy {
const string Goal = "12345678_";
State current;
string startState;
int nodesCreated, nodesExpanded;
priority_queue<State> greedyQueue;
set<string> visited;
stack<string> solutionStack;
public:
Greedy(const string start);
~Greedy();
void doGreedy();
};

Greedy.cpp:

tuple<int, int> getTarget(int n);Greedy::Greedy(const string start) : startState(start), nodesCreated(0), nodesExpanded(0) {}

Greedy::~Greedy() {}

void Greedy::doGreedy() {
greedyQueue.emplace(startState, "");
while (!greedyQueue.empty()) {
current = greedyQueue.top();
greedyQueue.pop();
if (visited.find(current.stateString) == visited.end()) {
visited.insert(current.stateString);
if (current.stateString == Goal) {  //end has been reached, calculate path, print out stats, and end.
cout << "Solution Found!" << endl;
//solutionStack.push(current.moveFromParent);
State* tempParent = current.parent;
while ( solutionStack.size() < 20 && tempParent != NULL) {
solutionStack.push(tempParent->moveFromParent);
tempParent = tempParent->parent;
}
break;
}
vector<State> childrenFound = current.expandNode();
for (int i = 0; i < childrenFound.size(); ++i) {    // for each child found, add it to the priority queue, set its parent, and set it as a child of parent
State temp = childrenFound[i];
if (visited.find(temp.stateString) == visited.end()) {  // We haven't been here before, put it in the queue
greedyQueue.push(temp);
}
}
}
}
cout << "Last 20 moves:" << endl;
while (!solutionStack.empty()) {
cout << solutionStack.top() << endl;
solutionStack.pop();
}
}

State.h:

class State {
public:
string moveFromParent;
State* parent;
string stateString;
int distance;
State();
State(const string str, State * _parent, string _moveFromParent);
State (const string str, string _moveFromParent);
State(const string str, int dist, State * _parent, string _moveFromParent);
~State();

bool operator<(const State & state) const;
bool operator==(const State & state) const;
int findBlank();
vector<State> expandNode();
};

State.cpp:

int manhattan(const string str);
tuple<int, int> getTarget(int n);

State::State() {}

State::State(const string str, State * _parent, string _moveFromParent) : stateString(str), moveFromParent(_moveFromParent) {
parent = _parent;
}

State::State(const string str, string _moveFromParent) : stateString(str), moveFromParent(_moveFromParent) {
parent = NULL;
distance = manhattan(stateString);
}

State::State(const string str, int dist, State* _parent, string _moveFromParent) : stateString(str), distance(dist), moveFromParent(_moveFromParent) {
parent = _parent;
distance = manhattan(stateString);
}

State::~State() {}

bool State::operator<(const State & state) const {
return distance > state.distance;
}

bool State::operator==(const State & state) const {
return ((stateString == state.stateString));
}

int State::findBlank() {
for (int i = 0; i < stateString.length(); ++i) {
if (stateString[i] == '_') {
return i;
}
}
}

vector<State> State::expandNode() {
vector<State> returnStates;
int blank = findBlank();
if (blank % 3 > 0) { // can move left
string newState = stateString;
newState[blank] = newState[blank - 1];
newState[blank - 1] = '_';
int heuristic = manhattan(newState);
State * childsParent = this;
string move = "left";
State temp = State(newState, heuristic, childsParent, move);
returnStates.push_back(temp);
}
if (blank % 3 < 2) { //can move right
string newState = stateString;
newState[blank] = newState[blank + 1];
newState[blank + 1] = '_';
int heuristic = manhattan(newState);
State * childsParent = this;
string move = "right";
State temp = State(newState, heuristic, childsParent, move);
returnStates.push_back(temp);
}
if (blank / 3 > 0) { //can move up
string newState = stateString;
newState[blank] = newState[blank - 3];
newState[blank - 3] = '_';
int heuristic = manhattan(newState);
State * childsParent = this;
string move = "up";
State temp = State(newState, heuristic, childsParent, move);
returnStates.push_back(temp);
}
if (blank / 3 < 2) { // can move down
string newState = stateString;
newState[blank] = newState[blank + 3];
newState[blank + 3] = '_';
int heuristic = manhattan(newState);
State * childsParent = this;
string move = "down";
State temp = State(newState, heuristic, childsParent, move);
returnStates.push_back(temp);
}
return returnStates;
}

int manhattan(const string str) {
int distance = 0;
for (int i = 0, length = str.length(); i != length; ++i) {
tuple<int, int> target;
if (str[i] == '_') {
target = { 2, 2 };
}
else {
int temp = str[i] - '0';
target = getTarget(temp);
}
tuple<int, int> current = getTarget(i + 1);
int localSum = abs(get<0>(current) - get<0>(target)) + abs(get<1>(current) - get<1>(target));
distance += localSum;
}
return distance;
}

tuple<int, int> getTarget(int n) {
return { (n - 1) / 3, (n - 1) % 3 };
}

У меня проблема, когда указатель на родительский элемент State изменяется, когда я расширяю больше узлов.

State имеет переменную-член State * parent. Это используется для возврата к началу после нахождения решения, чтобы получить движение решения.

После развертывания первого узла приоритетная очередь выглядит нормально, причем родительский узел всех узлов является корневым, родитель которого равен NULL. Однако после второго узла все узлы в моей очереди с приоритетами указывают на только что развернутый узел! Они должны указывать на их отдельных родителей, и не должны быть связаны друг с другом. Я не могу понять, где я иду не так, и любая помощь будет оценена. Спасибо!

1

Решение

Проблема в Greedy::doGreedy и ваше использование current,

Назначение current = greedyQueue.top(); создает копию верхнего объекта в очереди. Позже, когда вы звоните vector<State> childrenFound = current.expandNode();все возвращенные состояния имеют родительские указатели, которые ссылаются на current, На следующей итерации цикла вы делаете это назначение current опять же, изменение родителя, на которое указывают все эти возвращенные состояния.

С вашим кодом нелегко это исправить. Вы должны переосмыслить, как вы храните State объекты, так что родительские объекты остаются вокруг и неизменными. Часто такого рода вещи выполняются с помощью стека или списка, добавляя каждый узел в конец и выталкивая их, чтобы перейти к родителю.

1

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

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

По вопросам рекламы ammmcru@yandex.ru
Adblock
detector