(注:这是一篇学习笔记,其实是写的第2遍.昨晚3点多快要收尾时,电脑啪的一声关机了.当我想起用的编辑器是gedit时,一口鲜血很华丽地喷在屏幕上.只怪我手欠没用vim..因为得重新写一遍,所以很多地方简化了很多.你完全可以挑着想看的看,没有什么影响.)
宽度优先搜索
宽搜与深搜一道,是最简便的图搜索算法之一.这一算法也是其他很多重要的搜索算法的原型.诸如带贪婪的搜索,双向搜索,A*搜索等,其实都可以认为是基于宽度优先搜索的.之所以称之为宽度优先,是因为算法每次扩展的节点都是当前节点的直接后继,也就是说,算法首先搜索和s距离为k的所有节点,然后才搜索和s距离为k+1的所有节点.因此,宽搜找到的必定是最短路径.下面是宽度优先搜索的伪代码:
声明两个空的链表: Open 和 Closed.
将起始节点压入Open 表中.
While Open表非空:
移出Open表首元素X.
If X为目标节点:
跳出While循环,将X压入Closed表中,返回成功信息.
Else 继续.
For X的所有直接后继节点Y.
将Y压入Open表尾.
将X压入Closed表中.
End While
对于宽搜,我们并不关心其复杂度,因为宽搜实际上使用得并不多.当然,如果你有兴趣的话,可以参考<Artificial Intelligence : A Modern Approach>这本书.我们更多的是关心宽搜能解决些什么问题.用宽搜解决迷宫问题是数据结构课上的内容,下面的问题你可以思考下如何解决:
[题目]魔板(via: sicily 1150)由8个大小相同方块组成,分别用涂上不同颜色,用1到8的数字表示。
其初始状态是
1 2 3 4
8 7 6 5
对魔板可进行三种基本操作:
A操作(上下行互换):
8 7 6 5
1 2 3 4
B操作(每次以行循环右移一个):
4 1 2 3
5 8 7 6
C操作(中间四小块顺时针转一格):
1 7 2 4
8 6 3 5
用上述三种基本操作,可将任一种状态装换成另一种状态。
编写一程序,对于给定的目标态,输入到达的最短路径上的所有基本操作序列.不能到达输出-1.
深度优先搜索
和宽度优先搜索不一样的是,深度优先搜索的搜索策略是尽可能深地搜索图.换句话说,深搜其实就是在搜索树的每一层始终先扩展一个子节点,不断地递归该过程,直到不能再牵及,然后才从当前节点返回到上一级节点,沿另一方向继续搜索.需要注意的是,深搜的搜索策略是不完备的,而且,深搜得到的解并不一定就是最优解.下面是深度优先搜索的伪代码(注意它与宽搜的异同):
声明两个空的链表: Open 和 Closed.
将起始节点压入Open 表中.
While Open表非空:
移出Open表首元素X.
If X为目标节点:
跳出While循环,将X压入Closed表中,返回成功信息.
Else 继续.
For X的所有直接后继节点Y.
将Y压入Open表首.
将X压入Closed表中.
End While
我们可以看到,深搜和宽搜的代码基本上是一样的,也许实现上,对于数据结构的选择可以会有略微不同.因为深搜得到的结果可能是局部最优的,因此除非深搜的完备性很清楚,一般用宽搜而不是深搜.
[题目]下面是一个来自<the art of java>的题目,你可以试着使用深搜解决它:
航班问题:一位顾客要预定一张从New York到Los Angeles的航班机票,下面是航班线路,请你为顾客找一种购票方案。
航班 距离
New York到Chicago 900英里
Chicago到Denver 1000英里
New York到Toronto 500英里
New York到Denver 1800英里
Toronto到Calgary 1700英里
Toronto到Los Angeles 2500英里
Toronto到Chicago 500英里
Denver到Urbana 1000英里
Denver到Houston 1000英里
Houston到Los Angeles 1500英里
Denver到Los Angeles 1000英里
带贪心的搜索
带贪心的搜索其实是指在搜索时,算法根据某信息进行贪心搜索.如dijkstra算法.它与A*算法类似,但是却没有使用启发函数.贪心算法和动态规划一样,更多的是一种思想,如何使用则需灵活选择.比如,在马周游问题中,可以每次选择8连节点(马最多可以跳往8个方向)中入度最小的那个节点进行扩展.这里,节点Y的入度指能跳到它的节点X的个数,已跳过的X不算.找出贪心策略需要有比较清晰的理解,最好的办法就是多做些题.
[题目] 马周游问题 (via: sicily 1152)
在一个5 * 6的棋盘中的某个位置有一只马,如果它走29步正好经过除起点外的其他位置各一次,这样一种走法则称马的周游路线,试设计一个算法,从给定的起点出发,找出它的一条周游路线.
为了便于表示一个棋盘,我们按照从上到下,从左到右对棋盘的方格编号,如下所示:
对输入的每一个起点,求一条周游线路.对应地输出一行,有30个整数,从起点开始按顺序给出马每次经过的棋盘方格的编号.
双向搜索
双向搜索是指搜索同时在正反两个方向进行,正反向定义为:
正向搜索:从起始节点向目标节点搜索
反向搜索:从目标节点向起始节点搜索
注意,双向搜索中,正反两个方向是交替进行的,当两个方向上搜索到同一子节点时,程序结束.该子节点我们一般称为"相交点",可以证明,如果存在从起始节点到目标节点的最优路径,那么双向搜索的两个方向必定相交,从起始节点到相交点再到目标节点的路径即是最优路径.双向搜索的伪代码如下:
创建Open队列和Closed队列
将起始节点压入Open队列,将目标节点压入Closed队列
While
移出Open队列首元素X
For X的所有直接后继节点Y
If Y是否已经搜索过
跳出While循环,输出成功信息
Else 将Y压入Open队列中
End For
移出Closed队列首元素X'
For X'的所有直接后继节点Y'
If Y'是否已经搜索过
跳出While循环,输出成功信息
Else 将Y'压入Closed队列中
End For
End While
使用双向搜索可以让程序更快,比如下面的八数码问题,如果双向搜索函数写的好的话,它甚至于比下文要介绍的A*算法还快,在sicily上提交,0.01秒过了,暴爽.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 | /* source code of submission 273100, Zhongshan University Online Judge System */ #include <stdlib.h> #include <map> #include <iostream> #include <deque> using namespace std; deque<int> Dsrc,Ddes; map<int,int> Msrc,Mdes; int cur[9],nxt[9],zero,state,nxt_sta,floor,dir[4]={-1,1,-3,3}; void num2array(int s,int n[],int len) { for(int i=len-1;i>=0;i--) { n[i]=s%10; s/=10; } } void array2num(int &s,int n[],int len) { int res=0; for(int i=0;i<len;i++) { res=n[i]+res*10; } s=res; } void swap(int &x,int &y) { int tmp=x; x=y; y=tmp; } bool isreachable(int sta[],int len) { int res=0; for(int i=0;i<len;i++) { if(sta[i]==0) continue; for(int j=i+1;j<len;j++) { if(sta[j]==0) continue; if(sta[j]<sta[i]) res++; } } return (res%2==0); } bool check(int pos,int i) { switch (i) { case 1: if(pos!=0&&pos!=3&&pos!=6) return true; return false; case 2: if(pos!=2&&pos!=5&&pos!=8) return true; return false; case 3: if(pos!=0&&pos!=1&&pos!=2) return true; return false; case 4: if(pos!=6&&pos!=7&&pos!=8) return true; return false; } } void initial() { Dsrc.clear(); Ddes.clear(); Msrc.clear(); Mdes.clear(); state=123456780; num2array(state,cur,9); Dsrc.push_back(state); floor=0; Msrc[state]=floor; for(int i=0;i<=8;i++) cin>>cur[i]; for(int i=0;i<=8;i++) nxt[i]=0; array2num(state,cur,9); Ddes.push_back(state); floor=0; Mdes[state]=floor; nxt_sta=0; zero=0; } int find0(int sta[],int len) { for(int i=0;i<len;i++) if(sta[i]==0) return i; } int solve() { if(state==123456780) return 0; if(!isreachable(cur,9)) return -1; int tmp; while(1) { while(Msrc[Dsrc.front()]==floor) { tmp=Dsrc.front(); Dsrc.pop_front(); num2array(tmp,cur,9); zero=find0(cur,9); for(int i=1;i<=4;i++) { for(int j=0;j<=8;j++) nxt[j]=cur[j]; if(check(zero,i)) { swap(nxt[zero],nxt[zero+dir[i-1]]); array2num(nxt_sta,nxt,9); if(Msrc.find(nxt_sta)!=Msrc.end()) continue; if(Mdes.find(nxt_sta)!=Mdes.end()) return floor+Mdes[nxt_sta]+1; Dsrc.push_back(nxt_sta); Msrc[nxt_sta]=floor+1; } } } while(Mdes[Ddes.front()]==floor) { tmp=Ddes.front(); Ddes.pop_front(); num2array(tmp,cur,9); zero=find0(cur,9); for(int i=1;i<=4;i++) { for(int j=0;j<=8;j++) nxt[j]=cur[j]; if(check(zero,i)) { swap(nxt[zero],nxt[zero+dir[i-1]]); array2num(nxt_sta,nxt,9); if(Mdes.find(nxt_sta)!=Mdes.end()) continue; if(Msrc.find(nxt_sta)!=Msrc.end()) return floor+Msrc[nxt_sta]+1; Ddes.push_back(nxt_sta); Mdes[nxt_sta]=floor+1; } } } floor++; } } int main() { int n; cin>>n; while(n--) { initial(); cout<<solve()<<endl; } } |
[题目]八数码问题(via: sicily 1378)求从初始状态,如下:
1 2 3
4 5 6
7 8 0
到某一目标状态所需的最少步数,每次可将0与某一相邻位置(上、下、左、右)的数字互换。
A*搜索
你可以参考这篇A*搜索相对完整的介绍: 对于A*算法的一些疑问,还有这篇,A*算法中启发函数的使用.
A*算法适用性很强,但要注意的是,相同的问题可以找出不同的启发函数,使用不同的启发函数的A*算法效率差别是很大的,更多的时候,我们必须在这些启发函数中找到较好的那一个,并且保证它是相容(consistent)的.A*算法的伪代码请参考上面的两个链接,下面直接给出一道例题.
[题目] Rush Hour (via: rush hour 本地下载)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 | #include <iostream> #include <vector> #include <deque> #include <algorithm> #include <map> using namespace std; #define max 6+1 // for every map[][] #define num 8+1 // num of cars #define impossible 99999 int car[num]; // = 1 or 2, 1:left/right, 2:up/down int map_tmp[max][max]; int map_nxt[max][max]; //temp for next map int map_src[max][max]; // source of the map, only written once int id;//id++ hash double factor=1; // store every car's position; pos_x[2] : start pos, pos_y[2] : end pos struct Car_Pos { int pos_x[2],pos_y[2]; }car_pos[num]; struct info { int id; int father; int map[max][max]; int route[2];// which car(route[0]) goes which dir(route[1]) comes to this map, 1:left 3:right 2:up 4:down double g,h,f;//f=g+h, and h is always fo car1 } info_tmp,info_src,info_nxt; // info_tmp is the father pf info_nxt map<int,info> Mtable; deque<struct info> Dopen,Dclosed; int hash_id(int m[max][max]); void initial() { Dopen.clear(); Dclosed.clear(); Mtable.clear(); for(int i=1;i<=max-1;i++) // from 1 to 100 { for(int j=1;j<=max-1;j++) // from 1 to 100 { cin>>map_src[i][j]; info_src.map[i][j]=map_src[i][j]; } } id=hash_id(map_src); info_src.id=id; info_src.father=-1; info_src.g=0; // info_src.h=0; info_src.f=0; info_src.h=impossible; info_src.f=factor*info_src.h+info_src.g; if(Mtable.find(id)==Mtable.end()) { Dopen.push_back(info_src); Mtable[id]=info_src; } } //whether the car in position (pos_x,pos_y) can expand to direction (dir) or not, true for yes, vice verse bool check_dir(int pos_x,int pos_y,int dir,int m[max][max],int t) // dir:1/3/2/4, 1:left 3:right 2:up 4:down { switch(dir) { case 1: // go left { if(pos_y>1) { if(m[pos_x][pos_y-1]==t) return true; else return false; } return false; } case 3: // go right { if(pos_y<max-1) { if(m[pos_x][pos_y+1]==t) return true; else return false; } return false; } case 2: // go up { if(pos_x>1) { if(m[pos_x-1][pos_y]==t) return true; else return false; } return false; } case 4: // go down { if(pos_x<max-1) { if(m[pos_x+1][pos_y]==t) return true; else return false; } return false; } } } void get_cars_info() { for(int i=1;i<=max-1;i++) // from 1 to 100 { for(int j=1;j<=max-1;j++)// from 1 to 100 { if(map_src[i][j]!=0) { int temp=map_src[i][j]; for(int k=1;k<=4;k++) { if(check_dir(i,j,k,map_src,temp)) { if(k%2==1) car[temp]=1; else car[temp]=2; break; } } } } } } // to calculate hash for every map,making sure no two maps shares same hash,and one map goes with one hash,actually it is more like a mess int hash_id(int m[max][max]) { int id=0; for(int j=1;j<=max-1;j++) { for(int k=1;k<=max-1;k++) { int temp=j*max+k; // no meaning,just a fun temp*=temp; temp+=3; id=id+m[j][k]*temp; } } return id; } void find_car1(int m[max][max],int &pos_x,int &pos_y) // car1 can only goes left or right, up or down is impossible { for(int i=max-1;i>=0;i--) // from 100 to 1, to find car1 quicker using the hint before { for(int j=max-1;j>=0;j--) // from 100 to 1 { if(m[i][j]==1) // car1 found { pos_x=i; pos_y=j; return; } } } } int calc_h(struct info t) // calc h for t using its map infomation { int pos_x,pos_y; find_car1(t.map,pos_x,pos_y); // the pos of car1 int temp1=0,temp2=max-1-pos_y; for(int i=pos_y+1;i<=max-1;i++) // from pos_y+1 to 100 { if(t.map[pos_x][i]!=0) temp1++; } return temp1+temp2; } int cmp(const struct info &t1,const struct info &t2) { if(t1.f!=t2.f) return t1.f<t2.f; else return t1.h<t2.h; } void get_every_car_pos(int m[max][max]) { for(int i=1;i<=max-1;i++) // get the left/right cars info { int j=1; while(j<=max-1) { // while(j<=max-1&& m[i][j]==0 ) while(j<=max-1&& (m[i][j]==0 || car[m[i][j]]!=1)) { j++; } if(j>max-1) break; int no_of_car=m[i][j]; car_pos[no_of_car].pos_x[0]=i; car_pos[no_of_car].pos_x[1]=j; while(j<=max-1&&m[i][j]==no_of_car) { j++; } car_pos[no_of_car].pos_y[0]=i; car_pos[no_of_car].pos_y[1]=j-1; } } for(int i=1;i<=max-1;i++) // get the up/down cars info { int j=1; while(j<=max-1) { //while(j<=max-1&& m[j][i]==0 ) while(j<=max-1&& (m[j][i]==0 || car[m[j][i]]!=2)) { j++; } if(j>max-1) break; int no_of_car=m[j][i]; car_pos[no_of_car].pos_x[0]=j; car_pos[no_of_car].pos_x[1]=i; while(j<=max-1&&m[j][i]==no_of_car) { j++; } car_pos[no_of_car].pos_y[0]=j-1; car_pos[no_of_car].pos_y[1]=i; } } } void a_star() { while(1) { if(Dopen.size()==0){ cout<<endl; cout<<"Sorry,Dead lock!"<<endl; return ; } //info_tmp=Dopen.front(); deque<info>::iterator ptr; ptr=min_element(Dopen.begin(),Dopen.end(),cmp); info_tmp=(*ptr); Dclosed.push_back(info_tmp); //Dopen.pop_front(); Dopen.erase(ptr); //if(the_end(info_tmp.map)==true) if(info_tmp.h==0) { cout<<endl; cout<<"The min moves will be : "<<info_tmp.g<<endl; vector<int>Vcar; vector<int>Vdir; while(info_tmp.father!=-1) { Vcar.push_back(info_tmp.route[0]); Vdir.push_back(info_tmp.route[1]); info_tmp=Mtable[info_tmp.father]; } for(int i=Vcar.size()-1;i>=0;i--) { cout<<"Car"<<Vcar[i]<<" moves "; switch(Vdir[i]) { case 2: cout<<"up"<<endl; break; case 4: cout<<"down"<<endl; break; case 1: cout<<"left"<<endl; break; case 3: cout<<"right"<<endl; break; } } return ; } get_every_car_pos(info_tmp.map); for(int i=1;i<=num-1;i++)// for every car { int pos_x[2]={car_pos[i].pos_x[0],car_pos[i].pos_x[1]}; int pos_y[2]={car_pos[i].pos_y[0],car_pos[i].pos_y[1]}; if(car[i]==1) // cari goes left/right { if(pos_x[1]>1&&info_tmp.map[pos_x[0]][pos_x[1]-1]==0) // cari goes left { for(int j=1;j<=max-1;j++) { for(int k=1;k<=max-1;k++) { info_nxt.map[j][k]=info_tmp.map[j][k]; } } info_nxt.map[pos_x[0]][pos_x[1]-1]=i; info_nxt.map[pos_y[0]][pos_y[1]]=0; info_nxt.g=info_tmp.g+1; info_nxt.h=calc_h(info_nxt); info_nxt.f=info_nxt.g+factor*info_nxt.h; info_nxt.father=info_tmp.id; id=hash_id(info_nxt.map); info_nxt.id=id; info_nxt.route[1]=1; // 1:left 3:right 2:up 4:down info_nxt.route[0]=i; if(Mtable.find(id)==Mtable.end()) { Mtable[id]=info_nxt; Dopen.push_back(info_nxt); } } if(pos_y[1]<max-1&&info_tmp.map[pos_y[0]][pos_y[1]+1]==0) // cari goes right { for(int j=1;j<=max-1;j++) { for(int k=1;k<=max-1;k++) { info_nxt.map[j][k]=info_tmp.map[j][k]; } } info_nxt.map[pos_y[0]][pos_y[1]+1]=i; info_nxt.map[pos_x[0]][pos_x[1]]=0; info_nxt.g=info_tmp.g+1; info_nxt.h=calc_h(info_nxt); info_nxt.f=info_nxt.g+factor*info_nxt.h; info_nxt.father=info_tmp.id; id=hash_id(info_nxt.map); info_nxt.id=id; info_nxt.route[1]=3;// 1:left 3:right 2:up 4:down info_nxt.route[0]=i; if(Mtable.find(id)==Mtable.end()) { Mtable[id]=info_nxt; Dopen.push_back(info_nxt); } } } if(car[i]==2) // cari goes up/down { if(pos_x[0]>1&&info_tmp.map[pos_x[0]-1][pos_x[1]]==0) // cari goes up { for(int j=1;j<=max-1;j++) { for(int k=1;k<=max-1;k++) { info_nxt.map[j][k]=info_tmp.map[j][k]; } } info_nxt.map[pos_x[0]-1][pos_x[1]]=i; info_nxt.map[pos_y[0]][pos_y[1]]=0; info_nxt.g=info_tmp.g+1; info_nxt.h=calc_h(info_nxt); info_nxt.f=info_nxt.g+factor*info_nxt.h; info_nxt.father=info_tmp.id; id=hash_id(info_nxt.map); info_nxt.id=id; info_nxt.route[1]=2;// 1:left 3:right 2:up 4:down info_nxt.route[0]=i; if(Mtable.find(id)==Mtable.end()) { Mtable[id]=info_nxt; Dopen.push_back(info_nxt); } } if( pos_y[0]<max-1 && info_tmp.map[pos_y[0]+1][pos_y[1]]==0) // cari goes down { for(int j=1;j<=max-1;j++) { for(int k=1;k<=max-1;k++) { info_nxt.map[j][k]=info_tmp.map[j][k]; } } info_nxt.map[pos_y[0]+1][pos_y[1]]=i; info_nxt.map[pos_x[0]][pos_x[1]]=0; info_nxt.g=info_tmp.g+1; info_nxt.h=calc_h(info_nxt); info_nxt.f=info_nxt.g+factor*info_nxt.h; info_nxt.father=info_tmp.id; id=hash_id(info_nxt.map); info_nxt.id=id; info_nxt.route[1]=4;// 1:left 3:right 2:up 4:down info_nxt.route[0]=i; if(Mtable.find(id)==Mtable.end()) { Mtable[id]=info_nxt; Dopen.push_back(info_nxt); } } } } // sort(Dopen.begin(),Dopen.end(),cmp); //push_heap(Dopen.begin(),Dopen.end(),cmp); } } int main() { cout<<"Please input the map of "<<max-1<<"*"<<max-1<<": "<<endl; initial(); get_cars_info(); a_star(); cout<<endl; } |