启发式搜索算法学习之A* & ID_A*(续）
LBoy
posted @ 2011年2月28日 23:34
in Algorithm Study
, 6524 阅读
上一节简单的描述了A*和IDA*的基本理论，这节针对具体的题目进行分析，重点讲一下启发函数的构造。
八数码问题
启发函数的设计，一般有两种设计思路，可以证明，这两种思路都可以找到最优解。
一种是Diff ( Status a, Status b )，其返回值是a 和b状态相应位置上数字（空格除外）不同的次数。另一种比较经典的是曼哈顿距离Manhattan ( Status a, Status b )，其返回的是各个数字（除却空格）从状态a的位置到状态b的相应位置的最短曼哈顿距离的和。要论证启发函数设计是否可行，要考虑两个条件，一是，h(s) <= h(t) + w(s, t)；二是，f(s) <= f(t)，即f(x)是单调的函数。
对于第一种启发函数的设计思路：每次X标记的位置和周围的四个位置交换，会有两种可能，要么，x标记的返回b状态指示的位置，w(s, t) = 1;要么,w(s, t) = 0;，也就是说h的值每次最多减小1个单位，而去实际代价为搜索树的深度，那么g值每次增加1，那么估价函数f（）= g() + h() 要么增加1，要么不变。所以可以找到最优解。
对于第二种启发函数的设计思路：每次X标记的位置和周围的四个位置交换，会有两种可能，要么，x标记的接近最终的位置一步，w(s, t) = 1;要么,不变或者远离一步，w(s, t) <= -1,也就是说h的值每次最多减小1个单位，而去实际代价为搜索树的深度，那么g值每次增加1，那么估价函数f（）= g() + h()每次可能不变，或者增加1或2，所以可以找到最优解。
搜索问题的优化，一般从下面三种情况考虑，
- Hahs() 判重，这里主要是避免重复搜索，也是搜索里面最为重要的一种剪枝方法。
- 可行性剪枝，判断当前状态能否到达最终的状态。（个人把启发搜索咱归为此类）
- 最优性剪枝，这里主要在深度优先搜索中用到，因为dfs第一次到达目标状态不一定是最优的。（迭代加深的除外）
- 上下界剪枝，这种剪枝方法主要在博弈搜索里面用到。
上面的剪枝优化我们要用到Hash()判重，判重就要记录下所有的位置，并判定当前状态是否已经到达过。这个题目的判重有点麻烦。总共有N!种状态，一般我们要采用hash判重或者set判重，题目中给定的N=9， N! = 40320. 那么我们可以用简单的H[]判重。判重的方法：把当前的board的每个位置上的数排列起来，看成一个序列，判定这些数在N!中是排第几大的一个数。例如789123456对应排列中的第几大？ num(789123456) = 6 * 8！+ 6 * 7! + 6 * 6! + 0*5! + 0*4!+0*3!+0*2!+0*1!+0*0!;这也就是康托展开式。
int Hash(char *board, int n = 9) {
int ret = 0, tmp;
for (int i = 0; i < n-1; i++) {
tmp = 0;
for (int j = i + 1; j < n; j++) {
tmp += board[j] < board[i];
}
ret += frc[ n- i - 1 ] * tmp;
}
return ret;
}
void rHash(char *board, int val, int n = 9) {
int i, x, j, k, b[9];
memset(b, 0, sizeof(b));
for (i = 1; i <= n; i++) {
x = val / frc[n - i];
val %= frc[n - i];
for (j = 1, k = 0; k <= x; j++) {
if (b[j] == 0) k++;
}
b[--j] = 1;
board[i-1] = j;
}
}
有了上面的知识，这个题目就可以0msAC了，数据比较弱。link: http://poj.org/problem?id=1077
#include <iostream>
#include <queue>
using namespace std;
const int maxn = 362880;
int frc[9], goal[9][2];
int f[maxn], d[maxn];
int h(char board[]) {
int ret = 0, k;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
k = i * 3 + j;
if (board[k] != 8) {
ret += abs(i - goal[ board[k] ][0]);
ret += abs(j - goal[ board[k] ][1]);
}
}
}
return ret;
}
int Hash(char *board, int n = 9) {
int ret = 0, tmp;
for (int i = 0; i < n-1; i++) {
tmp = 0;
for (int j = i + 1; j < n; j++) {
tmp += board[j] < board[i];
}
ret += frc[ n- i - 1 ] * tmp;
}
return ret;
}
struct node {
char board[10];
int space, val;
bool operator < (const node &p) const {
return f[val] > f[p.val];
}
};
node init;
bool color[maxn];
priority_queue<node> open;
int par[maxn];
int stp[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
int path[maxn];
int ans[maxn], n;
void printPath() {
n = 0;
int u = n = 0;
do {
ans[n++] = path[u];
u = par[u];
} while(par[u] != -1);
while(n--) {
switch(ans[n]) {
case 0: putchar('u'); break;
case 1: putchar('d'); break;
case 2: putchar('l'); break;
case 3: putchar('r'); break;
default: puts("Error");
}
}
}
inline bool islegal(int x, int y) {
return !(x < 0 || x > 2 || y < 0 || y > 2);
}
void astar() {
while(!open.empty()) open.pop();
memset(color, 0, sizeof(color));
memset(path, 0, sizeof(path));
int u, v;
int x1, y1, x2, y2;
node cur, tmp;
u = Hash(init.board);
f[u] = h(init.board);
d[u] = 0; par[u] = -1;
init.val = u;
color[u] = 1;
open.push(init);
while(!open.empty()) {
cur = open.top(); open.pop();
if (cur.val == 0) {
printPath();
return;
}
u = cur.val;
x1 = cur.space / 3;
y1 = cur.space % 3;
for (int k = 0; k < 4; k++) {
x2 = x1 + stp[k][0];
y2 = y1 + stp[k][1];
if (islegal(x2, y2) == true) {
tmp = cur;
tmp.space = x2 * 3 + y2;
swap(tmp.board[tmp.space], tmp.board[cur.space]);
v = Hash(tmp.board); tmp.val = v;
if (color[v] == 1 && d[u] + 1 < d[v]) {
path[v] = k;
f[v] -= d[v] - d[u] - 1;
d[v] = d[u] + 1;
par[v] = u;
open.push(tmp);
}
if (color[v] == 0) {
path[v] = k;
d[v] = d[u] + 1;
f[v] = d[v] + h(tmp.board);
par[v] = u;
open.push(tmp);
color[v] = 1;
}
}
}
}
puts("unsolvable");
}
int main() {
//freopen("in.in", "r", stdin);
for (int k = frc[0] = 1; k < 9; k++) {
frc[k] = frc[k-1] * k;
}
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
goal[i*3 + j][0] = i;
goal[i*3 + j][1] = j;
}
}
char digit[2];
for (int k = 0; k < 9; k++) {
scanf("%s", digit);
if (digit[0] == 'x') {
digit[0] = '9';
init.space = k;
}
init.board[k] = digit[0] - '1';
}
astar();
return 0;
}
The Rotation Game
问题概述：片面上放置24个小木块，每个木块上都有1~3中的一个数字（如上图）ABCDEFG代码一趟7个数字是可以样字母标记的箭头方向移动的，移动的方式是循环的，也就是，A趟的第一个字母可以移动到A趟的最后一个字母位置，A趟其它的字母依次向前移动一个字符。问题：用最少的次数移动八趟，使得中间的八个方格的数字相同，并且要求字典序最小（字典序最小可以用ABCDEFG的方式移动）
问题分析：题目没有告诉最多移动的次数，因此普通的dfs存在危险，可能陷入无限深的搜索。题目说明了必有解，因此，可以用刚学的IDA*来解决这个问题。其余的不多说，说一下启发函数的正确性：
启发函数的值：设置为8-已在中间八个位置的最多的数的个数。对于A*算法的第一个必须条件是显然成立的。我们在移动某某一趟的时候，要么是的中间八个数字中相同的个数多一个，要么少一个，也就是说至多减少一个，而深度增加了一个，因此总的f的值最大只能和移动前的父节点相同。因此，满足两个条件，这个启发函数是可行的，即原问题可以功过这种估价函数找到最优解。
#include <iostream>
using namespace std;
int board[24];
int map[8][7] = { // ABCDEFG 对应一趟的block的下标
{0, 2, 6, 11, 15, 20, 22},
{1, 3, 8, 12, 17, 21, 23},
{10, 9, 8, 7, 6, 5, 4},
{19, 18, 17, 16, 15, 14, 13},
{23, 21, 17, 12, 8, 3, 1},
{22, 20, 15, 11, 6, 2, 0},
{13, 14, 15, 16, 17, 18, 19},
{4, 5, 6, 7, 8, 9, 10}
};
int opp[8] = {5, 4, 7, 6, 1, 0, 3, 2}; // A<->F,B<->E,C<->H,D<->G
int goal[8] = {6, 7, 8, 11, 12, 15, 16, 17}; // 中间八个位置坐标
char ch[8] = {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H'};
int h(int board[]) { // 启发函数的值：设置为8-已在中间八个位置的最多的数的个数
int cnt[3] = {0, 0, 0}, ret = 0;
for (int i = 0; i < 8; i++) {
cnt[ board[ goal[i] ] - 1 ]++;
}
return 8 - max(cnt[0], max(cnt[1], cnt[2]));
return ret;
}
void change(int idx) {
int tmp = board[ map[idx][0] ];
for (int i = 0; i < 6; i++) {
board[ map[idx][i] ] = board[ map[idx][i+1] ];
}
board[ map[idx][6] ] = tmp;
}
bool flg;
int ans[10000], bound;
int dfs(int dv, int pre) {
int hv = h(board);
if (hv + dv > bound) {
return hv + dv;
}
if (hv == 0) {
flg = true;
return dv;
}
int next_bound = 1<<30;
for (int k = 0; k < 8; k++) {
if (opp[k] == pre) {
continue;
}
ans[dv] = k;
change(k);
int new_bound = dfs(dv + 1, k);
if (flg) {
return new_bound;
}
next_bound = min(next_bound, new_bound);
change(opp[k]);
}
return next_bound;
}
bool id_astar() {
flg = false;
bound = h(board);
if(bound == 0) {
return false;
}
while(!flg && bound < 1000) {
bound = dfs(0, -1);
}
return flg;
}
int main() {
//freopen("in.in", "r", stdin);
while(scanf("%d", board+0) && board[0]) {
for (int k = 1; k < 24; k++) {
scanf("%d", board + k);
}
if(id_astar() == false) {
printf("No moves needed\n%d\n", board[6]);
continue;
}
for (int i = 0; i < bound; i++) {
putchar( ch[ ans[i] ]);
}
printf("\n%d\n", board[6]);
}
return 0;
}
小结：以上两个题目为A*模型和IDA*模型的基本应用，就是为了熟悉一下两个代码。下面的题目需要点时间思考的。
Booksort
问题概述：给定编号为1..N的一行书架，放着编号为1…N的混乱放置的书，先可以进行插排，问能否在4次包含4次以内 书的数的编号为1…N.
问题提分析：题目告诉了最多操作的次数，进行dfs的操作也应该是可以的，4^16次方的复杂度，需要慎重考虑，需要强有力的剪枝。用IDA*来解决这个问题是完全可以的。说一下启发函数的正确性：
启发函数的值：左侧的书和当前的书放置错误的数目。
对于A*算法的第一个必须条件是显然成立的。现在说明第二个条件的正确性，[0. a-1] [a, b] [b+1, c][c+1, n-1] 我们将元序列划分成4段（因为每次移动的可能为一个子序列），这样如果book[a-1] + 1== book[a] 且book[b] + 1 == book[b+1] 且book[c] + 1 == book[n-1]. 那么h的值最多将减少3. 而如果记实际代价函数为g = depth.那么是不相容的，不能满足第二个条件，这时我们知道深度每次是增加1的，如果乘以3，即g = 3*depth. 那么由f=g+h.可知，f仍然满足单调递增的特性，即满足第二个条件。
知道了上面启发函数的设计方法，这个题目就很简单了！下面分享我的代码（启发函数的设计思路<黑皮书》P169）
#include <iostream>
using namespace std;
int shelf[16], n;
int h(int shelf[]) {
int ret = 0;
for (int i = 1; i < n; i++) {
ret += shelf[i-1] + 1 != shelf[i];
}
return ret;
}
int t[16];
void change(int a, int b, int c) { //[a, b], [b+1, c]
int m = 0;
for (int k = b+1; k <= c; k++) {
t[m++] = shelf[k];
}
for (int k = a; k <= b; k++) {
t[m++] = shelf[k];
}
for (int k = a; k <= c; k++) {
shelf[k] = t[k-a];
}
}
int bound, flg;
int dfs(int dv) {
int hv = h(shelf);
if (hv + 3*dv > 3*bound) {
return (hv + 3*dv + 2)/3;
}
if (hv == 0) {
flg = true;
return dv;
}
int nxt_bound = 5, new_bound;
for (int i = 0; i < n-1; i++) {
for (int j = i; j < n-1; j++) {
for (int k = j + 1; k < n; k++) {
change(i, j, k);
new_bound = dfs(dv + 1);
if (flg) {
return new_bound;
}
nxt_bound = min(nxt_bound, new_bound);
change(i, i + k -j-1, k);
}
}
}
return nxt_bound;
}
bool id_astar() {
bound = 0;
flg = false;
while(!flg && bound < 5) {
bound = dfs(0);
}
return flg;
}
int main() {
//freopen("in.in", "r", stdin);
int ca; scanf("%d", &ca);
while(ca-- && scanf("%d", &n)) {
for (int i = 0; i < n; i++) {
scanf("%d", shelf + i);
}
if (id_astar() == false) {
puts("5 or more");
} else {
printf("%d\n", bound);
}
}
return 0;
}
Robot
LBOY: 机器人寻路的问题，思路很简单，深搜和广搜都可以，不过这个题目要求强有力的剪枝，一个思路就是启发搜索。
启发函数的设计思路很明显，当前位置距离终点的曼哈顿距离。
但是，题目机器人一次最多可以向前走三步，这里就不能在用搜索树的深度来作为我们要求的实际代价值g()了，因为这样会导致h()不相容。我的h()函数一次最多减小3.那么我一次至少增加三就是了。也对。和上面的一题的思路一样，我们也要配三的方法，g() = depth * 3。 这样h()就是相容的了。可以证明，这是的估价函数可以找到最优解。
#include <iostream>
#include <queue>
using namespace std;
const int stp[4][2] = {
{-1, 0}, {0, 1}, {1, 0}, {0, -1}
}; // n, e, s, w;
const int turn[2] = { 1, -1};
int m, n;
bool mat[50][50];
int f[4][50][50];
int d[4][50][50];
bool c[4][50][50];
int dir[27];
char s[10];
struct node {
int x, y, d;
node(int x=0, int y=0, int d=0)
:x(x), y(y), d(d) {}
bool operator < (const node &p) const {
return f[d][x][y] > f[p.d][p.x][p.y];
}
bool operator == (const node &p) const {
return x == p.x && y == p.y;
}
void out() {
printf("(%d, %d: %d), %d \n", x, y, d, f[d][x][y]);
}
}beg, end, cur;
priority_queue<node> q;
inline bool check(int x, int y) {
if (x <= 0 || x >= m || y <= 0 || y >= n) {
return false;
}
if (mat[x-1][y-1] || mat[x-1][y] || mat[x][y-1] || mat[x][y]) {
return false;
}
return true;
}
inline int dist(int x, int y) {
return abs(x - end.x) + abs(y - end.y);
}
inline void deal(node &cur, int x, int y, int di) {
if (c[di][x][y] == 0) {
c[di][x][y] = 1;
d[di][x][y] = d[cur.d][cur.x][cur.y] + 1;
f[di][x][y] = d[di][x][y] + (dist(x, y) + 2)/3;
q.push(node(x, y, di));
}
else if (c[di][x][y] == 1) {
if (d[di][x][y] > d[cur.d][cur.x][cur.y] + 1) {
d[di][x][y] = d[cur.d][cur.x][cur.y] + 1;
f[di][x][y] = d[di][x][y] + (dist(x, y) + 2)/3;
q.push(node(x, y, di));
}
}
}
int astar() {
if (!check(beg.x, beg.y) || !check(end.x, end.y)) {
return -1;
}
memset(c, 0, sizeof(c));
while(!q.empty()) q.pop();
c[beg.d][beg.x][beg.y] = 1;
d[beg.d][beg.x][beg.y] = 0;
f[beg.d][beg.x][beg.y] = (dist(beg.x, beg.y)+2)/3;
q.push(beg);
int x, y, di;
while(!q.empty()) {
cur = q.top(); q.pop();
if (cur == end) {// cur.out(); //continue;
return d[cur.d][cur.x][cur.y];
}
for (int k = 1; k <= 3; k++) {
x = cur.x + k * stp[cur.d][0];
y = cur.y + k * stp[cur.d][1];
if (check(x, y) == true) {
deal(cur, x, y, cur.d);
} else break;
}
for (int k = 0; k < 2; k++) {
di = (cur.d + turn[k] + 4) % 4;
deal(cur, cur.x, cur.y, di);
}
}
return -1;
}
int main() {
// freopen("in.in", "r", stdin);
dir['n' - 'a'] = 0; dir['e' - 'a'] = 1;
dir['s' - 'a'] = 2; dir['w' - 'a'] = 3;
while(scanf("%d %d", &m, &n) != EOF) {
if (m == 0 && n == 0) break;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
scanf("%d", mat[i] + j);
}
}
scanf("%d %d", &beg.x, &beg.y);
scanf("%d %d", &end.x, &end.y);
scanf("%s", s);
beg.d = dir[s[0] - 'a'];
// puts(s); beg.out(); end.out();
printf("%d\n", astar());
}
return 0;
}
周界搜索
LBOY: 结束之前，再引入一个概念，“周界搜索”----当目标状态或者起始状态固定，每次改变的都是另外一个状态的时候，我们就可以用先予处理出，固定状态到其它所有状态的最短路径，这种搜索算法，称为“周界搜索”（引致LRJ的黑皮书P165）
Pushing Boxes
LBOY: 这个是推箱子游戏的简化版，想研究推箱子游戏算法的，可以参考刘如佳的论文《搬运工的启示》，讲解的十分到位。这个题目说的只有一个箱子，一个人，一个目标地点，问用最少的步数将箱子推到目标地点。
题目分析：我们可以一次bfs求出箱子的目标节点到board的每一个小格子的最短距离（广搜第一次到达时候的距离就是最小的）。然后，我们进行启发式搜索，这里我们规定启发函数是 当前位置到目标位置的最短距离。每一步，我们最多推箱子一次，这样，箱子最多往前前进一步，那么估价函数满足单调性，所以这样设计启发函数可以找到最优i解。
代码写的有点长，5k+. 判重的时候我们要记录人和箱子的位置，来进行判重。详细的过程可以参考我的代码：
#include <iostream>
#include <queue>
using namespace std;
int row, col;
char mat[21][21];
int h[21][21];
int d[21][21][21][21];
int f[21][21][21][21];
char c[21][21][21][21];
struct node {
int x1, y1, x2, y2, p, s; // box & man & parent_id
node(int x1=0, int y1=0, int x2=0,int y2=0, int s=0,int p=0)
:x1(x1), y1(y1), x2(x2), y2(y2), s(s), p(p) {}
bool operator < (const node &b) const {
return s == b.s ? f[x1][y1][x2][y2] > f[b.x1][b.y1][b.x2][b.y2]:s > b.s;
}
bool operator == (const node &b) const {
return x1 == b.x1 && y1 == b.y1;
}
void out() {
printf("box:(%d, %d), man:(%d, %d)\n", x1, y1, x2, y2);
}
}start, target;
priority_queue<node> q;
int n;
struct path {
char ch; int p;
void set(char ch, int p) {
this->ch = ch; this->p = p;
}
}p[1<<18];
char ans[1<<10];
struct rnode {
int x, y; // box
rnode(int x=0,int y=0):x(x), y(y) {}
};
queue<rnode> rq;
const int stp[4][2] = {
{-1, 0}, {1, 0}, {0, -1}, {0, 1}
};
const char letter[2][4] = {
{'n', 's', 'w', 'e'},
{'N', 'S', 'W', 'E'}
};
inline bool islegal(int x, int y) {
return x >=0 && x < row && y >= 0 && y < col && mat[x][y] != '#';
}
void bfs(int x, int y) {
memset(h, -1, sizeof(h));
while(!rq.empty()) rq.pop();
rq.push(rnode(x, y));
h[x][y] = 0;
rnode cur;
while(!rq.empty()) {
cur = rq.front(); rq.pop();
for (int k = 0; k < 4; k++) {
x = cur.x + stp[k][0];
y = cur.y + stp[k][1];
if (islegal(x, y) == true) {
if (h[x][y] == -1) {
rq.push(rnode(x, y));
h[x][y] = h[cur.x][cur.y] + 1;
}
}
}
}
}
int astar() {
memset(c, 0, sizeof(c));
while(!q.empty()) q.pop();
n = 0;
c[start.x1][start.y1][start.x2][start.y2] = 1;
d[start.x1][start.y1][start.x2][start.y2] = 0;
f[start.x1][start.y1][start.x2][start.y2] = h[start.x1][start.y1];
p[n].set(0, -1); start.p = 0; start.s = 0; n++;
q.push(start);
node cur;
int x1, y1, x2, y2, s; char ch;
while(!q.empty()) {
cur = q.top(); q.pop();
if (cur == target) {
return cur.p; //d[cur.x1][cur.y1][cur.x2][cur.y2];
}
for (int k = 0; k < 4; k++) { // N, S, W, E
x2 = cur.x2 + stp[k][0];
y2 = cur.y2 + stp[k][1];
if (islegal(x2, y2) == true) {
if (x2 == cur.x1 && y2 == cur.y1) {
x1 = x2 + stp[k][0];
y1 = y2 + stp[k][1];
ch = letter[1][k];
s = cur.s + 1;
} else {
x1 = cur.x1;
y1 = cur.y1;
ch = letter[0][k];
s = cur.s;
}
if (islegal(x1, y1) == true) {
if (c[x1][y1][x2][y2] == 0) { // 未访问
c[x1][y1][x2][y2] = 1; // 插入open
d[x1][y1][x2][y2] = d[cur.x1][cur.y1][cur.x2][cur.y2] + 1;
f[x1][y1][x2][y2] = d[x1][y1][x2][y2] + h[x1][y1];
p[n].set(ch, cur.p);
q.push(node(x1, y1, x2, y2, s, n++));
}
else if (c[x1][y1][x2][y2] == 1) {
if (d[x1][y1][x2][y2] > d[cur.x1][cur.y1][cur.x2][cur.y2] + 1) {
d[x1][y1][x2][y2] = d[cur.x1][cur.y1][cur.x2][cur.y2] + 1;
f[x1][y1][x2][y2] = d[x1][y1][x2][y2] + h[x1][y1];
p[n].set(ch, cur.p);
q.push(node(x1, y1, x2, y2, s, n++));
}
}
}
}
}
}
return -2;
}
int main() {
//freopen("in.in", "r", stdin);
// freopen("out.out", "w", stdout);
int ca = 0;
while(scanf("%d %d", &row, &col) && (row || col)) {
for (int i = 0; i < row; i++) {
scanf("%s", mat + i);
for (int j = 0; j < col; j++) {
if (mat[i][j] == 'B') {
start.x1 = i;
start.y1 = j;
}
if (mat[i][j] == 'S') {
start.x2 = i;
start.y2 = j;
}
if (mat[i][j] == 'T') {
target.x1 = i;
target.y1 = j;
}
}
}
bfs(target.x1, target.y1);
int par = astar();
printf("Maze #%d\n", ++ca);
if (par == -2) {
puts("Impossible.");
} else {
n = 0;
while(par) {
ans[n++] = p[par].ch;
par = p[par].p;
}
while(n--) putchar(ans[n]);
putchar('\n');
}
putchar('\n');
}
}
小结：对于A*和IDA*的文字性总结就到这里，以后遇到好的题目，在继续总结。3Q!
- 无匹配
评论 (0)
Copyright © 2007