启发式搜索

这里对应的问题就是十六格拼图的问题，这里由于状态数较多，直接进行dfs或者bfs就无法在规定时间内求出解。这里就需要高等搜索算法了。

迭代加深

通过单纯的dfs无法在限定时间内找到初态到最终状态的最短路径，但是通过重复进行限制最大深度的DFS（深度受限搜索）却可以做到。简单地说就是在循环执行深度受限搜索的过程中逐步增加限制值limit，直到找到解为止。这种算法称为迭代加深。

PS：为了提高速度，迭代加深不会记录已经搜索过的状态。但是与此同时我们也需要做一些调整，防止出现回溯到上一状态的情况出现。

IDA*

在迭代加深中，通过推测值进行剪枝处理的算法成为IDA*或者A*。这里的推测值又称启发，通常取可以完成目标所需的下限值。

在十六格拼图中，如果能预估出当前状态到最终状态的最小成本h，我们就可以对搜索范围进行剪枝了。也就是说，如果当前深度g加上最小成本h（也就是在当前状态开始至少还需要h次状态迁移）超过了限制深度d，就可以直接中断搜索。

这里的h是一个预估值，不需要十分精确。并且，虽然增大h可以提高搜索速度，但是h太大的话可能会导致找不到解。

在十六宫格拼图问题中，我们以个拼图块到最终状态之间的曼哈顿距离总和为推测值h

A*

前面的是在迭代加深A*中使用推测值，实际上，推测值也可以用于含有优先级队列的狄克斯特拉算法（或广度优先搜索）为基础的算法，这类算法称为A*算法，它用优先级队列管理状态，优先对“起点到当前位置成本 当前位置到目标状态的推测值”最小的状态进行状态迁移，可以更快地找到解。

题目：ALDS1_13_C

下面是使用IDA*的解法

代码语言：javascript复制

#include <bits/stdc  .h>
using namespace std;

#define N 4
#define N2 16

const int dx[] = {0, -1, 0, 1}; //分别对应上左下右移动
const int dy[] = {1, 0, -1, 0};
const string pth[] = {"u", "l", "d", "r"};

vector<int> path;
const int max_limit = 45;
int limit;

struct node
{
    int f[N2];
    int space, MD;
};

int MDT[N2][N2]; //u到v的曼哈顿距离

node current;
int get_all_MD(const node &nd)
{
    int ans = 0;
    for (int i = 0; i < N2;   i)
    {
        if (nd.f[i] == N2)
            continue;
        ans  = MDT[nd.f[i] - 1][i];
    }
    return ans;
}

bool dfs(int depth, int prev)
{
    if (current.MD == 0)
        return true;
    //当前深度加上启发，超过限制，则进行剪枝。
    if (depth   current.MD > limit)
        return false;

    int sx = current.space / N;
    int sy = current.space % N;

    node tmp;
    for (int i = 0; i < 4;   i)
    {
        int tx = sx   dx[i];
        int ty = sy   dy[i];
        if (sx >= N || sx < 0 || sy >= N || sy < 0)
            continue;

        //防止回到上一状态
        if (abs(prev - i) == 2)
            continue;
        //暂存当前结果
        tmp = current;
        swap(current.f[current.space], current.f[tx * N   ty]);
        current.space = tx * N   ty;
        current.MD = get_all_MD(current);
        path.push_back(i);

        if (dfs(depth   1, i))
            return true;
        path.pop_back();
        current = tmp;
    }
    return false;
}

int solve(node& in)
{
    in.MD = get_all_MD(in);
    //cout<<in.MD<<endl;

    for (limit = in.MD; limit <= max_limit;   limit)
    {
        //cout << "limit:" << limit << endl;
        path.clear();
        if (dfs(0, -100))
        {
            return path.size();
        }
    }
    return -1;
}

int main()
{
    for (int i = 0; i < N2;   i)
    {
        for (int j = 0; j < N2;   j)
        {
            MDT[i][j] = abs(i / N - j / N)   abs(i % N - j % N);
        }
        cout << endl;
    }

    for (int i = 0; i < N2;   i)
    {
        cin >> current.f[i];
        if (current.f[i] == 0)
        {
            current.space = i;
            current.f[i] = N2;
        }
    }
    printf("%dn", solve(current));
    
}

转载请注明来源：https://www.longjin666.top/?p=1072

编程算法 迁移

0 人点赞