qq_44907188
Ta,suo
采纳率0%
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;

}

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

相关推荐