реализация жадного решения и 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. Однако после второго узла все узлы в моей очереди с приоритетами указывают на только что развернутый узел! Они должны указывать на их отдельных родителей, и не должны быть связаны друг с другом. Я не могу понять, где я иду не так, и любая помощь будет оценена. Спасибо!