PC/UVa：110802/10181
15-Puzzle Problem
一道很难很难的题，写了3天。
经典的15数码问题，需要使用启发式搜索算法。试了3个版本的A*算法。
判断是否可解是从网上抄的，原理是个数学问题，我也没管。
代价函数H表示当前状态到目标状态的代价，这里使用曼哈顿距离，因为状态变换的唯一方法就是上下左右移动，所以曼哈顿距离没什么问题。
计算曼哈顿距离的过程中，不能计算空位置和目标位置的曼哈顿距离，否则就超时，为什么我也不知道。 不使用优先队列也会超时。
AStarVer1是根据网上流传最多的二维平面寻路算法写的。A*算法维护两个列表，一个打开列表和关闭列表，打开列表中保存待扩展的节点，关闭列表中保存已经访问过的节点。每次从打开列表中移除F值最小的节点，并加入到关闭列表中。如果最小节点是目标状态，则算法结束，否则扩展它：
如果得到在关闭列表中的节点，则不进行任何操作；如果得到在打开列表中的节点，则比较F值（也是G值），取较小的放入打开列表中；如果扩展到的节点是一个新状态，则计算F值，加入入到打开列表中；AStarVer2去掉了上一版本中的一些冗余，即使用OpenList和heap保存了两份打开列表，但是这两个之间并不存在同步更新关系。打开列表需要选取最小值，使用二叉堆比较合适，因为取最小值是O(1)的操作，这是最快的。但是一般来说二叉堆并不支持替换操作，所以上述第二点用二叉堆无法实现，但幸运的是，即使将相同状态、不同F值的节点加入到二叉堆中，仍然可以保证优先取出F值最优的那个，所以再次从二叉堆中取出相同状态的节点时并不影响。再次取出时，关闭列表中已经存在该节点了，这里都采用了直接覆盖关闭列表中较优节点的操作，这是没有问题的。如果再次取出了该结点，说明上次取出后进行的搜索操作无法得到目标状态，那么这次取出也不会。
AStarVer3是根据《算法艺术与信息学竞赛》的介绍写的算法，和之前的区别就是不使用关闭列表，而使用状态集合。当扩展出新的节点后，如果是已经出现过的状态，则比较F值，并进行相应替换操作。本质上来说并没有什么区别，因为替换的只能是打开列表中的状态，而不是关闭列表中的状态，我个人感觉是因为关闭列表是之前已经走过的状态，再次得到关闭列表中的状态时，G值一定是增大的（或者一样大？），所以不会发生替换情况。
#include <iostream> #include <vector> #include <string> #include <map> #include <queue> #include <cmath> #define NO_SOLUTION "This puzzle is not solvable." #define STR_FINAL_STATE "123456789ABCDEF0" #define FINAL_STATE 0x123456789ABCDEF0 #define SIZE 4 #define ASTAR_SOLUTION using namespace std; bool solvable(vector<vector<int>> &Puzzle) { vector<int> tiles; for (int i = 0; i < SIZE; i++) { for (int j = 0; j < SIZE; j++) { tiles.push_back(Puzzle[i][j]); } } int sum = 0, row; for (size_t i = 0; i < tiles.size(); i++) { int tile = tiles[i]; if (tile == 0) { row = (i / SIZE + 1); continue; } for (size_t m = i; m < tiles.size(); m++) if (tiles[m] < tile && tiles[m] != 0) sum++; } return !((sum + row) % 2); } #ifdef ASTAR_SOLUTION class Node { private: void swap(size_t i, size_t j); string strState; public: unsigned long long ullState, back; int F, G, H; char chDir; Node() = default; Node(const string &strState, const int G = 0); typedef Node(Node::*Move)(); Node up(); Node down(); Node left(); Node right(); void calH(const vector<vector<int>> &ManhattanDistance); }; bool operator<(const Node &n1, const Node& n2) { //标准库优先队列是最大堆，这里的逻辑是反的 //F越大，结点越小，在最大堆中越靠下 //F值相同，G越大越接近目标状态，结点越大，越靠上 if (n1.F > n2.F) return true; else if (n1.F < n2.F) return false; else{ if (n1.G > n2.G) return false; else if (n1.G < n2.G) return true; else return n1.ullState < n2.ullState; } } void Node::swap(size_t i, size_t j) { strState[i] ^= strState[j] ^= strState[i] ^= strState[j]; ullState = stoull(strState, nullptr, 16); } void Node::calH(const vector<vector<int>> &ManhattanDistance) { int idx; H = 0; for (size_t i = 0; i < strState.size(); i++) { if (strState[i] == '0'){ continue; //不对空位置计算距离，超时的原因在这里 //idx = 0; } else if (isdigit(strState[i])){ idx = strState[i] - '0'; } else idx = strState[i] - 'A' + 10; H += ManhattanDistance[idx][i]; } //1.5倍H会WA，1.33倍H会TLE，好神奇 F = G + H; } Node::Node(const string &strState, const int G) : strState(strState), ullState(0), back(0), F(0), G(G), H(0), chDir('S') { ullState = back = stoull(strState, nullptr, 16); } Node Node::up() { Node node(strState, G + 1); string::size_type blank = node.strState.find('0'); if (blank >= 4){//up node.back = ullState; node.chDir = 'U'; node.swap(blank, blank - 4); } return node; } Node Node::down() { Node node(strState, G + 1); string::size_type blank = node.strState.find('0'); if (blank <= 11){//down node.back = ullState; node.chDir = 'D'; node.swap(blank, blank + 4); } return node; } Node Node::left() { Node node(strState, G + 1); string::size_type blank = node.strState.find('0'); if (blank % 4 != 0){//left node.back = ullState; node.chDir = 'L'; node.swap(blank, blank - 1); } return node; } Node Node::right() { Node node(strState, G + 1); string::size_type blank = node.strState.find('0'); if (blank % 4 != 3){//right node.back = ullState; node.chDir = 'R'; node.swap(blank, blank + 1); } return node; } void calDistance(vector<vector<int>> &ManhattanDistance) { for (int i = 1; i <= SIZE * SIZE; i++) { for (int pos = 0; pos < SIZE * SIZE; pos++) { ManhattanDistance[i % 16][pos] = abs((i - 1) / 4 - pos / 4) + abs((i - 1) % 4 - pos % 4); } } } void insertOpenList1(priority_queue<Node> &heap, map<unsigned long long, Node> &OpenList, const Node &node) { map<unsigned long long, Node>::iterator iterOpen = OpenList.find(node.ullState); if (iterOpen != OpenList.end()){ if (node.G < iterOpen->second.G){ iterOpen->second = node; heap.push(node); } } else{ OpenList[node.ullState] = node; heap.push(node); } } void AStarVer1(const string &strInit, string &strSolution, vector<vector<int>> &ManhattanDistance) { //网上流传最广的方法，UVa运行时间1.860 priority_queue<Node> heap; map<unsigned long long, Node> OpenList; map<unsigned long long, Node> CloseList; map<unsigned long long, Node>::iterator iterClose; vector<Node::Move> MoveMethod; MoveMethod.push_back(&Node::up); MoveMethod.push_back(&Node::down); MoveMethod.push_back(&Node::left); MoveMethod.push_back(&Node::right); Node node(strInit, 0), curr; heap.push(node); OpenList[node.ullState] = node; while (!OpenList.empty()){ curr = heap.top(); if (curr.ullState == FINAL_STATE) break; if (curr.G >= 45) break; heap.pop(); OpenList.erase(curr.ullState); CloseList[curr.ullState] = curr; for (size_t i = 0; i < MoveMethod.size(); i++) { node = (curr.*(MoveMethod[i]))(); if (node.ullState == curr.ullState) continue;//无法进行该方向的移动 node.calH(ManhattanDistance); iterClose = CloseList.find(node.ullState); if (iterClose != CloseList.end()) continue;//在关闭列表中则直接跳过 insertOpenList1(heap, OpenList, node); } } if (!OpenList.empty()){ if (curr.G >= 45) strSolution.assign(NO_SOLUTION); else{ string strRev; while (curr.chDir != 'S'){ strRev.push_back(curr.chDir); curr = CloseList.find(curr.back)->second; } strSolution.assign(strRev.rbegin(), strRev.rend()); } } } void AStarVer2(const string &strInit, string &strSolution, vector<vector<int>> &ManhattanDistance) { //来自博客寂静山林，作者邱秋，略有修改，见下 //修改前UVa运行时间1.190，修改后UVa运行时间1.200 //可以去掉Ver1中的OpenList，因为和heap互相不影响 //即使维护了OpenList中节点的唯一性，也无法保证heap中节点的唯一性 //标准库提供的优先队列无法替代或者删除相同的节点，但是代价小的会被先取出 priority_queue<Node> heap; map<unsigned long long, Node> CloseList; map<unsigned long long, Node>::iterator iterClose; vector<Node::Move> MoveMethod; MoveMethod.push_back(&Node::up); MoveMethod.push_back(&Node::down); MoveMethod.push_back(&Node::left); MoveMethod.push_back(&Node::right); Node node(strInit, 0), curr; heap.push(node); while (!heap.empty()){ curr = heap.top(); if (curr.ullState == FINAL_STATE) break; if (curr.G >= 45) break; heap.pop(); CloseList[curr.ullState] = curr; for (size_t i = 0; i < MoveMethod.size(); i++) { node = (curr.*(MoveMethod[i]))(); if (node.ullState == curr.ullState) continue;//无法进行该方向的移动 node.calH(ManhattanDistance); iterClose = CloseList.find(node.ullState); if (iterClose != CloseList.end()){ //注释掉的是原博客作者的写法 //如果能以更少的步数到达一个走过的状态，则该状态需要重新扩展 //直观上感觉这种情况应该是不会出现的 //同时Ver1也证明了已经走过的状态可以直接跳过，UVa可AC /*if (node.G < iterClose->second.G){ CloseList.erase(iterClose); heap.push(node); }*/ } else{ heap.push(node); } } } if (!heap.empty()){ node = heap.top(); if (node.G >= 45) strSolution.assign(NO_SOLUTION); else{ string strRev; while (node.chDir != 'S'){ strRev.push_back(node.chDir); node = CloseList.find(node.back)->second; } strSolution.assign(strRev.rbegin(), strRev.rend()); } } else strSolution.assign(NO_SOLUTION); } void AStarVer3(const string &strInit, string &strSolution, vector<vector<int>> &ManhattanDistance) { //算法艺术与信息学竞赛中提供的写法，UVa运行时间1.480 //CloseList更改为StateList，表示所有出现过的状态，实质上将打开列表和关闭列表合并了 priority_queue<Node> heap; map<unsigned long long, Node> StateList; map<unsigned long long, Node>::iterator iterState; map<unsigned long long, Node>::iterator iter; vector<Node::Move> MoveMethod; MoveMethod.push_back(&Node::up); MoveMethod.push_back(&Node::down); MoveMethod.push_back(&Node::left); MoveMethod.push_back(&Node::right); Node node(strInit, 0), curr; heap.push(node); StateList[node.ullState] = node;//初始状态加入状态列表 while (!heap.empty()){ curr = heap.top(); if (curr.ullState == FINAL_STATE) break; if (curr.G >= 45) break; heap.pop(); //Ver1和Ver2中加入到关闭列表中的操作可以去掉 //CloseList[curr.ullState] = curr; for (size_t i = 0; i < MoveMethod.size(); i++) { node = (curr.*(MoveMethod[i]))(); if (node.ullState == curr.ullState) continue;//无法进行该方向的移动 node.calH(ManhattanDistance); iterState = StateList.find(node.ullState); if (iterState != StateList.end()){ if (node.G < iterState->second.G){ //可能替换属于打开列表中的状态 //也可能替换属于关闭列表中的状态，但是根据Ver1，这不太可能 iterState->second = node; heap.push(node); } } else{ //新状态 StateList[node.ullState] = node; heap.push(node); } } } if (!heap.empty()){ node = heap.top(); if (node.G >= 45) strSolution.assign(NO_SOLUTION); else{ string strRev; while (node.chDir != 'S'){ strRev.push_back(node.chDir); node = StateList.find(node.back)->second; } strSolution.assign(strRev.rbegin(), strRev.rend()); } } else strSolution.assign(NO_SOLUTION); } #endif int main() { int N = 0; cin >> N; vector<vector<int>> Puzzle(SIZE, vector<int>(SIZE, 0)); vector<vector<int>> ManhattanDistance(16, vector<int>(16, 0)); calDistance(ManhattanDistance); for (int n = 0; n < N; n++) { for (int i = 0; i < SIZE; i++) { for (int j = 0; j < SIZE; j++) { cin >> Puzzle[i][j]; } } #ifdef ASTAR_SOLUTION //A*算法中代价函数F = G + H //G表示从初始状态到当前状态的移动次数 //H表示从当前状态到目标状态的代价函数，是一个估计值 //因为15数码只能上下左右移动，所以代价函数可以取曼哈顿距离 if (!solvable(Puzzle)){ cout << NO_SOLUTION << endl; continue; }/**/ string strInit, strSolution; for (int i = 0; i < SIZE; i++) { for (int j = 0; j < SIZE; j++) { if (Puzzle[i][j] < 10) strInit.push_back(Puzzle[i][j] + '0'); else strInit.push_back(Puzzle[i][j] - 10 + 'A'); } } AStarVer3(strInit, strSolution, ManhattanDistance); cout << strSolution << endl; #endif } return 0; } /* 2 2 3 4 0 1 5 7 8 9 6 10 12 13 14 11 15 13 1 2 4 5 0 3 7 9 6 10 12 15 8 11 14 */