如果目标也已知的话,用双向BFS能很大提高速度
单向时,是 b^len的扩展。
双向的话,2*b^(len/2) 快了很多,特别是分支因子b较大时
至于实现上,网上有些做法是用两个队列,交替节点搜索 ×,如下面的伪代码: while(!empty()){
扩展正向一个节点
遇到反向已经扩展的return
扩展反向一个节点
遇到正向已经扩展的return
}
但这种做法是有问题的,如下面的图:
求S-T的最短路,交替节点搜索(一次正向节点,一次反向节点)时
Step 1 : S –> 1 , 2
Step 2 : T –> 3 , 4
Step 3 : 1 –> 5
Step 4 : 3 –> 5 返回最短路为4,错误的,事实是3,S-2-4-T
我想,正确做法的是交替逐层搜索,保证了不会先遇到非最优解就跳出,而是检查完该层所有节点,得到最优值。 也即如果该层搜索遇到了对方已经访问过的,那么已经搜索过的层数就是答案了,可以跳出了,以后不会更优的了。 当某一边队列空时就无解了。
优化:提供速度的关键在于使状态扩展得少一些,所以优先选择队列长度较少的去扩展,保持两边队列长度平衡。这比较适合于两边的扩展情况不同时,一边扩展得快,一边扩展得慢。如果两边扩展情况一样时,加了后效果不大,不过加了也没事。
无向图时,两边扩展情况类似。有向图时,注意反向的扩展是反过来的 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判重,扩展*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做队列,方便遍历 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()){//优先扩展队列长度小的 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; }
我用这种做法,做了几道题,都没错,速度还行。
按难度递增:
hdu 1195
NOIP2002G2字串变换 注意反向的扩展是反过来
ZOJ 1505
ZOJ 3467
/**//* 3维中,求点(x0,y0,z0)到(x1,y1,z1)不超过步字典序最小的路径 一步能跳(x,y,z) 组合一下有!*8 = 48种 48^6太大了 双向BFS 2*48^3
参照watashi的代码写的 STL真神奇 vector重载了比较运算符的 typedef map<Point , vector<Point> > Hash;
一层一层,这样才保证正确解 这里由于两边结构差不多,所以判断队列长度的优化效果不大 细节较多 我写得较挫 */ 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) //注意需要判断这个,因为长度=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
/**//* 如图所示,问从初始状态变化到目标状态,不超过步 规模比较大 状态总数为:*6^8 1个为E,其余格子每个种可能 我这里用了enum,这样编码会直观点吧 用二进制编码,每三位bit代表一个格子
状态很多,要用双向BFS,优先选择队列长度小的扩展,否则会超时 还有注意判重时,用了Hash,节点要用静态数组!!! 之前每次都make_pair()就超时了!!! map判重也超时了 */
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 用变进制判重会快点...
|