Astars算法的基本思想是:
定义合适的代价函数gx和启发式函数hx,当gx和hx都满足条件时,Astars算法就可以保证得到最优解。
我对状态的定义如下:
状态由名为Node的结构体表示,其中包含一个三行三列的二维数组A,A中0的坐标x0、y0,Astars算法相关的fx、gx、hx参数组成。
gx意味到达该状态移动的次数,hx为启发式函数,这里设定为不在位的数字的数量,这个条件从不高估从节点x到目标节点的实际代价。八数字中的0表示空位。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39
| struct Node { int A[3][3]; int x0; int y0; int gx; int hx; int fx; bool visited;
Node(Node* existNode) { if (existNode != nullptr) { for (int i = 0; i < 3; i++) { for (int j = 0; j < 3; j++) { this->A[i][j] = existNode->A[i][j]; } } this->x0 = existNode->x0; this->y0 = existNode->y0; this->gx = existNode->gx; this->hx = existNode->hx; this->fx = existNode->fx; this->visited = false; } } Node() { for (int i = 0; i < 3; i++) { for (int j = 0; j < 3; j++) { this->A[i][j] = i + j * 3; } } this->x0 = 0; this->y0 = 0; this->gx = 0; this->hx = 0; this->fx = 0; this->visited = false; } }
|
在运行过程中,现对初始状态进行判断,若不是目标状态,进行Astars算法(调用search函数)。先通过x0,y0定位0的位置,进行状态拓展(expand函数,根据当前状态复制一个node,然后调整相关参数,包括移动的两个数字,0的坐标,fx gx hx)。之后通过排序算法选取fx最小的状态,进行判断。
这个过程中涉及到两个关键问题:一是如何避免产生重复的状态,二是排序的效率问题(代码通过洛谷的相应题目进行检验,排序效率过低会Time Limit Exceed)。
对于“如何避免产生重复状态”的问题,8数码问题可以用字符串区分不同状态的字符串。采用同一种方式给各个状态编码。我在Node类内定义了一个序列化函数serialize(),将当前状态的数组转换为一个字符串。额外使用unordered_set对转换后的序列进行哈希存储。当要拓展新状态时,查找unordered_set对象中,是否有与新状态序列化的结果相同的序列。查找到则不拓展这个状态。
| unordered_set<string> visitedStates; Node* newNode = expand(x + 1, y, current, B); if (visitedStates.find(newNode->serialize()) == visitedStates.end()) { nodeQueue.push(newNode); visitedStates.insert(newNode->serialize()); }
|
对于“排序的效率问题”,我先在忽略效率问题的前提下,采用了O(n)的遍历策略。之后(现版本)采用了std标准库中的priority_queue,自定义了CompareNode进行元素优先级的比较。具体定义为:
| priority_queue<Node*, vector<Node*>, CompareNode> nodeQueue;
|
Node表示容器中包含的元素类型为Node;vector<Node*>为优先队列的容器模板;CompareNode为自定义的比较逻辑,不实现时默认使用std::less创造最大堆。我们这里要使fx最小的排最前面,优先取出,因此用Node1->fx > Node2->fx。具体定义为
| struct CompareNode { bool operator()(Node* a, Node* b) { return a->fx > b->fx; } };
|
各个元素在被取出后从优先队列中删除。
另外,虽然行列的设置只要统一,行列反了也不影响,如果反了,就是在对矩阵转置,目标状态和当前状态对应的两个矩阵都会转置,在解题逻辑中没有影响。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191
| #include <iostream> #include <vector> #include <unordered_set> #include <queue> #include <string>
using namespace std;
struct Node { int A[3][3]; int x0; int y0; int gx; int hx; int fx;
Node(Node* existNode) { if (existNode != nullptr) { for (int i = 0; i < 3; i++) { for (int j = 0; j < 3; j++) { this->A[i][j] = existNode->A[i][j]; } } this->x0 = existNode->x0; this->y0 = existNode->y0; this->gx = existNode->gx; this->hx = existNode->hx; this->fx = existNode->fx; } } Node() { for (int i = 0; i < 3; i++) { for (int j = 0; j < 3; j++) { this->A[i][j] = i + j * 3; } } this->x0 = 0; this->y0 = 0; this->gx = 0; this->hx = 0; this->fx = 0; }
string serialize() const { string s; for (int i = 0; i < 3; i++) { for (int j = 0; j < 3; j++) { s += to_string(A[i][j]); } } return s; } };
struct CompareNode { bool operator()(Node* a, Node* b) { return a->fx > b->fx; } };
int compareMap(Node* node, int target[3][3]) { int count = 0; for (int j = 0; j < 3; j++) { for (int i = 0; i < 3; i++) { if (target[i][j] != 0 && node->A[i][j] != target[i][j]) { count += 1; } } } return count; }
Node* expand(int tx, int ty, Node* node, int target[3][3]) { Node* newNode = new Node(node); newNode->A[node->x0][node->y0] = newNode->A[tx][ty]; newNode->A[tx][ty] = 0; newNode->x0 = tx; newNode->y0 = ty; newNode->gx = node->gx + 1; newNode->hx = compareMap(newNode, target); newNode->fx = newNode->gx + newNode->hx; return newNode; }
int search(Node* node, int target[3][3]) { priority_queue<Node*, vector<Node*>, CompareNode> nodeQueue; unordered_set<string> visitedStates;
nodeQueue.push(node); visitedStates.insert(node->serialize());
while (!nodeQueue.empty()) { Node* current = nodeQueue.top(); nodeQueue.pop();
if (compareMap(current, target) == 0) return current->gx;
int x = current->x0; int y = current->y0;
if (x <= 1) { Node* newNode = expand(x + 1, y, current, target); if (visitedStates.find(newNode->serialize()) == visitedStates.end()) { nodeQueue.push(newNode); visitedStates.insert(newNode->serialize()); } else { delete newNode; } } if (x >= 1) { Node* newNode = expand(x - 1, y, current, target); if (visitedStates.find(newNode->serialize()) == visitedStates.end()) { nodeQueue.push(newNode); visitedStates.insert(newNode->serialize()); } else { delete newNode; } } if (y <= 1) { Node* newNode = expand(x, y + 1, current, target); if (visitedStates.find(newNode->serialize()) == visitedStates.end()) { nodeQueue.push(newNode); visitedStates.insert(newNode->serialize()); } else { delete newNode; } } if (y >= 1) { Node* newNode = expand(x, y - 1, current, target); if (visitedStates.find(newNode->serialize()) == visitedStates.end()) { nodeQueue.push(newNode); visitedStates.insert(newNode->serialize()); } else { delete newNode; } } delete current;
} return -1; }
int main() { Node* initS = new Node; char temp = '0'; for (int i = 0; i < 3; i++) { for (int j = 0; j < 3; j++) { cin >> temp; initS->A[i][j] = (int)temp - (int)'0'; if (initS->A[i][j] == 0) { initS->x0 = i; initS->y0 = j; } } }
int C[9] = { 1, 2, 3, 8, 0, 4, 7, 6, 5 }; int B2[3][3]; for (int j = 0; j < 3; j++) { for (int i = 0; i < 3; i++) { B2[i][j] = C[3 * i + j]; } }
initS->gx = 0; initS->hx = compareMap(initS, B2); cout << search(initS, B2) << endl;
return 0; }
|