首页 > 代码库 > [BZOJ 1085] [SCOI2005] 骑士精神 [ IDA* 搜索 ]
[BZOJ 1085] [SCOI2005] 骑士精神 [ IDA* 搜索 ]
题目链接 : BZOJ 1085
题目分析 :
本题中可能的状态会有 (2^24) * 25 种状态，需要使用优秀的搜索方式和一些优化技巧。
我使用的是 IDA* 搜索，从小到大枚举步数，每次 DFS 验证在当前枚举的步数之内能否到达目标状态。
如果不能到达，就枚举下一个步数，重新搜索，即使某些状态在之前的 DFS 中已经搜索过，我们仍然搜索。
并且在一次 DFS 中，我们不需要判定重复的状态。
在 IDA* 中，重要的剪枝优化是 估价函数 ，将一些不可能存在可行解的枝条剪掉。
如果估价函数写得高效，就能有极好的效果。我们写估价函数的原则是，绝对不能剪掉可能存在可行解的枝条。
因此，在预估需要步数时，应让估计值尽量接近实际步数，但一定不能大于实际需要的步数。
本题的一个很有效的估价函数是，比较当前状态的黑白骑士与目标状态的黑白骑士有多少不同，我们把这个值作为估价函数值，因为每一步最多将当前状态的一个骑士改变为与目标状态相同。但是应该注意的是，空格所在的格子不要算入其中。
代码如下：
#include <iostream>#include <cstdio>#include <cstdlib>#include <cstring>#include <cmath>#include <algorithm> using namespace std; const int MaxStep = 15;const int Dx[8] = {1, 1, -1, -1, 2, 2, -2, -2}, Dy[8] = {2, -2, 2, -2, 1, -1, 1, -1}; int Te, Ans; char Str[6]; struct ES{ int num, pos; bool operator == (const ES &e) const { return (num == e.num) && (pos == e.pos); }} S, T; inline bool Inside(int x, int y) { if (x < 0 || x > 4) return false; if (y < 0 || y > 4) return false; return true;} void Print(ES x) { for (int i = 0; i < 5; ++i) { for (int j = 0; j < 5; ++j) { if (x.pos == (i * 5 + j)) printf("*"); else { if (x.num & (1 << (i * 5 + j))) printf("1"); else printf("0"); } } printf("\n"); }} inline int Expect(ES x) { int Temp, Cnt; Temp = x.num ^ T.num; Cnt = 0; if (x.pos != T.pos) { if (Temp & (1 << T.pos)) --Cnt; if (Temp & (1 << x.pos)) --Cnt; } while (Temp) { ++Cnt; Temp -= Temp & -Temp; } return Cnt;} bool DFS(ES Now, int Step, int Limit) { if (Now == T) return true; if (Step == Limit) return false; if (Expect(Now) > Limit - Step) return false; int x, y, xx, yy; ES Next; x = Now.pos / 5; y = Now.pos % 5; for (int i = 0; i < 8; i++) { xx = x + Dx[i]; yy = y + Dy[i]; if (!Inside(xx, yy)) continue; Next = Now; Next.pos = xx * 5 + yy; Next.num &= (1 << 25) - 1 - (1 << (xx * 5 + yy)); if (Now.num & (1 << (xx * 5 + yy))) Next.num |= (1 << (x * 5 + y)); if (DFS(Next, Step + 1, Limit)) return true; } return false;} int IDAStar(ES S) { if (S == T) return 0; for (int i = 1; i <= MaxStep; ++i) if (DFS(S, 0, i)) return i; return -1;} int main() { scanf("%d", &Te); T.num = 549855; T.pos = 12; for (int Case = 1; Case <= Te; ++Case) { S.num = 0; for (int i = 0; i < 5; ++i) { scanf("%s", Str); for (int j = 0; j < 5; ++j) { if (Str[j] == ‘1‘) S.num |= (1 << (i * 5 + j)); if (Str[j] == ‘*‘) S.pos = i * 5 + j; } } Ans = IDAStar(S); printf("%d\n", Ans); } return 0;}
[BZOJ 1085] [SCOI2005] 骑士精神 [ IDA* 搜索 ]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。