IDAstar搜索
2011-01-17 09:45:21 来源:WEB开发网 闂傚倸鍊搁崐鎼佸磹閹间礁纾归柟闂寸绾惧綊鏌熼梻瀵割槮缁炬儳缍婇弻鐔兼⒒鐎靛壊妲紒鐐劤缂嶅﹪寮婚悢鍏尖拻閻庨潧澹婂Σ顔剧磼閻愵剙鍔ょ紓宥咃躬瀵鎮㈤崗灏栨嫽闁诲酣娼ф竟濠偽i鍓х<闁绘劦鍓欓崝銈囩磽瀹ュ拑韬€殿喖顭烽幃銏ゅ礂鐏忔牗瀚介梺璇查叄濞佳勭珶婵犲伣锝夘敊閸撗咃紲闂佺粯鍔﹂崜娆撳礉閵堝洨纾界€广儱鎷戦煬顒傗偓娈垮枛椤兘骞冮姀銈呯閻忓繑鐗楃€氫粙姊虹拠鏌ュ弰婵炰匠鍕彾濠电姴浼i敐澶樻晩闁告挆鍜冪床闂備胶绮崝锕傚礈濞嗘挸绀夐柕鍫濇川绾剧晫鈧箍鍎遍幏鎴︾叕椤掑倵鍋撳▓鍨灈妞ゎ厾鍏橀獮鍐閵堝懐顦ч柣蹇撶箲閻楁鈧矮绮欏铏规嫚閺屻儱寮板┑鐐板尃閸曨厾褰炬繝鐢靛Т娴硷綁鏁愭径妯绘櫓闂佸憡鎸嗛崪鍐簥闂傚倷娴囬鏍垂鎼淬劌绀冮柨婵嗘閻﹂亶姊婚崒娆掑厡妞ゃ垹锕ら埢宥夊即閵忕姷顔夐梺鎼炲労閸撴瑩鎮橀幎鑺ョ厸闁告劑鍔庢晶鏇犵磼閳ь剟宕橀埞澶哥盎闂婎偄娲ゅù鐑剿囬敃鈧湁婵犲﹤鐗忛悾娲煛鐏炶濡奸柍瑙勫灴瀹曞崬鈻庤箛鎾寸槗缂傚倸鍊烽梽宥夊礉鎼达絽鍨濇い鏍仜妗呴梺鍛婃处閸ㄦ壆绮婚幎鑺ュ€甸柨婵嗙凹缁ㄨ棄霉閻樿崵鐣烘慨濠冩そ濡啫鈽夊▎鎰€烽梺璇插閻噣宕¢幎鑺ュ仒妞ゆ洍鍋撶€规洖鐖奸、妤佸緞鐎n偅鐝┑鐘愁問閸n垳寰婇崜褉鍋撶粭娑樻搐缁犳煡鏌涢妷顔煎闁藉啰鍠栭弻锝夊棘閹稿孩鍠愰梺鑽ゅ枎缂嶅﹪寮诲☉鈶┾偓锕傚箣濠靛洨浜俊鐐€ら崜娆撴偋閸℃稈鈧棃宕橀鍢壯囧箹缁厜鍋撻懠顒€鍤紓鍌氬€风欢锟犲窗濡ゅ懎绠伴柟闂寸劍閸嬧晠鏌i幋锝嗩棄缁绢厸鍋撻梻浣虹帛閸旀洜绮旈棃娴虫盯宕橀鍏兼К闂侀€炲苯澧柕鍥у楠炴帡骞嬪┑鎰磻闁诲氦顫夐幐椋庣矆娓氣偓閸╃偤骞嬮敂钘変汗闂佸湱绮敮鈺傚閳ь剛绱撴担鐟板姢鐟滄壆鍋熼崚鎺戔枎閹惧疇鎽曞┑鐐村灦閻喖鈻介鍫熺厵閻熸瑥瀚慨鍥ㄣ亜閵夛妇绠炴慨濠冩そ閺屽懘鎮欓懠璺侯伃婵犫拃鍌氬祮闁哄瞼鍠栭幖褰掝敃閿濆懐锛撻梻浣瑰缁诲嫰宕戝☉銏犵厴闁瑰濮崑鎾绘晲鎼存ê浜炬い鎾寸⊕濞呭﹪鏌$仦鐣屝f繛纰变邯楠炲繒浠﹂挊澶婅厫闂傚倷鐒﹂惇褰掑磹閺囥垹绠犻柟閭﹀枟椤洟鏌熼幆褏鎽犲┑顖涙尦閺屾盯骞橀弶鎴犵シ闂佸憡鎸稿畷顒勨€旈崘顔嘉ч柛鈩冾殘娴犳悂姊洪懡銈呮毐闁哄懏鐩幃楣冩倻閽樺)銊ф喐婢舵劕纾婚柟鍓х帛閺呮煡骞栫划鐟板⒉闁诲繐绉瑰铏圭磼濡闉嶅┑鐐插级閿曘垺淇婇悽绋跨妞ゆ牗姘ㄩ悿鈧梻鍌氬€搁悧濠勭矙閹邦喛濮抽柤娴嬫櫇绾捐棄霉閿濆牊顥夐柣鎾村姈閹便劌螣缁嬪灝顬嬪┑鈥冲级閸旀瑩鐛Ο鍏煎珰闁肩⒈鍓﹀Σ浼存⒒娴gǹ鏆遍柟纰卞亰瀹曟劖绻濆В绋挎喘瀵埖鎯旈幘瀛樻澑婵$偑鍊栧濠氬Υ鐎n亶鍟呴柕澶涜礋娴滄粍銇勯幘璺轰粶婵℃彃顭烽弻锝夋晲閸パ冨箣濡ょ姷鍋炵敮锟犵嵁鐎n喖绫嶉柍褜鍓熼幃妤佺節濮橆厸鎷洪柣鐔哥懃鐎氼參宕曞Δ鍛厱婵☆垵銆€閸嬫捇鎮㈤幓鎺戠阀濠电姷鏁告慨鐑藉极閸涘﹥鍙忛柣鎴f閺嬩線鏌涘☉姗堟敾闁告瑥绻戦妵鍕箻閸楃偟浠肩紒鐐劤椤兘寮婚悢鐓庣鐟滃繒鏁☉銏$厓闂佸灝顑呴悘锕傛煏閸パ冾伃妤犵偞甯″畷鍗烆渻閹屾缂傚倸鍊搁崐椋庣矆娓氣偓钘濋梺顒€绉撮弸浣糕攽閻樿櫕鐨戠€规挷绶氶弻娑㈠焺閸愵亖濮囬梺绋匡功閸忔﹢寮诲☉妯锋斀闁糕剝顨忔导鈧俊鐐€栧褰掑礉閺囥垹鐓橀柟杈鹃檮閸婂鏌涢妷銏℃珖閺嶏繝姊绘担鍛婂暈闁圭ǹ顭烽幃鐑芥晜閻e备鏀虫繝鐢靛Т濞诧箓宕甸崘顔界厓闁告繂瀚弳鐔兼煥濞戞瑧鐭掓慨濠囩細閵囨劙骞掗幋婊冩瀳闂備礁鎲¢悷銉︻殽閹间礁鐓濋柟鐐灱閸亪鏌涢銈呮灁闁告ɑ鎮傞弻锝堢疀閺囩偘鎴风紒缁㈠幖閻栫厧鐣烽幋锕€绠婚悹鍥皺閻も偓濠电偠鎻徊浠嬪箟閿熺姴纾规い鏍仦閳锋垹鐥鐐村櫣濞存粌缍婇幃璺衡槈閺嵮冨Е闂佺硶鏂侀崑鎾愁渻閵堝棗绗掗柛鐕佸亰閹啫煤椤忓懐鍘告繛杈剧到濠€杈ㄦ櫠椤忓牊鐓冮悷娆忓閻忔挳鏌熼鐣屾噰鐎殿喖鐖奸獮瀣偐鏉堫煈鏁囬梻鍌氬€风粈浣革耿鏉堛劎浠氶梻浣侯攰婵倗鍒掓惔銊ョ闁圭儤顨呯猾宥夋煕椤愩倕鏋庡ù鐘烘缁辨挻鎷呴崜鎻掑壍濡炪倖娲樻繛濠囧极閸愵喖纾兼繛鎴炶壘楠炲牓姊绘担鍛婃儓婵炲眰鍨藉畷婵嗙暆閸曨剙鈧爼鏌eΟ鑲╁笡闁绘挻娲熼弻鐔兼嚋椤掆偓婵$厧霉濠婂嫬鍔ら柍瑙勫灴閺佸秹宕熼鈩冩線闂備胶枪閿曘儵鎮ч悩鑼殾婵犻潧顑嗛弲婵嬫煃瑜滈崜鐔煎灳閿曞倸閿ゆ俊銈傚亾闁绘帒鐏氶妵鍕箳瀹ュ牆鍘$紓浣哄Т婢т粙鍩€椤掆偓閸樻粓宕戦幘鏂ユ斀闁绘ǹ浜粣鏃堟煕鐎n偒娈旈柍瑙勫灴椤㈡瑧娑甸悜鐣屽弽婵犵數鍋涢幏鎴犲緤閸啣锝夊箛閺夎法顔婇梺鐟板暱绾绢參宕伴幘璇茬闁绘ḿ绮崵鎴︽煠缁嬭法浠涙慨锝嗗姍濮婂宕掑顑藉亾閻戣姤鍤勯柤鍝ユ暩娴犳碍绻濋悽闈涗粶妞ゆ洦鍙冨畷妤€螣娓氼垰娈ㄥ銈嗗姂閸婃牜鈧碍姘ㄩ埀顒傛嚀婢瑰﹪宕伴弽褉鏋旈柕濠忓缁♀偓闂佹眹鍨藉ḿ褎鐗庣紓浣哄亾濠㈡ḿ绮旈悷閭﹀殨闁哄被鍎辩粻鐢告煙閻戞ḿ绠橀柛鐐垫暬閺岋綁鎮╅悜姗嗕哗闁诲繐绻堥崝宀勵敊韫囨稑唯鐟滃宕戦幘鑸靛枂闁告洦鍓欑喊宥呪攽閳藉棗浜濈紒璇插€块敐鐐剁疀濞戞瑦鍎梺闈╁瘜閸橀箖鏁嶅⿰鍐f斀闁宠棄妫楅悘鐘绘煙绾板崬浜伴柨婵堝仜椤撳ジ宕堕埡鍐跨闯濠电偠鎻紞渚€藟閹捐绀夌€广儱顦伴悡娆戠磼鐎n亞浠㈤柡鍡涗憾閺岋綁鏁愰崶褍骞嬪Δ鐘靛仜椤戝寮崘顔肩劦妞ゆ帒鍊绘稉宥呪攽閻樺磭顣查柛瀣剁秮閺屾盯濡烽幋婵嗘殶濡ょ姴娲幃妤冩喆閸曨剙纰嶇紓浣割槹閹告娊鍨鹃弮鍫濈妞ゆ柨妲堣閺屾盯鍩勯崗鐙€浜Λ鍕吋閸モ晝锛濇繛杈剧到婢瑰﹪宕曢幇鐗堢厱闁靛ǹ鍎遍。宕囩磼椤旂⒈鍎忔い鎾冲悑瀵板嫮鈧綆浜栭崑鎾绘煥鐎c劋绨婚梺鐟版惈缁夊爼藝閿旈敮鍋撳▓鍨灈闁诲繑绻堥崺鐐哄箣閿曗偓閻擄繝鏌涢埄鍐炬畼濞寸媭鍨跺娲川婵犲海鍔堕梺鍛婃处閸欏骸煤閸涘﹣绻嗛柕鍫濈箳閸掍即鏌涢悤浣哥仸鐎规洘鍔欏畷褰掝敃閿濆懎浼庢繝纰樻閸ㄦ娊宕㈣缁傚秵銈i崘鈺佲偓鍨叏濡厧浜鹃悗姘炬嫹

核心提示:http://poj.org/problem?id=1077Source CodeProblem: 1077 User: p_hoenix Memory: 220K Time: 0MS Language: C++ Result: Accepted Source Code #include <iostream
http://poj.org/problem?id=1077 Source Code Problem: 1077 User: p_hoenix Memory: 220K Time: 0MS Language: C++ Result: Accepted Source Code #include <iostream> #include <utility> #include <vector> #include <fstream> #include <math.h> using namespace std; const int MAX = 1 << 20; const int ROW = 3, COL = 3; //棋盘 struct Board { Board& operator=(const Board &b) { for(int i = 0; i < ROW; i++) for(int j = 0; j < COL; j++) tile[i][j] = b.tile[i][j]; r = b.r; c = b.c; return *this; } int tile[ROW][COL];//4*4的方块 int r,c;//空格的位置 }; typedef Board Status; struct Step { int r,c; int dir; }; class PicturePizzle { public: friend void input(PicturePizzle &pp); PicturePizzle() { pStepDir = (int*)malloc(sizeof(int) * MAX); stepHeap = (Board*)malloc(sizeof(Board) * MAX); } ~PicturePizzle() { free(pStepDir); free(stepHeap); } //移动步骤. typedef struct{ int r,c;//空格位置 int dir;//移动方向 }Step; //判断以该状态开始是否可以完成拼图 bool JudgeValidStatus(); //heuristic function,启发式函数,计算(估算)最大移动步数 int Heuristic(); //IDA*搜索寻找移动方案 //当前状态,深度,h(),前一步的移动方向. bool IDAstar(Status &s, int depth, int h, int prevDir); //打印移动路径 void ShowStep(int depth); void Run(); //private: Board board; int h; int maxDepth; vector<Board> step; int *pStepDir; Board *stepHeap; //郁闷的地方,C++ primer里面说可以给const static在里面初始化,在类外面定义的,但是VC6.0不可以 //目标棋盘 const static Board destBoard;// = {1 ,2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 4, 4}; const static int nDestPos[ROW * COL + 1][2];//最终棋盘的各个方块的位置 const static int dir[4][2]; }; //1到16的方块编号 const Board PicturePizzle::destBoard = {1 ,2, 3, 4, 5, 6, 7, 8, 9, 2, 2};//10, 11, 12, 13, 14, 15, 16, 3, 3}; const int PicturePizzle::nDestPos[ROW * COL + 1][2] = {{-1, -1}, {0, 0}, {0, 1}, {0, 2}, {1, 0}, {1, 1},{1, 2}, {2, 0}, {2, 1}, {2, 2}}; //{3, 0}, {3, 1}, {3, 2}, {3, 3}}; const int PicturePizzle::dir[4][2] = {{0, -1}, {-1, 0}, {0, 1}, {1, 0}};//左上右下 bool PicturePizzle::JudgeValidStatus() { int i, j, array[ROW * COL], k, sum; sum = k = 0; //转化成一维数组 for(i = 0; i < ROW; i++) for(j = 0; j < COL; j++) { array[k++] = board.tile[i][j]; } //因为在最终状态下,棋盘的一维数组是有序递增的. //除了X结点外,要到达目标位置需要移动的最大步数,因为在转换成了一维后原本可以上下移动的都被转化成了水平移动. //但是幸运的是,他们是同奇同偶的.具体的证明我也不知道,画图有这么个规律 for(i = 0; i <= ROW * COL - 2; i++) for(j = i + 1; j <= ROW * COL - 1; j++) if(array[i] > array[j]) sum++; //这个是X方块到目标位置的最短步数,不管怎么移动,只要最后是在目标位置,必定是同奇同偶的.(简单的考虑就是撤销) //而每一次的其他方块的移动都是与X方块的交换来实现的,所以他们的和必定是偶数 sum += abs(board.r - nDestPos[ROW * COL][0]) + abs(board.c - nDestPos[ROW * COL][1]); return sum % 2 == 0; } int PicturePizzle::Heuristic() { int r, c, tile, sum = 0; for(r = 0; r < ROW; r++) for(c = 0; c < COL; c++) { tile = board.tile[r][c]; //计算每个方块(非空格)移动到目标位置的曼哈顿距离,不需要计算空格 if(tile != ROW * COL) { sum += abs(r - nDestPos[tile][0]) + abs(c - nDestPos[tile][1]); } } h = sum; return sum; } int global = 0; bool PicturePizzle::IDAstar(Status &s, int depth, int h, int prevDir) { //cout<<global++<<endl; if(memcmp(&s, &destBoard, sizeof(destBoard)) == 0)//到达目标状态 { this->ShowStep(depth); return true; } if(depth >= maxDepth)//超过当前深度 return false; Status ns; int nr,nc,nh,moveTile; for(int d = 0; d < 4; d++) { if(abs(d - prevDir) == 2)//会撤销上次的移动 continue; ns = s; nr = s.r + dir[d][0]; nc = s.c + dir[d][1]; if(nr < 0 || nr > ROW - 1 || nc < 0 || nc > COL - 1)//越界 continue; //移动方块 moveTile = s.tile[nr][nc]; ns.tile[s.r][s.c] = moveTile; ns.tile[nr][nc] = ROW * COL; ns.r = nr; ns.c = nc; //向左移动.并且与X交换的方块离它的目标位置近了一步. //反过来,因为X是向左的,那么moveTile就是向右的,那么这个时候只有moveTile在它的目标位置的左边的时候才成立 //也就是说它原来的位置nc是在目标的左边 if(d == 0 && nc < nDestPos[moveTile][1]) nh = h - 1;//nh比当前的h少1 else if(d == 1 && nr < nDestPos[moveTile][0])//上 nh = h - 1; else if(d == 2 && nc > nDestPos[moveTile][1])//右 nh = h - 1; else if(d == 3 && nr > nDestPos[moveTile][0]) nh = h - 1; else nh = h + 1; //大于f if(depth + nh > maxDepth) continue; //step.insert(step.begin() + depth, ns); //step.erase(step.begin() + depth + 1); pStepDir[depth] = d; stepHeap[depth] = ns; if(IDAstar(ns, depth + 1, nh, d)) return true; } return false; } void PicturePizzle::ShowStep(int depth) { int i = 0; //cout<<depth<<endl; for(i = 0; i < depth; i++) switch(pStepDir[i]) { case 0: cout<<'l'; break; case 1: cout<<'u'; break; case 2: cout<<'r'; break; case 3: cout<<'d'; break; } cout<<endl; /* for(i = 0; i < depth; i++) { for(int r = 0; r < ROW; r++) { for(int c = 0; c < COL; c++) cout<<stepHeap[i].tile[r][c]<<"\t"; cout<<endl; } cout<<endl<<endl; } */ /* cout<<step.size()<<endl<<endl; for(vector<Board>::iterator iter = step.begin(); iter != step.end(); iter++) { cout<<i++<<endl; for(int r = 0; r < 4; r++) { for(int c = 0; c < 4; c++) cout<<iter->tile[r][c]<<"\t"; cout<<endl; } cout<<endl<<endl; }*/ } void PicturePizzle::Run() { if(JudgeValidStatus()) { maxDepth = Heuristic(); while(maxDepth++) if(IDAstar(board, 0, h, 20)) break; } else { cout<<"unsolvable"<<endl; } } void input(PicturePizzle &pp) { //cout<<"输入一个文件(.txt),表示拼图的初始" //fstream file("in.txt"); int num; for(int r = 0; r < ROW; r++) for(int c = 0; c < COL; c++) { //file>>num; cin>>num; if(/*file.fail()*/cin.fail()) { //file.clear(); //file.ignore(1,'\t'); cin.clear(); cin.ignore(1, ' '); pp.board.tile[r][c] = ROW * COL; pp.board.r = r; pp.board.c = c; } else pp.board.tile[r][c] = num; } //file.close(); } int main() { //freopen("out.txt", "w", stdout); PicturePizzle pp; input(pp); pp.Run(); return 0; }
更多精彩
赞助商链接