第一次IDA*。很有意思的思路。IDA*重点和A*不一样,A*总是看当前最优的估值函数f()=g()+h(),但IDA*不一样,只要深度在允许范围内,IDA*就不断地深搜,不管f()的大小。
另外一个值得mark:当要对不规则的数组进行连续的有规律的操作时候,可以建立个映射数组。
附代码,不过这个代码写的有点丑陋,另外值得参考的代码http://www.cnblogs.com/zhsl/archive/2013/04/30/3052530.html
#include<iostream> #include<string> using namespace std; struct Solution{ string path; int mark; }; struct StateNode{ string path; int blockHash[24]; int gvalue; int fvalue; int hvalue; }; bool nodeFlag[6563]; // mark if the status is visited before int bound = 0; int hashMap[8][7] = { {22,20,15,11,6,2,0},//a {23,21,17,12,8,3,1},//b {4,5,6,7,8,9,10},//c {13,14,15,16,17,18,19},//d {1,3,8,12,17,21,23},//e {0,2,6,11,15,20,22},//f {19,18,17,16,15,14,13},//g {10,9,8,7,6,5,4}//h }; int goalBlock[8] = { 6, 7, 8, 11, 12, 15, 16, 17 }; int Max(int a, int b) { if (a > b) return a; return b; } int MinHDistance(int blockHash[24]) { int dis[] = { 0, 0, 0 };//1,2,3 for (int i = 0; i < 8; i++){ dis[ blockHash[goalBlock[i]] - 1]++; } int maxvalue = Max(Max(dis[0], dis[1]), dis[2]); return 8 - maxvalue; } StateNode InitializeStateNode(int initArr[24]) { StateNode initNode; for (int i = 0; i < 24; i++) initNode.blockHash[i] = initArr[i]; initNode.path = ""; initNode.gvalue = 0; initNode.hvalue = MinHDistance(initArr); initNode.fvalue = initNode.hvalue; return initNode; } StateNode Operation(char opt, StateNode stateNode) { StateNode sucNode = stateNode; int optIndex = opt - 'A'; int preValue = sucNode.blockHash[hashMap[optIndex][0]]; sucNode.blockHash[hashMap[optIndex][0]] = sucNode.blockHash[hashMap[optIndex][6]]; for (int i = 1; i < 7; i++){ int tmp = sucNode.blockHash[hashMap[optIndex][i]]; sucNode.blockHash[hashMap[optIndex][i]] = preValue; preValue = tmp; } sucNode.gvalue++; sucNode.hvalue = MinHDistance(sucNode.blockHash); sucNode.fvalue = sucNode.gvalue + sucNode.hvalue; sucNode.path = sucNode.path + opt; return sucNode; } bool IsFinalGoal(StateNode stateNode) { if (stateNode.hvalue == 0) return true; return false; } float IDASearch(StateNode stateNode, bool& fflag, Solution& sol, int bound) { if (IsFinalGoal(stateNode)) { fflag = true; sol.path = stateNode.path; sol.mark = stateNode.blockHash[6]; return stateNode.fvalue; } if (stateNode.fvalue > bound) { return stateNode.fvalue; } int roundMin = 1 << 30; //The succesor //A B C D E F G H for (char o = 'A'; o <= 'H'; o++) { StateNode sucNode = Operation(o, stateNode); float value = IDASearch(sucNode, fflag, sol, bound); if (fflag == true){ return value; } else { if (roundMin > value){ roundMin = value; } } } return roundMin; } Solution IDAStar(StateNode initNode) { bool fflag = false; float bound = initNode.hvalue; Solution sol; while (fflag == false) { bound = IDASearch(initNode,fflag,sol, bound); } return sol; } int main() { int blocks[24]; scanf("%d", &blocks[0]); while (blocks[0] != 0) { for (int i = 1; i < 24; i++) scanf("%d", &blocks[i]); StateNode initNode = InitializeStateNode(blocks); if (initNode.hvalue == 0) { printf("%s\n", "No moves needed"); printf("%d\n", blocks[7]); } else { Solution sol = IDAStar(initNode); printf("%s\n", sol.path.c_str()); printf("%d\n", sol.mark); } scanf("%d", &blocks[0]); } return 0; }