###### Ta,suo

2020-04-06 21:26 阅读 80

# 请教大神以下代码哪部分是控制最后要到的状态的？

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

using namespace std;

class Board;

class Solver;

class Board

{

``````friend class Solver;

friend class compare_node;
``````

public:

``````typedef enum

{

TL_SPACE,

TL_1,

TL_2,

TL_3,

TL_4,

TL_5,

TL_6,

TL_7,

TL_8,

}TILE;

Board()

{

for (int i = 0; i != 8; tiles.push_back(TILE(++i)));

tiles.push_back(TL_SPACE);

}

Board(int t[3][3])

{

for (int i = 0; i != 3; ++i)

for (int j = 0; j != 3; ++j)

tiles.push_back(TILE(t[i][j]));

}

int hamming()

{

int count = 0;

for (int i = 0; i != tiles.size(); ++i)

if (tiles[i] != TILE((i + 1)) && tiles[i] != TL_SPACE)

++count;

return count;

}

int manhattan()

{

int count = 0;

int num;

for (int i = 0; i != tiles.size(); ++i)

{

if (tiles[i] == TL_SPACE)

continue;

num = (tiles[i] + 8) % 9;

count = count + (abs(num / 3 - i / 3) + abs(num % 3 - i % 3));

}

return count;

}

bool equals(const Board &b) const

{

bool ret = true;

for (int i = 0; i != b.tiles.size(); ++i)

{

if (this->tiles[i] != b.tiles[i])

{

ret = false;

break;

}

}

return ret;

}

void neighbors(vector<Board> &nghbrs)

{

nghbrs.clear();

int pos = 0;

for (; pos != tiles.size() && tiles[pos] != TL_SPACE; ++pos);

int row = pos / 3;

int col = pos % 3;

if (row > 0)

{

nghbrs.push_back(*this);

nghbrs.back().swap(pos, (row - 1) * 3 + col);

}

if (row < 2)

{

nghbrs.push_back(*this);

nghbrs.back().swap(pos, (row + 1) * 3 + col);

}

if (col > 0)

{

nghbrs.push_back(*this);

nghbrs.back().swap(pos, row * 3 + col - 1);

}

if (col < 2)

{

nghbrs.push_back(*this);

nghbrs.back().swap(pos, row * 3 + col + 1);

}

}

string toString()

{

string s;

ostringstream convert;

for (int i = 0; i != tiles.size(); ++i)

convert << static_cast<int>(tiles[i]) << " ";

s = convert.str();

return s;

}
``````

private:

``````vector<TILE> tiles;

Board *parent = nullptr;

int f = 0;

int g = 0;

int h = 0;

void swap(size_t pos1, size_t pos2)

{

if (pos1 >= tiles.size() || pos2 >= tiles.size())

throw runtime_error("position not match");

std::swap(tiles[pos1], tiles[pos2]);

}
``````

};

// function used to compared board in heap

class compare_node

{

public:

``````bool operator()(Board *&l, Board *&r)

{

return l->f > r->f;

}
``````

};

// vector for board pointers

class bvector : public vector

{

public:

``````bvector()

{

make_heap(this->begin(), this->end(), compare_node());

}

void push_node(Board *b)

{

this->push_back(b);

push_heap(this->begin(), this->end(), compare_node());

}

void pop_node()

{

pop_heap(this->begin(), this->end(), compare_node());

this->pop_back();

}
``````

};

class Solver

{

``````friend class Board;
``````

public:

``````Solver() = default;

Solver(Board *p) : initial(p) {}

void init()

{

if (initial == nullptr)

{

cerr << "Solver not initialized" << endl;

return;

}

if (!isSolvable())

{

cerr << "No solution existed" << endl;

return;

}

initial->g = 0;

initial->h = initial->manhattan() + initial->hamming();

initial->f = initial->g + initial->h;

open_ref[initial->toString()] = initial;

open_set.push_node(initial);

while (!open_set.empty())

{

Board *closed_node = open_set.front();

open_ref.erase(closed_node->toString());

closed_ref[closed_node->toString()] = closed_node;

open_set.pop_node();

if (closed_node->equals(*end))

{

Board *p = closed_node;

while (p->parent != nullptr)

{

solution.push_back(p->toString());

p = p->parent;

}

solution.push_back(initial->toString());

reverse(solution.begin(), solution.end());

return;

}

vector<Board> neighbors;

closed_node->neighbors(neighbors);

for (auto iter = neighbors.begin(); iter != neighbors.end(); ++iter)

{

Board *new_node = new Board(*iter);

new_node->g = 0;

new_node->h = new_node->manhattan() + new_node->hamming();

new_node->f = new_node->f + new_node->h;

// ignore the neighbor which is already evaluated.

if (closed_ref.find(new_node->toString()) != closed_ref.end())

{

delete new_node;

continue;

}

if (open_ref.find(new_node->toString()) != open_ref.end())

{

delete new_node;

continue;

}

new_node->parent = closed_node;

open_set.push_node(new_node);

open_ref[new_node->toString()] = new_node;

}

}

return;

}

vector<string> getSolution()

{

return solution;

}

// http://www.geeksforgeeks.org/check-instance-8-puzzle-solvable/

// It is not possible to solve an instance of 8 puzzle if the number of inversions is odd

// in the initial state

bool isSolvable()

{

int count = 0;

for (int i = 0; i != initial->tiles.size(); ++i)

for (int j = i + 1; j != initial->tiles.size(); ++j)

if (initial->tiles[i] != Board::TILE::TL_SPACE &&

initial->tiles[j] != Board::TILE::TL_SPACE &&

static_cast<int>(initial->tiles[i]) > static_cast<int>(initial->tiles[j]))

++count;

return (count % 2 == 0);

}

~Solver()

{

delete initial;

delete end;

for (auto iter = open_ref.begin(); iter != open_ref.end(); ++iter)

delete iter->second;

for (auto iter = closed_ref.begin(); iter != closed_ref.end(); ++iter)

delete iter->second;

}
``````

private:

``````Board *initial = nullptr;

Board *end = new Board();

bvector open_set;

unordered_map<string, Board*> open_ref;

unordered_map<string, Board*> closed_ref;

vector<string> solution;
``````

};

int main()

{

``````int t1[3][3] = { { 1, 2, 3 },{ 4, 5, 6 },{ 8, 7, 0 } };

int t2[3][3] = { { 8, 1, 3 },{ 4, 0, 2 },{ 7, 6, 5 } };

Board *b1 = new Board(t1);

Board *b2 = new Board(t2);

Solver s1(b1);

Solver s2(b2);

s1.init();

s2.init();

auto ret2 = s2.getSolution();

cout << "The solution to " << b1->toString() << endl;

for (auto str : ret2)

cout << str << endl;

system("PAUSE");

return 0;
``````

}

• 点赞
• 写回答
• 关注问题
• 收藏
• 复制链接分享