[LeetCode]Sliding Puzzle

这道题要我们求最少的move数使得我们可以solve它。这道题我们每次可以进行的操作就是，0和其相邻的tile互换，所以我们根据这一点每次找当前状态的邻接节点即可。时间空间复杂度均为O(4^d)，d为从当前状态到目标状态的最小距离。代码如下：

	class Solution {
	public:
	int slidingPuzzle(vector<vector<int>>& board) {
	int m = board.size(), n = board[0].size(), layer = 0, pos = 0;
	string target = "123450";
	for(int i = 0; i < m; ++i)
	for(int j = 0; j < n; ++j)
	if(!board[i][j])pos = i * n + j;
	//BFS
	queue<pair<string, int>> q;
	q.push(make_pair(getKey(board), pos));
	unordered_set<string> visited;
	while(q.size())
	{
	int len = q.size(), i = 0;
	while(i++ < len)
	{
	auto p = q.front();
	q.pop();
	visited.insert(p.first);
	if(p.first == target)return layer;
	auto neighbors = adj(p.first, p.second, m, n);
	for(auto& neighbor : neighbors)
	{
	if(visited.find(neighbor.first) == visited.end())
	q.push(neighbor);
	}
	}
	++layer;
	}
	return -1;
	}
	private:
	string getKey(vector<vector<int>>& board)
	{
	string key;
	for(auto& row : board)
	for(auto& cell : row)
	key += to_string(cell);
	return key;
	}
	vector<pair<string, int>> adj(string state, int pos, int m, int n)
	{
	int i = pos / n, j = pos % n;
	pair<int, int> dirs[4] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
	vector<pair<string, int>> neighbors;
	for(int k = 0; k < 4; ++k)
	{
	int x = i + dirs[k].first, y = j + dirs[k].second;
	if(x >= 0 && x < m && y >= 0 && y < n)
	{
	string s = state;
	swap(s[pos], s[x * n + y]);
	neighbors.push_back(make_pair(s, x * n + y));
	}
	}
	return neighbors;
	}
	};

view raw Sliding Puzzle_bfs.cpp hosted with ❤ by GitHub

另外一种做法是A* search，在bfs或者其他非启发式搜索的时候我们keep track of的都是当前状态从开始状态转移过来已经travel的距离g(n)。但是A* search，作为启发式搜索算法，会在搜索的时候考虑估算从当前节点到目标节点的距离，也就是启发方程，heuristic fucniton h(n)。我们在搜索的时候，不再是单纯地考虑已经走过的距离，而是将两者结合在一起:

• f(n) = g(n) + h(n)

其中g(n)代表的是从初始节点到达当前节点走过的距离，h(n)代表的是当前节点到目标节点的估算距离。这里h(n)有几个性质:

• 如果h(n)从来不高估从当前节点到目标节点的距离的话，可以保证让我们找到最优解。我们称这种h(n)为admissble heuristic
• 如果h(n)满足h(n)  <= h(n') + w(n, n')，其中n和n'为相邻节点，w(n, n')为两个节点边的权重，我们称h(n)为consistent或者monotone。那么当我们跑类似dijkstra算法从priority queue上展开节点的时候，到当前节点的最短路径就被找到了。因为f(n) = g(n) + h(n) <= g(n) + h(n') + w(n, n') = g(n') + h(n') = f(n')，也就是说，f(n)在任意一条路径上都是递增的，那么我们只需要用类似dijkstra的证明方法证明即可，这里不做赘述
• 如果h是consistent的并且在目标节点处为0，那么其一定是admissible的。假设n节点经过v1，v2...组成的最短路径到达目标节点t，我们有h(n) <= h(v1) + w(v1, n) <= h(v2) + w(v1, v2) + w(v1, n) <= ... <= shortestPath(n, t) + h(t) = shortestPath(n, t)，这对任意n都成立，证明完毕

回归到这一题，我们可以用所有除了0以为的tile距离目标位置的曼哈顿距离的和做heuristic function，那么h(n)一定是consistent并且admissible的:

• 在目标节点处h为0
• 我们每次只能讲一个tile和0互换，从n状态变为n'，cost为1，这样最多只能把h(n)到h(n')减小1。所以满足h(n)  <= h(n') + w(n, n')

所以我们只需要按照这个f(n)进行A star search即可，实现的话用priority queue，时间复杂度O(d log d)，d为最短路径，因为所有f(n)小于d的节点都会被展开。代码如下:

	class Solution {
	public:
	int slidingPuzzle(vector<vector<int>>& board) {
	int m = board.size(), n = board[0].size(), pos = 0;
	string target = "123450";
	for(int i = 0; i < m; ++i)
	for(int j = 0; j < n; ++j)
	if(!board[i][j])pos = i * n + j;
	//A* search
	priority_queue<pair<int, pair<string, int>>, vector<pair<int, pair<string, int>>>, greater<pair<int, pair<string, int>>>> pq;
	string state = getState(board);
	int estimatedDist = h(state, m, n);
	pq.push({estimatedDist, {state, pos}});
	unordered_set<string> visited;
	while(pq.size())
	{
	auto p = pq.top();
	pq.pop();
	if(visited.find(p.second.first) != visited.end())continue;
	visited.insert(p.second.first);
	if(p.second.first == target)return p.first;
	auto neighbors = adj(p.second.first, p.second.second, m, n, p.first + 1);
	for(auto& neighbor : neighbors)
	{
	if(visited.find(neighbor.second.first) == visited.end())
	pq.push(neighbor);
	}
	}
	return -1;
	}
	private:
	string getState(vector<vector<int>>& board)
	{
	string key;
	for(auto& row : board)
	for(auto& cell : row)
	key += to_string(cell);
	return key;
	}
	int h(string state, int m, int n)
	{
	int dist = 0;
	for(int k = 0; k < state.size(); ++k)
	{
	if(state[k] != '0')
	{
	int i = k / n, j = k % n;
	int targetPos = state[k] - '0' - 1, x = targetPos / n, y = targetPos % n;
	dist += abs(x - i) + abs(y - j);
	}
	}
	return dist;
	}
	vector<pair<int, pair<string, int>>> adj(string state, int pos, int m, int n, int distTravelled)
	{
	int i = pos / n, j = pos % n;
	pair<int, int> dirs[4] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
	vector<pair<int, pair<string, int>>> neighbors;
	for(int k = 0; k < 4; ++k)
	{
	int x = i + dirs[k].first, y = j + dirs[k].second;
	if(x >= 0 && x < m && y >= 0 && y < n)
	{
	string s = state;
	swap(s[pos], s[x * n + y]);
	int estimatedDist = h(s, m, n);
	neighbors.push_back({distTravelled - h(state, m, n) + estimatedDist, {s, x * n + y}});
	}
	}
	return neighbors;
	}
	};

view raw Sliding Puzzle_a_star.cpp hosted with ❤ by GitHub