zcmimi's blog
avatar
zcmimi
2020-09-23 17:16:30

前置知识:

  • 迭代加深搜索
  • A*

迭代加深搜索

迭代加深搜索是一种每次限制搜索深度的深度优先搜索。

首先设定一个较小的深度作为全局变量,进行DFS

每进入一次DFS,将当前深度加一,当发现大于设定的深度就返回。

如果在搜索的途中发现了答案就可以回溯,同时在回溯的过程中可以记录路径。

如果没有发现答案,就返回到函数入口,增加设定深度,继续搜索。

在大多数的题目中,广度优先搜索还是比较方便的,而且容易判重。

当发现广度优先搜索在空间上不够优秀,而且要找最优解的问题时,就应该考虑迭代加深。

A*

A*算法是BFS的一种改进

定义起点s,终点t,

sx的估价函数g(x),

xt的估价函数h(x),

定义x的估价函数f(x)

A*算法每次从优先队列中取出一个f(x)最小的x,然后更新相邻的状态

如果h(x)不超过x的实际答案,则A*算法能找到最优解

上述条件下,如果h满足三角形不等式,则A*算法不会将重复结点加入队列

IDA*

IDA*,即采用迭代加深的A*算法。相对于A*算法,IDA*改成了深度优先的方式

  • 不需要判重,不需要排序
  • 空间需求减少

优点:

  • 空间开销小,每个深度下实际上是一个深度优先搜索,不过深度有限制,而DFS的空间消耗小是众所周知的;
  • 利于深度剪枝。

缺点:

重复搜索:回溯过程中每次设定的深度变大都要再次从头搜索

影响不大

例题

[AHOI2012]铁盘整理

给定一个长度为n互不相同的序列a_i,每次操作可以将[1,i],i\in[1,n]翻转,求最少几次操作可以使它变成升序数列。(1 \le n \le 50, 1 \le a_i \le 100)

首先将数组离散化为1,2,\dots,n

一次翻转最多只能改变一对相邻数的差,

因此对于一个序列,有多少对相邻的数差不为1,就至少要翻转多少次。

估价函数:

a[n+1]=n+1;
int h(){
    int cnt=0;
    for(int i=1;i<=n;++i)cnt+=(a[i]!=a[i+1]+1&&a[i]!=a[i+1]-1);
    return cnt;
}

完整代码:

#include<bits/stdc++.h>
const int N=100011;
int n,mxd,a[N],b[N];
bool sol;
int h(){ // 估价函数
    int cnt=0;
    for(int i=1;i<=n;++i)cnt+=(a[i]!=a[i+1]+1&&a[i]!=a[i+1]-1);
    return cnt;
}
void dfs(int g,int pre){
    if(sol||g+h()>mxd)return;
    if(!h())return sol=1,void();
    for(int i=1;i<=n;++i)if(i!=pre){
        std::reverse(a+1,a+i+1);
        dfs(g+1,i);
        std::reverse(a+1,a+i+1);
    }
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i)scanf("%d",a+i),b[i]=a[i];
    std::sort(b+1,b+n+1);
    for(int i=1;i<=n;++i)a[i]=std::lower_bound(b+1,b+n+1,a[i])-b;
    a[n+1]=n+1;
    for(int i=0;!sol;++i){
        mxd=i,dfs(0,0);
        if(sol)printf("%d\n",i);
    }
}
IDA*
comment评论
Search
search