UVA11212 EditingaBook ( IDA*搜索)
2024-09-07 06:51:03
首先说说IDS,就DFS限定一个层数上限maxd,如果在maxd范围内没有找到解,就增加maxd,继续搜索。
当访问到当前结点u时,估计还要搜索h(u)层,如果h(u)+当前层数d>maxd的时候就剪枝,这就是IDA*。
IDA*属于DFS,当状态空间某一层的结点数无穷大时,BFS失效,只能DFS。
相比BFS,它的空间占用少(不需要判重复),时间效率也不低。
注意:A*的关键在于选取估价函数h()。
----------------------------------分割线-------------------------------------------------------------
来说说 UVA11212 EditingaBook
缩小搜索空间的策略有
策略1:只剪切连续的数字片段。
策略2:剪切的片段头为a尾为b,要么粘贴到a-1的后面,要么粘贴到b+1前面。
策略3:不要破坏已经连续的片段。
但是策略1和策略2并能保证正解:如5 4 3 2 1 —》 3 2 5 4 1 —》 3 4 1 2 5 -》 1 2 3 4 5。
策略1,2出错主要是因为忽略了后效性,策略3是可以的,把连续的片段看成整体,拆开它一定是比不拆它的步数要少。
下面寻找估价函数
由于每次剪切最多更改3个数字的前继(或后继),所以统计前继不对的数字个数为n个那么只少还要搜n/3层。如果d+n/3>maxd即3*d+n>maxd就剪枝。
还有一个剪枝是:移动片段b1~b2到b2+1~c后面,相当于移动b2+1~c到b1~b2前面,所以只要枚举把片段往后移动就行了。
//Rey
#include<bits/stdc++.h> const int maxn = ; int n,a[maxn]; inline bool End()
{
for(int i = ; i < n; i++){
if(a[i] <= a[i-]) return false;
}
return true;
} inline int h()
{
int cnt = ;
for(int i = ; i < n; i++)
if(a[i] != a[i-]+) cnt++;
return cnt;
} int maxd;
const int intsz = sizeof(int);
const int asz = sizeof(a);
bool dfs(int d)
{
if(*d + h() > *maxd) return false;
if(End()) return true; int old[maxn];//保存a
memcpy(old,a,asz);
int b[maxn];//剪切板 for(int i = ; i < n; i++) if( i == || old[i] != old[i-] + ) //策略3 选择尽量长的连续片段 剪切的起点
for(int j = i; j < n; j++) { //终点 和 策略2不同选取片段可以不连续
while(j+ < n && old[j+] == old[j] + )j++;//策略3
memcpy(b,old+i,intsz*(j-i+));
//剪切移动片段
for(int k = j+;k < n;k++){//由于对称性,只要往后贴就行了
while(k+ < n && old[k+] == old[k] + )k++;//策略3 不破坏
memcpy(a+i,old+j+,intsz*(k-j));
memcpy(a+i+k-j,b,intsz*(j-i+));
if(dfs(d+))return true;
//恢复
memcpy(a,old,asz);
}
}
return false;
} inline int solve()
{
if(End())return ;
for(maxd = ; maxd < ;maxd++)
if(dfs()) return maxd;
return ;
}
int main()
{
//freopen("in.txt","r",stdin);
int Cas = ;
while(~scanf("%d",&n)&&n) {
for(int i = ; i < n; i++)
scanf("%d",a+i);
int ans = solve();
printf("Case %d: %d\n",++Cas,ans);
}
return ;
}
最新文章
- Oracle时间戳(毫秒)转为Date
- L2TP协议
- 一些Android程序的反逆向方法
- linux bugfree 安装
- Hadoop集群配置(最全面总结)
- java基础(一章)
- Example015实现html中checkbox的全选和反选(2)
- python+appium+unittest
- Java基础学习笔记十八 异常处理
- WaitGroup
- scrapy学习笔记(1)
- Spring核心模块:IoC容器介绍
- 使用多线程提高Rest服务性能
- c语言可变参
- mysql 查询优化~sql优化通用
- JS client(X,Y)、screen(X,Y)、page(X,Y)的区别
- JAVA开发人员画图表总结(ECHARTS)
- 进阶之路(基础篇) - 008 SPI数据传输(库函数方法)
- Linux基础命令---chmod
- Mcode的介绍