A*

轉自http://www.mamicode.com/info-detail-1534200.html

康托展開

X = a[1]*(n-1)!+a[2]*(n-2)!+...+a[i]*(n-i)!+...+a[n-1]*1!+a[n]*0!

其中a[i]表示在num[i+1..n]中比num[i]小的數的數量

逆康托展開

由于：

a[i]≤n-i, a[i]*(n-i)!≤(n-i)*(n-i)!<(n-i+1)!

于是我們得到：

對于X=a[1]*(n-1)!+a[2]*(n-2)!+...+a[i]*(n-i)!+...+a[n-1]*1!+a[n]*0!

中的a[i]來說，無論a[i+1..n]的值為多少，其后面的和都不會超過(n-i)!

eg：當i=1? 所以X約等于a[1]*(n-1)! +后面

X除以(n-1)!，得到商c和余數r。其中c就等于a[1]，r則等于后面的部分

這樣依次求解，就可以得到a[]數組了！

比如求解3的全排列中，編號為3的排列：

3 / 2! = 1 ... 1 => a[1] = 1

1 / 1! = 1 ... 0 => a[2] = 1

0 / 0! = 0 ... 0 => a[3] = 0

之后我們回想一下a[i]和含義??

a[i]表示在num[i+1..n]中比num[i]小的數的數量

對于已經排好序的序列比如

 {1, 2, 3},

a[] = {1, 1, 0}

unused = {1, 2, 3}, a[1] = 1, num[1] = 2

unused = {1, 3}, a[2] = 1, num[2] = 3

unused = {1}, a[3] = 0, num[3] = 1

=> 2, 3, 1

解釋看http://www.mamicode.com/info-detail-1534200.html?

講得很好

代碼也很易懂

#include <algorithm>
#include <cstring>
#include <string.h>
#include <iostream>
#include <list>
#include <map>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <queue>
#include <vector>
#include <cstdio>
#include <cmath>#define LL long long
#define N 100005
#define INF 0x3ffffffusing namespace std;int factor[]={1,1,2,6,24,120,720,5040,40320};
vector<int>stnum; //八數碼某個狀態序列
int destination; //目標狀態康托展開值struct state
{int f; //評估值和狀態值的總和。int g; //從起始狀態到當前狀態的最少步數int h; //評估函數int k; //該狀態康托展開值state(int f,int g,int h,int k):f(f),g(g),h(h),k(k){};friend bool operator<(state a,state b){if(a.f!=b.f)return a.f>b.f;else return a.g>b.g;}
};int cantor(vector<int>num) //康托展開
{int k = 0;int n = 9;for(int i=0;i<n;i++) {int tp = 0;for(int j = i+1; j < n; j++) {if(num[j] < num[i]) {tp++;}}k += tp * factor[n-1-i];}return k;
}vector<int> recantor(int k) //逆康托展開
{vector<int>num;int a[10];int n = 9;bool used[10];memset(used,false,sizeof(used));for(int i=0;i<n;i++){a[i] = k / factor[n-1-i];k %= factor[n-1-i];int cnt = 0;for(int j=0;j<n;j++){if(!used[j]) {cnt++;if(a[i] + 1==cnt) {num.push_back(j);used[j] = true;break;}}}}return num;
}int pos[]={8,0,1,2,3,4,5,6,7};int getdis(int a,int b) //曼哈頓距離
{return (abs(a/3-b/3)+abs(a%3-b%3));//a/3-b/3行差，a%3-b%3列差
}int get_evaluation(vector<int>num) //評估函數
{//評估函數設定為1-8八數字當前位置到目標位置的曼哈頓距離之和。 比如其中就有當前位置的1和目標位置的1 的曼哈頓距離之和//目標式1 2 3 4 5 6 7 8 0//此時 pos[1]=0 ,表示在目標式中1原本應該在第0位 從而推出0應該在第8位 對應pos[0] 所以pos的作用是 映射這個數字在目標式子中的位置，所以要偏移//當前   2 4 7 6 8 0 1 3 5//因此 i 表示 在當前式子中這個數字的位置  比如2 是第0位 4 是第1位int h=0;for(int i=;i<9;i++){h+=getdis(i,pos[num[i]]);}return h;
}void solve()
{priority_queue<state>openlist;set<int>closelist; //在closelist中，拋棄該狀態。while(!openlist.empty()) openlist.pop();closelist.clear();int h=get_evaluation(stnum);openlist.push(state(h,0,h,cantor(stnum)));int step=0; //統計步數bool flag=false; //標記是否能找到目標狀態while(!openlist.empty()){state cur=openlist.top(); //從openlist中取出F值最小的狀態openlist.pop();int k=cur.k;//cur的康托展開 closelist.insert(k); //將該狀態加入closelist if(destination==k) {//若該狀態為目標狀態，結束搜索flag=true; //找到目標狀態step=cur.g; //步數break;}vector<int> st = recantor(k); //當前狀態的八數碼序列for(int i=0;i<9;i++) if(st[i]==0) //找到0的位置{if(i%3!=2) { //不在行末，0位可以和右邊相鄰位置交換swap(st[i],st[i+1]);int x = cantor(st);int g = cur.g+1;int h = get_evaluation(st);int f = g + h;if(closelist.find(x)==closelist.end()) {openlist.push(state(f,g,h,x));}swap(st[i],st[i+1]);//又要換回來來進行下面的步驟}if(i%3!=0) { //不在某行開頭，可以和左邊相鄰位置交換swap(st[i],st[i-1]);int x = cantor(st);int g = cur.g+1;int h = get_evaluation(st);int f = g + h;if(closelist.find(x)==closelist.end()) {openlist.push(state(f,g,h,x));}swap(st[i],st[i-1]);}if(i<6) {swap(st[i],st[i+3]);int x = cantor(st);int g = cur.g+1;int h = get_evaluation(st);int f = g + h;if(closelist.find(x)==closelist.end()) {openlist.push(state(f,g,h,x));}swap(st[i],st[i+3]);}if(i>2) {swap(st[i],st[i-3]);int x = cantor(st);int g = cur.g+1;int h = get_evaluation(st);int f = g + h;if(closelist.find(x)==closelist.end()) {openlist.push(state(f,g,h,x));}swap(st[i],st[i-3]);}}}if(!flag) cout << "No Solution!" << endl;else cout<<step<<endl;}int main() {vector <int> des;for(int i=0;i<8;i++) des.push_back(i+1);des.push_back(0);destination=cantor(des);int T;cin >> T;while(T--){int a;stnum.clear();for(int i=0;i<9;i++) {cin>>a; stnum.push_back(a);}solve();}return 0;
}

通常A* 還有一個更新

對于第n個F

即 if(F>g(n)+1+H(n-1))? F=g(n)+1+H(n-1)