IDA*算法，，即迭代加深的A*算法，实际上就是迭代加深+DFS+估价函数
题目传送：The Rotation Game
AC代码：
;int mp[25];int n;int pos[] = {7, 8, 9, 12, 13, 16, 17, 18};int depth;int ans_num;char ans[205];bool is_ok(int *g) {//判断是否已达到结果int t = g[7];if(t == g[8] && t == g[9] && t == g[12] && t == g[13] && t == g[16] && t == g[17] && t == g[18]) {return true;}return false;}void change_state(int *g, int a1, int a2, int a3, int a4, int a5, int a6, int a7) {//状态转换（这里就是数字移位）int tmp = g[a1];g[a1] = g[a2]; g[a2] = g[a3]; g[a3] = g[a4];g[a4] = g[a5]; g[a5] = g[a6]; g[a6] = g[a7];g[a7] = tmp;}int get_maxnum(int *g) {//获取中间8个数之间出现次数最大的那个数的次数int cnt[4];cnt[1] = cnt[2] = cnt[3] = 0;for(int i = 0; i < 8; i ++) {cnt[g[pos[i]]] ++;}return max(cnt[1], max(cnt[2], cnt[3]));}//IDA*算法的核心即为DFS+迭代加深+估价函数int dfs(int *g, int cur_depth, int pre_dir) {;//而每次搜索对应一次数字移位，而当搜索次数小于8个数中要改变得几个数时，肯定不对。剪枝①};}int tmp[25];((i == 2 && pre_dir == 5) || (i == 5 && pre_dir == 2)) continue;if((i == 3 && pre_dir == 8) || (i == 8 && pre_dir == 3)) continue;if((i == 4 && pre_dir == 7) || (i == 7 && pre_dir == 4)) continue;for(int j = 1; j <= 24; j ++) tmp[j] = g[j];switch(i) {case 1: ans[cur_depth] = ‘A’; change_state(tmp, 1, 3, 7, 12, 16, 21, 23); break;case 2: ans[cur_depth] = ‘B’; change_state(tmp, 2, 4, 9, 13, 18, 22, 24); break;case 3: ans[cur_depth] = ‘C’; change_state(tmp, 11, 10, 9, 8, 7, 6, 5); break;case 4: ans[cur_depth] = ‘D’; change_state(tmp, 20, 19, 18, 17, 16, 15, 14); break;case 5: ans[cur_depth] = ‘E’; change_state(tmp, 24, 22, 18, 13, 9, 4, 2); break;case 6: ans[cur_depth] = ‘F’; change_state(tmp, 23, 21, 16, 12, 7, 3, 1); break;case 7: ans[cur_depth] = ‘G’; change_state(tmp, 14, 15, 16, 17, 18, 19, 20); break;case 8: ans[cur_depth] = ‘H’; change_state(tmp, 5, 6, 7, 8, 9, 10, 11); break;}if(is_ok(tmp)) {ans_num = tmp[7];ans[cur_depth + 1] = ‘\0’;return 1;}if(dfs(tmp, cur_depth + 1, i)) return 1;}return 0;}int main() {int x;while(1) {scanf(“%d”, &mp[1]);if(mp[1] == 0) {break;}for(int i = 2; i <= 24; i ++) {scanf(“%d”, &mp[i]);}if(is_ok(mp)) {printf(“No moves needed\n”);printf(“%d\n”, mp[7]);continue;}depth = 1;while(1) {if(dfs(mp, 0, -1)) {break;}depth ++;}printf(“%s\n”, ans);printf(“%d\n”, ans_num);}return 0;}
有时我们选择改变，并非经过深思熟虑，
