＜＜人工智能导论＞＞上机--A*解决八数码问题

A*算法的精髓：
$$f(n)=g(n)+h(n)$$
$h(n)$是当前状态$n$到目标状态的曼哈顿距离和。利用堆优化$BFS$即可。还可以在$BFS$时记录前驱，然后倒着找到路线方案。

/*
* @author:  codancer
* @createTime:  2020-11-28, 17:31:10
*/

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
const ll mod = 1e9+7;
#define pb push_back
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define fep(i,a,b) for(int i=(a);i>=(b);i--)
#define deb(x) cerr<<#x<<" = "<<(x)<<"\n"
typedef vector<int> VI;
typedef vector<ll> VII;
typedef pair<int,int> pii;
mt19937_ rng(chrono::steady_clock::now().time_since_epoch().count());
ll Rand(ll B) {
	return (ull)rng() % B;
}
struct Status{
	vector<vector<int> > bd;
	int g;//实际花费
	int h;//预期花费
	//估价函数g+h
};
bool operator<(Status a,Status b){
	return a.g+a.h>b.g+b.h;
}
map<vector<vector<int> >, int > vis;
priority_queue<Status> q;
int h(vector<vector<int> > bd){//计算当前局面的估价函数
	int ans=0;
	for(int i=0;i<3;i++){
		for(int j=0;j<3;j++){
			if(bd[i][j]==1) ans+=(i+j);
			if(bd[i][j]==2) ans+=i+abs(j-1);
			if(bd[i][j]==3) ans+=i+abs(j-2);
			if(bd[i][j]==4) ans+=abs(i-1)+abs(j-2);
			if(bd[i][j]==5) ans+=abs(i-2)+abs(j-2);
			if(bd[i][j]==6) ans+=abs(i-2)+abs(j-1);
			if(bd[i][j]==7) ans+=abs(i-2)+j;
			if(bd[i][j]==8) ans+=abs(i-1)+j;
		}
	}
	return ans;
}
vector<vector<int> > target={{1,2,3},{8,0,4},{7,6,5}};
int dir[4][2]={{-1,0},{0,1},{0,-1},{1,0}};
map<vector<vector<int>>,vector<vector<int>> > pre;
int A_star(vector<vector<int> > board){
	q.push({board,0,h(board)});
	while(!q.empty()){
		Status now=q.top();q.pop();
		if(vis[now.bd]) continue;
		vis[now.bd]=1;
		if(now.bd==target){
			return now.g;
		}
		vector<vector<int> > q_board=now.bd;//当前局势

		int zx,zy;//0所在的位置
		for(int i=0;i<3;i++){
			for(int j=0;j<3;j++){
				if(q_board[i][j]==0){
					zx=i;
					zy=j;
				}
			}
		}

		for(int i=0;i<4;i++){
			int dx=zx+dir[i][0];
			int dy=zy+dir[i][1];
			if(dx>=0&&dx<3&&dy>=0&&dy<3){
				vector<vector<int> > nxt_board=q_board;
				swap(nxt_board[dx][dy],nxt_board[zx][zy]);
				if(vis[nxt_board]) continue;
				pre[nxt_board]=q_board;
				q.push({nxt_board,now.g+1,now.g+1+h(nxt_board)});
			}
		}
	}
	return -1;

}
vector<vector<int> > board;
int main(){
	int x;
	for(int i=0;i<3;i++){
		vector<int> row;
		for(int j=0;j<3;j++){
			cin>>x;
			row.pb(x);
		}
		board.pb(row);
	}
	cout<<"最少步数"<<endl;
	cout<<A_star(board)<<endl;
	for(int i=0;i<3;i++){
		for(int j=0;j<3;j++){
			cout<<board[i][j]<<' ';
		}
		cout<<endl;
	}
	cout<<endl;
	vector<vector<vector<int> > > order;
	map<vector<vector<int>> ,int> cnt;
	while(target!=board){
		order.pb(target);
		target=pre[target];
	}
	reverse(order.begin(),order.end());
	for(auto v:order){
		for(int i=0;i<3;i++){
			for(int j=0;j<3;j++){
				cout<<v[i][j]<<' ';
			}
			cout<<endl;
		}
		cout<<endl;
	}
	return 0;
}