如果目標(biāo)也已知的話(huà)，用雙向BFS能很大提高速度
單向時(shí)，是 b^len的擴(kuò)展。
雙向的話(huà)，2*b^(len/2) 快了很多，特別是分支因子b較大時(shí)
至于實(shí)現(xiàn)上，網(wǎng)上有些做法是用兩個(gè)隊(duì)列，交替節(jié)點(diǎn)搜索 ×，如下面的偽代碼：
while(!empty()){
擴(kuò)展正向一個(gè)節(jié)點(diǎn)
遇到反向已經(jīng)擴(kuò)展的return
擴(kuò)展反向一個(gè)節(jié)點(diǎn)
遇到正向已經(jīng)擴(kuò)展的return
}
但這種做法是有問(wèn)題的，如下面的圖：
求S-T的最短路，交替節(jié)點(diǎn)搜索（一次正向節(jié)點(diǎn)，一次反向節(jié)點(diǎn)）時(shí)
Step 1 : S –> 1 , 2
Step 2 : T –> 3 , 4
Step 3 : 1 –> 5
Step 4 : 3 –> 5 返回最短路為4，錯(cuò)誤的，事實(shí)是3，S-2-4-T
我想，正確做法的是交替逐層搜索，保證了不會(huì)先遇到非最優(yōu)解就跳出，而是檢查完該層所有節(jié)點(diǎn)，得到最優(yōu)值。
也即如果該層搜索遇到了對(duì)方已經(jīng)訪(fǎng)問(wèn)過(guò)的，那么已經(jīng)搜索過(guò)的層數(shù)就是答案了，可以跳出了，以后不會(huì)更優(yōu)的了。
當(dāng)某一邊隊(duì)列空時(shí)就無(wú)解了。
優(yōu)化：提供速度的關(guān)鍵在于使?fàn)顟B(tài)擴(kuò)展得少一些，所以優(yōu)先選擇隊(duì)列長(zhǎng)度較少的去擴(kuò)展，保持兩邊隊(duì)列長(zhǎng)度平衡。這比較適合于兩邊的擴(kuò)展情況不同時(shí)，一邊擴(kuò)展得快，一邊擴(kuò)展得慢。如果兩邊擴(kuò)展情況一樣時(shí)，加了后效果不大，不過(guò)加了也沒(méi)事。
無(wú)向圖時(shí)，兩邊擴(kuò)展情況類(lèi)似。有向圖時(shí)，注意反向的擴(kuò)展是反過(guò)來(lái)的 x->y（如NOIP2002G2字串變換）
Code
  void gao(vector<int> &from , vector<int> &to , Hash &hash) {
 to.clear();
  for(vector<int>::iterator it = from.begin() ; it != from.end() ; it++){
利用hash判重，擴(kuò)展*it
 }
 }
int bibfs(int start , int dest){
if(start == dest){ //注意要先判相等
return 0;
}
Hash bfs , rbfs;
bfs[start] = 0;
rbfs[dest] = 0;
vector<int> Q[2] , rQ[2]; //用vector做隊(duì)列，方便遍歷
int cur = 0 , rcur = 0;
Q[cur].push_back(start);
rQ[rcur].push_back(dest);
for(int step = 1 ; step <= limit && !Q[cur].empty() && !rQ[rcur].empty(); step++){
//cout<<step<<endl;
if(Q[cur].size() <= rQ[rcur].size()){//優(yōu)先擴(kuò)展隊(duì)列長(zhǎng)度小的
gao(Q[cur],Q[cur^1],bfs);
cur ^= 1;
for(vector<int>::iterator it = Q[cur].begin() ; it != Q[cur].end() ; it++){
if(rbfs.find(*it) != rbfs.end()){
return step;
}
}
}else{
gao(rQ[rcur],rQ[rcur^1],bfs);
rcur ^= 1;
for(vector<int>::iterator it = rQ[rcur].begin() ; it != rQ[rcur].end() ; it++){
if(bfs.find(*it) != bfs.end()){
return step;
}
}
}
}
return -1;
}
 我用這種做法，做了幾道題，都沒(méi)錯(cuò)，速度還行。
按難度遞增：
hdu 1195
NOIP2002G2字串變換 注意反向的擴(kuò)展是反過(guò)來(lái)
ZOJ 1505
ZOJ 3467
/**//*
3維中，求點(diǎn)(x0,y0,z0)到(x1,y1,z1)不超過(guò)步字典序最小的路徑
一步能跳(x,y,z) 組合一下有!*8 = 48種
48^6太大了
雙向BFS 2*48^3
參照watashi的代碼寫(xiě)的
STL真神奇
vector重載了比較運(yùn)算符的
typedef map<Point , vector<Point> > Hash;
一層一層，這樣才保證正確解
這里由于兩邊結(jié)構(gòu)差不多，所以判斷隊(duì)列長(zhǎng)度的優(yōu)化效果不大
細(xì)節(jié)較多
我寫(xiě)得較挫
*/
struct Point{
int x , y , z;
Point(){}
Point(int x,int y , int z):x(x),y(y),z(z){}
bool operator < (const Point &B)const{
if(x != B.x){
return x < B.x;
}else if(y != B.y){
return y < B.y;
}else{
return z < B.z;
}
}
bool operator == (const Point &B)const{
return x == B.x && y == B.y && z == B.z;
}
Point operator +(const Point &B)const{
return Point(x+B.x , y+B.y, z+B.z);
}
};
typedef map<Point , vector<Point> > Hash;
vector<Point> dir;
void init(int x ,int y , int z){
int d[] = {x, y, z};
sort(d,d+3);
dir.clear();
do{
for(int mask = 0 ; mask < 8 ; mask ++){
int nx = (mask & 1) ? d[0] : -d[0];
int ny = (mask & 2) ? d[1] : -d[1];
int nz = (mask & 4) ? d[2] : -d[2];
dir.push_back(Point(nx,ny,nz));
}
}while(next_permutation(d,d+3));
}
void gao(vector<Point> &from , vector<Point> &to , Hash &bfs){
to.clear();
int len = bfs[*from.begin()].size();
for(vector<Point>::iterator it = from.begin() ; it != from.end() ; it++){
Hash::iterator preIt = bfs.find(*it);
for(int k = 0 ; k < 48 ; k++){
Point next = *it + dir[k];
Hash::iterator nextIt = bfs.find(next);
if(nextIt == bfs.end()){
bfs[next] = preIt->second;
to.push_back(next);
}else if(!(nextIt->second.front() == next || nextIt->second.back() == next) //注意需要判斷這個(gè)，因?yàn)殚L(zhǎng)度=len的可能是之前的
&& nextIt->second.size() == len && nextIt->second > preIt->second){
nextIt->second = preIt->second;
}
}
}
}
void bibfs(vector<Point> &ans , Point &start , Point &dest){
if(start == dest){
ans.push_back(start);
return;
}
Hash bfs , rbfs;
bfs[start].push_back(start);
rbfs[dest].push_back(dest);
vector<Point> Q[2] , rQ[2];
//for(int i = 0 ; i < 2 ; i ++){
// Q[i].reserve(1000);
// rQ[i].reserve(1000);
//}
int cur = 0 , rcur = 0;
Q[cur].push_back(start);
rQ[rcur].push_back(dest);
for(int step = 0 ; ans.empty() && !Q[cur].empty() && step < 6 ; step++){
if(Q[cur].size() <= rQ[cur].size()){
gao(Q[cur],Q[cur^1],bfs);
cur ^= 1;
//chk
for(int i = 0 ; i < Q[cur].size() ; i++){
Point &val = Q[cur][i];
Hash::iterator fit = bfs.find(val);
Hash::iterator rfit = rbfs.find(val);
if(rfit != rbfs.end()){
vector<Point> tmp = fit->second;
tmp.insert(tmp.end() , rfit->second.begin(), rfit->second.end());
if(ans.empty() || tmp < ans){
ans = tmp;
}
}
fit->second.push_back(val);//push
}
} else {
gao(rQ[rcur],rQ[rcur^1],rbfs);
rcur ^= 1;
//chk
for(int i = 0 ; i < rQ[rcur].size() ; i++){
Point &val = rQ[rcur][i];
Hash::iterator rfit = rbfs.find(val);
Hash::iterator fit = bfs.find(val);
if(fit != bfs.end()){
vector<Point> tmp = rfit->second;
tmp.insert(tmp.begin() , fit->second.begin() , fit->second.end());
if(ans.empty() || tmp < ans){
ans = tmp;
}
}
rfit->second.insert(rfit->second.begin(),val);//push
}
}
}
}
int main()
{
//freopen("in","r",stdin);
//freopen("out","w",stdout);
int x0,y0,z0,x1,y1,z1,x,y,z;
while(~scanf("%d%d%d%d%d%d%d%d%d",&x0,&y0,&z0,&x1,&y1,&z1,&x,&y,&z)){
init(x,y,z);
vector<Point> ans;
Point start(x0,y0,z0) , dest(x1,y1,z1);
bibfs(ans , start , dest);
printf("To get from (%d,%d,%d) to (%d,%d,%d) takes " , x0,y0,z0,x1,y1,z1);
if(ans.empty()){
printf("more than 6 3D knight moves (%d,%d,%d).\n",x,y,z);
}else{
printf("%d 3D knight moves (%d,%d,%d): ",ans.size()-1,x,y,z);
for(int i = 0 ; i < ans.size() ; i++){
if(i)printf(" => ");
printf("(%d,%d,%d)",ans[i].x,ans[i].y,ans[i].z);
}
puts(".");
}
}
return 0;
}
Poj 3131
/**//*
如圖所示，問(wèn)從初始狀態(tài)變化到目標(biāo)狀態(tài)，不超過(guò)步
規(guī)模比較大
狀態(tài)總數(shù)為：*6^8 1個(gè)為E，其余格子每個(gè)種可能
我這里用了enum，這樣編碼會(huì)直觀點(diǎn)吧
用二進(jìn)制編碼，每三位bit代表一個(gè)格子
狀態(tài)很多，要用雙向BFS，優(yōu)先選擇隊(duì)列長(zhǎng)度小的擴(kuò)展，否則會(huì)超時(shí)
還有注意判重時(shí)，用了Hash，節(jié)點(diǎn)要用靜態(tài)數(shù)組！！！
之前每次都make_pair()就超時(shí)了！！！
map判重也超時(shí)了
*/
enum Board {RBW, BRW, RWB, WRB, BWR, WBR, E};//0,1,
const int MAXN = 500007;
struct Node{
int pos;
short val;
Node *next;
};
Node nodes[MAXN*20] , *pN;
struct Hash{
Node* hash[MAXN];
vector<int> vt;
void init(){
for(vector<int>::iterator it = vt.begin() ; it != vt.end() ; it++){
hash[*it] = NULL;
}
vt.clear();
}
void add(int pos , short val){
int mod = pos % MAXN;
if(hash[mod] == NULL){
vt.push_back(mod);
}
pN->pos = pos;
pN->val = val;
pN->next = hash[mod];
hash[mod] = pN++;
//assert(pN < nodes + MAXN*20);
}
short find(int pos){
int loc = pos % MAXN;
Node *p = hash[loc];
while(p != NULL ){
if(p->pos == pos){
return p->val;
}
p = p->next;
}
return -1;
}
};
Hash bfs , rbfs;
int bin[10];
int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};
Board change[6][4] = {
{RWB, WBR, RWB, WBR},
{BWR, WRB, BWR, WRB},
{RBW, BWR, RBW, BWR},
{WBR, BRW, WBR, BRW},
{BRW, RWB, BRW, RWB},
{WRB, RBW, WRB, RBW}
};
#define iset(val,pos,x) (val ^= val & bin[pos] , val |= x << 3*(pos) )
#define get(val,pos) ((val >> 3*(pos) ) & 7)
inline bool out(int x , int y){
return x < 0 || x >= 3 || y < 0 || y >= 3;
}
void gao(vector<int> &from , vector<int> &to , Hash &hash){
to.clear();
for(vector<int>::iterator it = from.begin() ; it != from.end() ; it++){
int &board = *it;
int pos , x , y , step = hash.find(board);
for(int i = 0 ;i < 9 ; i++){
if(get(board,i) == E){
pos = i;
y = i / 3;
x = i % 3;
break;
}
}
for(int k = 0 ; k < 4 ; k ++){
int xx = x + dx[k];
int yy = y + dy[k];
if(out(xx,yy)){
continue;
}
int next = board;
int nextPos = yy * 3 + xx , val = get(next, nextPos);
iset(next,pos,change[val][k]);
iset(next,nextPos,E);
if(hash.find(next) == -1){
hash.add(next,step+1);
to.push_back(next);
}
}
}
}
int bibfs(int &start , int dest[2]){
vector<int> Q[2] , rQ[2];
int cur = 0 , rcur = 0;
pN = nodes;
bfs.init();
rbfs.init();
bfs.add(start,0);
Q[cur].push_back(start);
int pos = 0;
while(get(dest[0], pos) != E){
pos++;
}
for(int mask = 0 ; mask < (1<<9) ; mask++){
if((mask>>pos) & 1){
continue;
}
int next = 0;//init 0 !!!
for(int i = 0 ;i < 9 ; i ++){
iset(next, i, get(dest[(mask>>i)&1], i) );
}
if(next == start){
return 0;
}
rbfs.add(next,0);
rQ[rcur].push_back(next);
}
for(int step = 1 ; step <= 30 ; step++){
if(Q[cur].size() <= rQ[rcur].size()){//
gao(Q[cur],Q[cur^1],bfs);
cur ^= 1;
for(vector<int>::iterator it = Q[cur].begin() ; it != Q[cur].end() ; it++){
if(rbfs.find(*it) != -1){
return step;
}
}
}else{
gao(rQ[rcur],rQ[rcur^1],rbfs);
rcur ^= 1;
for(vector<int>::iterator it = rQ[rcur].begin() ; it != rQ[rcur].end() ; it++){
if(bfs.find(*it) != -1){
return step;
}
}
}
}
return -1;
}
int main()
{
//freopen("in","r",stdin);
//freopen("out","w",stdout);
bin[0] = 7;
for(int pos = 1 ; pos < 9 ; pos++){
bin[pos] = bin[pos-1]<<3;
}
for(int x,y;scanf("%d%d",&x,&y) , x != 0;){
x--;
y--;
int dest[2] , start = 0;
for(int i = 0; i < 3 ; i ++){
for(int j = 0 ; j < 3 ; j++){
char ch;
scanf(" %c",&ch);
if(ch == 'W'){
iset(dest[0],3*i+j,RBW);
iset(dest[1],3*i+j,BRW);
}else if(ch == 'B'){
iset(dest[0],3*i+j,RWB);
iset(dest[1],3*i+j,WRB);
}else if(ch == 'R'){
iset(dest[0],3*i+j,BWR);
iset(dest[1],3*i+j,WBR);
}else{
iset(dest[0],3*i+j,E);
iset(dest[1],3*i+j,E);
}
}
}
iset(start, 3*y+x, E);
cout<<bibfs(start , dest)<<endl;
}
return 0;
}
CII 3010
雙向bfs很快，能排第3
用變進(jìn)制判重會(huì)快點(diǎn)...
|