高级搜索算法

导语

点击查看

一.迭代加深

所谓迭代加深，它有着两个特征：一是它是个最优解问题，二是最优的答案深度最小

迭代加深搜索，实质上就是限定下界的深度优先搜索。即首先允许深度优先搜索K层搜索树，若没有发现可行解，再将K+1后重复以上步骤搜索，直到搜索到可行解。

虽然说有一定的重复，可是这样这样可以更快减少搜索深度

先来看道例题：

1.SCOI2005骑士精神

这道题是一道很典型的可以用高级搜索的题目，且不止迭代深搜一种方法

由于已经规定的15步，所以我们可以把搜索深度定为0—15

然后再进行普通的dfs，但是如果深度大于范围，直接return

就有：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
using namespace std;
int t;
int dis[9][2] = { { 2, 1 }, { 2, -1 }, { -2, 1 }, { -2, -1 }, { 1, 2 }, { 1, -2 }, { -1, 2 }, { -1, -2 } };//方向
int vis[7][7];
int vis1[7][7];
bool flag;
int sx, sy;
bool check() {
    for (int i = 1; i <= 5; i++) {
        if (vis1[1][i] != 1)
            return 0;
        if (i != 1)
            if (vis1[2][1] != 0 || vis1[2][i] != 1)
                return 0;
        if (i != 5)
            if (vis1[4][5] != 1 || vis1[4][i] != 0)
                return 0;
        if (vis1[5][i] != 0)
            return 0;
    }
    if (vis1[3][1] != 0 || vis1[3][2] != 0)
        return 0;
    if (vis1[3][4] != 1 || vis1[3][5] != 1)
        return 0;
    return 1;
}//也可以用一个二维数组比较
void dfs(int st, int mst, int kx, int ky) {
    if (st > mst)
        return;//大于就退出
    if (vis1[3][3] == 2 && check()) {
        flag = 1;//找到就返回
        return;
    }
    for (int i = 0; i < 8; i++) {
        int tx = kx + dis[i][0];
        int ty = ky + dis[i][1];
        if (tx > 0 && ty > 0 && tx <= 5 && ty <= 5) {
            int o = vis1[tx][ty];
            vis1[tx][ty] = vis1[kx][ky];
            vis1[kx][ky] = o;
            dfs(st + 1, mst, tx, ty);
            vis1[tx][ty] = o;
            vis1[kx][ky] = 2;
            if (flag)
                return;
        }
    }
}
void IDDFS() {
    flag = 0;
    for (int ans = 0; ans <= 11; ans++) {
        for (int i = 1; i <= 5; i++)
            for (int j = 1; j <= 5; j++) vis1[i][j] = vis[i][j];
        dfs(0, ans, sx, sy);
        if (flag) {//枚举范围
            printf("%d\n", ans);
            return;
        }
    }
    printf("-1\n");
}
int main() {
    scanf("%d", &t);
    while (t--) {
        for (int i = 1; i <= 5; i += 1)
            for (int j = 1; j <= 5; j++) {
                char c = getchar();
                while (c == ' ' || c == '\n') c = getchar();
                if (c == '1')
                    vis[i][j] = 1;
                else if (c == '0')
                    vis[i][j] = 0;
                else {
                    sx = i, sy = j;
                    vis[i][j] = 2;
                }
            }
        IDDFS();
    }
    return 0;
}

由于这是自己很久之前写的，所以代码质量很不好

但是这样也过不了，会超时

我们考虑优化

如果我们现在已经走了的步数加上还与目标不相同点的个数（check()）大于范围，就可以直接退出了

因为我们每走一步，最多只会让一个格子到达目标位

所以至少还要check()步

这样，我们把check()这样的函数叫做乐观估计函数

改了之后就可以AC了

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
using namespace std;
int t;
int dis[9][2] = { { 2, 1 }, { 2, -1 }, { -2, 1 }, { -2, -1 }, { 1, 2 }, { 1, -2 }, { -1, 2 }, { -1, -2 } };
int vis[7][7];
int mu[7][7] = { { 0, 0, 0, 0 },       { 0, 1, 1, 1, 1, 1 }, { 0, 0, 1, 1, 1, 1 },
                 { 0, 0, 0, 2, 1, 1 }, { 0, 0, 0, 0, 0, 1 }, { 0, 0, 0, 0, 0 } };
bool flag;
int sx, sy;
int check() {
    int cnt = 0;
    for (int i = 1; i <= 5; i++)
        for (int j = 1; j <= 5; j++)
            if (vis[i][j] != mu[i][j])
                cnt++;
    return cnt;
}
void dfs(int st, int mst, int kx, int ky) {
    if (st > mst)
        return;
    if (check() == 0) {
        flag = 1;
        return;
    }
    for (int i = 0; i < 8; i++) {
        int tx = kx + dis[i][0];
        int ty = ky + dis[i][1];
        if (tx > 0 && ty > 0 && tx <= 5 && ty <= 5) {
            swap(vis[tx][ty], vis[kx][ky]);
            if (check() > mst - st) {
                swap(vis[kx][ky], vis[tx][ty]);
                continue;
            }

            dfs(st + 1, mst, tx, ty);
            swap(vis[kx][ky], vis[tx][ty]);
            if (flag)
                return;
        }
    }
}
void IDDFS() {
    flag = 0;
    for (int ans = 0; ans <= 15; ans++) {
        dfs(0, ans, sx, sy);
        if (flag) {
            printf("%d\n", ans);
            return;
        }
    }
    printf("-1\n");
}
int main() {
    scanf("%d", &t);
    while (t--) {
        for (int i = 1; i <= 5; i += 1)
            for (int j = 1; j <= 5; j++) {
                char c = getchar();
                while (c == ' ' || c == '\n') c = getchar();
                if (c == '1')
                    vis[i][j] = 1;
                else if (c == '0')
                    vis[i][j] = 0;
                else {
                    sx = i, sy = j;
                    vis[i][j] = 2;
                }
            }
        IDDFS();
    }
    return 0;
}

总结一下：

1.迭代深搜首先要给出搜索范围才可以用此方法

2.乐观估计函数的写法，且一定要记住这是估计最优时的情况（与A*相似）

然后还有这道题，也很有意思：

2.编辑书稿

给出1～n的一个排列，可以剪切连续的一段数，然后粘贴到某个位置。不能连续剪切两次，只能剪切和粘贴交替。目标是把排列变成1～n的升序排列。

例如，为了将{2,4,1,5,3,6}变为升序，可以剪切1，放在2前，然后剪切3，将其放在4前。再如，对于排列{3,4,5,1,2}，只需要一次剪切和一次粘贴即可。

输入格式

多数数据，每个测试点包含不超过20组数据，每组数据的格式为：

第1行：1个整数n(2<=n<=12)

第2行：1～n的一个随机排列

当n=0时，表示输入结束

输出格式

对每个数据，输出一个整数，表示需要最少的操作次数。剪切-粘贴一次算为一次操作。

样例

样例输入

6
2 4 1 5 3 6
5
3 4 5 1 2
0

样例输出

Case 1: 2
Case 2: 1

 其实把小的数往前移与把大的数往后移是一样的，且如果我交换的这一个序列的开头已经符合，那么如果再把这条链操作就会更大

然后就没有什么难点。

二.双向BFS（DBFS）

如果我们已经知道搜索的起点状态与终点状态，那么我们就可以用DBFS

于是就从两边向中间直接搜索即可，两边最先接触到时，就直接退出

但是每个状态怎么做呢？

我们就需要用到hash，这也是DBFS的难点。

每一种状态只能映射一个值.

我们常有的有：

1.康托展开

2.坐标做值

3.k进制

而上面的骑士精神这道题，我们就可以用DBFS来做：

把整张图转化为二进制，而空位的坐标转化为二进制，就有

25+6=31个点，放好不爆int，这里，把空位也当做0

vis数组用map映射

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <queue>
#include <map>
using namespace std;
int t, goal[33] = { 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1 };
int a[33];
int dis[9][2] = { { 2, 1 }, { -2, 1 }, { 2, -1 }, { -2, -1 }, { 1, 2 }, { 1, -2 }, { -1, 2 }, { -1, -2 } };
int get_num(int s[]) {
    int k = 1, ans = 0;
    for (int i = 30; i >= 0; i--) {
        ans += k * s[i];
        k *= 2;
    }
    return ans;
}
struct node {
    int s[33];
    bool flag;
};
struct edge {
    bool flag;
    int step;
};
void DBFS() {
    queue<node> q;
    map<int, edge> vis[2];
    vis[1].clear();
    vis[0].clear();
    vis[0][get_num(a)].flag = 1;
    vis[1][get_num(goal)].flag = 1;
    vis[0][get_num(a)].step = vis[1][get_num(goal)].step = 0;
    node nx;
    for (int i = 0; i <= 30; i++) {
        nx.s[i] = a[i];
    }
    nx.flag = 0;
    q.push(nx);
    for (int i = 0; i <= 30; i++) {
        nx.s[i] = goal[i];
    }
    nx.flag = 1;
    q.push(nx);
    while (!q.empty()) {
        node tx = q.front();
        q.pop();
        int p = get_num(tx.s);
        if (vis[!tx.flag][p].flag) {
            if (vis[!tx.flag][p].step + vis[tx.flag][p].step <= 15)
                printf("%d\n", vis[!tx.flag][p].step + vis[tx.flag][p].step);
            else
                printf("-1\n");
            return;
        }
        int tu[6][6] = {};
        int k = 5;
        for (int i = 1; i <= 5; i++)
            for (int j = 1; j <= 5; j++) {
                k++;
                tu[i][j] = tx.s[k];
            }
        int x = 0, y = 0, t = 1;
        k = 5;
        while (k >= 3) {
            y += tx.s[k] * t;
            t *= 2;
            k--;
        }
        t = 1;
        while (k >= 0) {
            x += tx.s[k] * t;
            t *= 2;
            k--;
        }
        for (int i = 0; i < 8; i++) {
            int nex = x + dis[i][0];
            int ney = y + dis[i][1];
            if (nex <= 0 || nex > 5 || ney <= 0 || ney > 5)
                continue;
            swap(tu[nex][ney], tu[x][y]);
            int nex1 = nex, ney1 = ney;
            node px = tx;
            k = 2;
            while (k >= 0) {
                px.s[k] = nex % 2;
                nex /= 2;
                k--;
            }
            k = 5;
            while (k >= 3) {
                px.s[k] = ney % 2;
                ney /= 2;
                k--;
            }
            k = 5;
            for (int i = 1; i <= 5; i++)
                for (int j = 1; j <= 5; j++) px.s[++k] = tu[i][j];
            int tmp = get_num(px.s);
            swap(tu[nex1][ney1], tu[x][y]);
            if (vis[px.flag][tmp].flag)
                continue;
            vis[px.flag][tmp].flag = 1;
            vis[px.flag][tmp].step = vis[px.flag][get_num(tx.s)].step + 1;
            if (vis[px.flag][tmp].step > 7)
                continue;
            if (vis[!tx.flag][tmp].flag) {
                if (vis[!tx.flag][tmp].step + vis[tx.flag][tmp].step <= 15)
                    printf("%d\n", vis[!tx.flag][tmp].step + vis[tx.flag][tmp].step);
                else
                    printf("-1\n");
                return;
            }
            q.push(px);
        }
    }
    printf("-1\n");
}
int main() {
    scanf("%d", &t);
    int cnt = 5;
    while (t--) {
        cnt = 5;
        memset(a, 0, sizeof(a));
        for (int i = 1; i <= 5; i++) {
            for (int j = 1; j <= 5; j++) {
                char c = getchar();
                while (c == ' ' || c == '\n') c = getchar();
                if (c == '*') {
                    int i1 = i, j1 = j, k = 2;
                    while (k >= 0) {
                        a[k--] = i1 % 2;
                        i1 /= 2;
                    }
                    k = 5;
                    while (k >= 3) {
                        a[k--] = j1 % 2;
                        j1 /= 2;
                    }
                    a[++cnt] = 0;
                } else
                    a[++cnt] = c - '0';
            }
        }
        DBFS();
    }
    return 0;
}

其实编辑书稿我觉得也可以用dbfs，但是还没有实现

三.A*算法

其实自己还没有完全理解....

先mark一下