八数码的IDA*算法实现

// IDA*（迭代式深度搜索） // 把SIZE改成4就可以变成15数码问题 /* IDA*算法在是A*与ID算法的结合物，用了A*算法的预估方法和预估值(f=g+h)，用了ID算法的迭代深入(最初从Manhatton距离开始) 较之A*算法，IDA*算法不需要Open表和Closed表，大大节省了内存空间，而且IDA*算法可以不采用递归式程序设计方法，这样也可以节约堆栈空间。 A*,例如目标是D,起始为A,首先初始化将每个节点到D的直线距离赋给节点做代价函数,然后在访问了A之后,马上预测A的子节点B/C,求得B的实际代价为A到B的花费加上B的原始代价.同理取得C的实际代价,之后在A的所有子节点中选择代价最小的节点进行扩展。上面的过程重复进行直到找到目标。 迭代加深（ID），ID算法将深度设置为dep，对于一个树做深度优先的遍历（节制条件：所有节点的深度不大于dep），如果没有找到目标，那么将dep++，重复上面的过程直到找到目标。 IDA* 算法（迭代深度优先算法），将上面的A*和ID算法结合起来，也就是，在进行搜索时，使用耗散值替代ID中的深度值（f=g+h）,也就是说，搜索的范围在那些不超过给定值的节点中进行深度优先搜索。如果搜索不成功，那么返回头节点，并且使限定的耗散值变大（具体为所有超过上次限定值节点中的最小耗散）， 也就是说，在迭代过程中我们需要纪录一下那些我们已经探知的，超过限定的节点的耗散函数值，然后挑选其中的最小值，再次进行搜索。 每次循环都进行深度优先搜索，当f超过一给定的阈值(threshold)时，去掉相应的分支并进行回溯，该阈值的初始值为对初始节点路径费用的估计fs， 且该阈值随着算法的每一次循环而不断增加．在每一次循环中计算用于下一次循环的阈值，其计算方法为取本次循环中路径费用超过当前阈值的那些费用中的最小值作为 下一次循环的阈值．摘自《IDA*算法的程序实现和实验分析.pdf》 */ #include<stdio.h> #include<string.h> #include<math.h> #include<time.h> #define SIZE 3 typedef char board[SIZE][SIZE]; board target = {1,2,3,8,0,4,7,6,5}; // 目标状态，改成15数码的话要同时改掉 board start; long add[4][2]={-1,0,0,1,1,0,0,-1}; /*************************估价函数*****************************/ long targetplace[SIZE*SIZE][2]; // 这个估价函数是用来剪枝的 long CAL_H(board & node) { long i,j; long re = 0; for (i=0; i<SIZE; i++) for (j=0; j<SIZE; j++) if (node[i][j]) { re += abs(i - targetplace[node[i][j]][0]) + abs(j - targetplace[node[i][j]][1]); } return re; } /***************************************************************/ bool can_solve() { // 搜索前判断是否可解 long i,j,k1,k2; for (i=0; i<SIZE; i++) for (j=0; j<SIZE; j++) { if (start[i][j]==0) { start[i][j] = SIZE*SIZE; k1 = (SIZE-1-i) + (SIZE-1-j); } if(target[i][j]==0){ target[i][j] = SIZE*SIZE; k2 = (SIZE-1-i) + (SIZE-1-j); } } for (i=0; i<SIZE*SIZE; i++) for (j=i+1; j<SIZE*SIZE; j++) { if (start[i/SIZE][i%SIZE] > start[j/SIZE][j%SIZE]) k1++; if (target[i/SIZE][i%SIZE] > target[j/SIZE][j%SIZE]) k2++; } for (i=0; i<SIZE; i++) for (j=0; j<SIZE; j++) { if (start[i][j]==SIZE*SIZE) start[i][j]=0; if (target[i][j]==SIZE*SIZE) target[i][j]=0; } return (k1%2)==(k2%2); } void out_board(board state,long step) { long i,j; printf("STEP %ld:\n", step); for(i=0;i<SIZE;i++){ for(j=0;j<SIZE;j++){ printf("%ld ", state[i][j]); } printf("\n"); } printf("\n"); } void output(long dep, char path[]) { // 输出答案 long i,j,x1,y1,x0,y0; board state; memcpy(state, start, sizeof(state)); out_board(state,0); for(i=0;i<SIZE;i++)for(j=0;j<SIZE;j++)if(state[i][j]==0)x0=i,y0=j; for (i=0; i<dep; i++) { x1=x0+add[path[i]][0]; y1=y0+add[path[i]][1]; state[x0][y0] = state[x1][y1]; state[x1][y1] = 0; x0 = x1, y0 = y1; out_board(state,i+1); } printf("The minimum number of steps is %ld.\n", dep); } /***********************************************************************************/ long ans; char path[100000]; long max_depth, max_nodes, tot_nodes, cur_nodes; bool ida(board & node, long x0, long y0, long dep, long d, long h) {//i表示从哪个方向上过来的，最初的初值为-1。 if(dep>max_depth) max_depth = dep; cur_nodes ++; long i,j,k,x1,y1,h1; if (memcmp(node, target, sizeof(target))==0) { output(dep, path); return 1; } if (dep==ans) return 0; board node1; for (i=0; i<4; i++) { if (((i%2)==(d%2)) && i!=d) continue; x1 = x0 + add[i][0]; y1 = y0 + add[i][1]; if (x1<0||y1<0||x1==SIZE||y1==SIZE) continue; memcpy(node1, node, sizeof(node1)); node1[x1][y1] = 0; node1[x0][y0] = node[x1][y1]; if (i==3 && y1<targetplace[node[x1][y1]][1]) h1=h-1;// 跟目标位置比比，看是不是有效移动(就是这样移动OK不OK) else if (i==1 && y1>targetplace[node[x1][y1]][1]) h1=h-1; else if (i==0 && x1<targetplace[node[x1][y1]][0]) h1=h-1; else if (i==2 && x1>targetplace[node[x1][y1]][0]) h1=h-1; else h1=h+1; //这个方向上的移动不OK，那么估价函数h(x)就又远了一步 if (h1+dep+1>ans) continue; // 根据估价值(h1+dep)，具体来说是(dep+1)+h1 // 和假定的解的步数(ans)来剪枝 path[dep] = i; if (ida(node1,x1,y1,dep+1,i,h1)) return 1; } return 0; } int main() { long i,j,k,x0,y0; long cs; clock_t begin, finish; double duration; // scanf("%ld", &cs); cs = 1; while (cs--) { printf("\ninput:\n"); for (i=0;i<SIZE;i++)for(j=0;j<SIZE;j++) { scanf("%ld",&k); start[i][j] = k; if (k==0) { x0=i; y0=j; } } if (!can_solve()) { printf("This puzzle is not solvable.\n"); continue; } begin = clock(); for (k=1,i=0; i<SIZE; i++) for (j=0; j<SIZE; j++) { targetplace[target[i][j]][0] = i; targetplace[target[i][j]][1] = j; } max_depth = 0; // 空间 max_nodes = 0; // 单次扩展的最大节点数 tot_nodes = 0; // 总共扩展的节点数(包括迭代时重复的节点) i = -1; //剪枝 j = CAL_H(start); for (ans=j; ; ans+=1) { //运行 cur_nodes = 0; if (ida(start,x0,y0,0,i,j)) { break; } if(cur_nodes>max_nodes) max_nodes = cur_nodes; tot_nodes += cur_nodes; } finish = clock(); duration = (double)(finish - begin) / CLOCKS_PER_SEC; printf("running time: %2.5f seconds\n",duration); printf("%d\n",max_depth); // printf("%d\n",tot_nodes); } return 0; } /* 3 6 5 7 0 2 1 4 8 */