一、A * ：
估价函数的设计准则：估值f（state）≤未来实际代价g（state）。
A * 算法的实现，A * =优先队列BFS+估价函数。
1。优先队列BFS算法维护了一个优先队列，不断从堆中取出当前代价最小的状态
进行扩展。每个状态第一次从堆中取出时，就得到了从初态到该状态的最小代价。
如果给定一个目标状态，需要求出从初态到目标状态的最小代价，那么优先队列
BFS这个优先策略是不完善的。
2。为了提高搜索效率，我们很自然的想到，可以对未来可能产生的代价进行预估。
详细的讲：我们设计一个估价函数，以任意状态为输入，计算出从该状态到目标状态所
需代价的估计值。在搜索中，仍然维护一个堆，不断从堆中取出 当前代价+未来估价 最小的状态进行扩展
3。为了保证第一次从堆中取出目标状态时得到的就是最优解，我们设计的估价函数需要满足一个基本准则：估价函数的估值不能大于未来实际代价，估价比实际代价更优。
4。这种带有估价函数的优先队列BFS就称为A * 算法。只要保证对于任意状态state，都有f（state）≤g（state），A * 算法就一定能在目标状态第一次从堆中被取出时得到最优解，并且在搜索过程中每个状态只需要被扩展一次（之后再被取出就可以直接忽略）。估价f（state）越准确，越接近g（state），A * 算法的效率就越高。如果估价始终为5.0，就等价于普通优先队列BFS。
5。A * 算法提高搜索效率的关键，就在于能否设计出一个优秀的估价函数。估价函数在满足上述设计准则的前提下，含应该尽可能反映未来实际代价的变化趋势和相对大小关系，这样搜索才会较快的逼近最优解。
例题：POJ2449： 第K短路。
对于任意正整数i和任意节点x，当第i次从堆中取出包含节点x的二元组时，对应的dist值就是从S到x的第i短路。
使用优先队列BFS在最坏的情况下的复杂度为O（K （N+M）log（N+M））。这道题目给定了起点和终点，求长度最短（代价最小）的路径，可以考虑使用A*算法提高搜索效率。
得到以下解题步骤：
（1）预处理出各个节点x到终点T的最短路长度f（x）——这等价于在反向图上以T为起点求解单源最短路径问题，可以在O（（N+M）log(N+M) ）的时间内完成。
（2）建立一个二叉堆，存储一些二元组（x，dist+f（x）），其中x为节点编号，dist表示S到x当前走过的距离。起初堆中只有（S，0+f（S））。
（3）从二叉堆中取出dist+f（x）最小的二元组（x，dist+f（x）），然后沿着从x出发的每条边（x，y）进行扩展。如果节点y被取出的次数尚未到达K，就把新的二元组（y，dist+lenth（x，y）+f（y））插入堆中。
（4）重复2-3步，直至第k次取出包含终点T的二元组，此时二元组中的dist值就是从S到T的第K短路。
A * 算法的复杂度上届与优先队列BFS相同。不过，因为估价函数的作用，图中很多节点的访问次数都远小于k。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
#include<algorithm>
#include<queue>
#include<cmath>
#include<string>
#define ll long long
using namespace std;
const int maxn=10010;
const int mmax=100010;
int n,m,s,t,k;
int x,y,z;
int dis[maxn],head[maxn],ver[mmax],nt[mmax],edge[mmax];
int _head[maxn],_ver[mmax],_nt[mmax],_edge[mmax];
int tot,_tot;
bool ha[maxn];
int num[maxn];
struct node
{
int x;
int dx;
int fx;
node () {}
node(int a,int b,int c)
{
x=a;
dx=b;
fx=c;
}
friend bool operator <(const node &a,const node &b)
{
return a.dx+a.fx>b.dx+b.fx;
}
};
void add(int x,int y,int z)
{
ver[++tot]=y,edge[tot]=z;
nt[tot]=head[x],head[x]=tot;
}
void _add(int x,int y,int z)
{
_ver[++_tot]=y;
_edge[_tot]=z;
_nt[_tot]=_head[x];
_head[x]=_tot;
}
void Dij(int T)
{
priority_queue< pair<int,int> >q;
memset(dis,0x3f,sizeof(dis));
dis[T]=0;
memset(ha,0,sizeof(ha));
q.push(make_pair(0,T));
while(q.size())
{
int x=q.top().second;
q.pop();
if(ha[x]) continue;
ha[x]=true;
for(int i=_head[x];i;i=_nt[i])
{
int y=_ver[i],z=_edge[i];
//printf("y: %d\n",y);
if(dis[y]>dis[x]+z)
{
dis[y]=dis[x]+z;
q.push(make_pair(-dis[y],y));
}
}
}
//printf("dis: %d %d\n",dis[1],dis[2]);
return ;
}
int sk(void)
{
memset(num,0,sizeof(num));
priority_queue<node>q;
q.push(node(s,0,dis[s]));
while(q.size())
{
node now=q.top();
q.pop();
num[now.x]++;
//printf("%d %d \n",now.x,now.dx);
if(num[now.x]>k) continue;
if(num[now.x]==k&&now.x==t) return now.dx;
for(int i=head[now.x];i;i=nt[i])
{
int y=ver[i],z=edge[i];
//printf("y2: %d\n",y);
q.push(node(y,now.dx+z,dis[y]));
}
}
return -1;
}
int main(void)
{
while(scanf("%d%d",&n,&m)!=EOF)
{
memset(head,0,sizeof(head));
memset(_head,0,sizeof(_head));
tot=0;
_tot=0;
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);
_add(y,x,z);
}
scanf("%d%d%d",&s,&t,&k);
if(s==t)k++;
Dij(t);
printf("%d\n",sk());
}
return 0;
}
**二、IDA *： **
IDA * ＝迭代加深DFS + 估价函数。
把估价函数与迭代加深的DFS算法相结合。
迭代加深的DFS算法限定一个深度，在不超过该深度的前提下执行DFS，若找不到解就扩大深度限制，重新进行搜索。
我们需要设计一个估价函数，估算从每个状态到目标状态需要的步数。当然，与A * 算法一样，估价函数需要遵守 估计值不大于未来实际步数 的准则。然后，以迭代加深的DFS的搜索框架为基础，把原来简单的深度限制加强为： 若当前深度+未来估计步数＞深度限制，则立即从当前分支回溯。
例题：POJ3460：Booksort：
本题有两种解法：
（1）采用双向BFS，从起始状态、目标状态开始各搜2步，看能否到达相同的状态进行衔接，复杂度降低为5602。
（2）采用IDA * ：
在目标状态下，第i本书后面应该是第i+1本书，我们称i+1是i的正确后继。
对于任意状态，考虑整个排列中书的错误后继的总个数（记为tot），可以发现么此操作至多更改3本书的后继。即使在最理想的情况下，每次操作都能把某3个错误后继全部改对，消除所有错误后继的操作次数至少也需要（tot/3） 向上取整，次。
因此我们把一个状态的估价函数设计为f（s）=（tot/3），其中tot表示在状态s下书的错误后继总数。
我们采用迭代加深的方法，从1–4依次限制搜索深度，然后从起始状态出发DFS。DFS时，在每个状态下直接枚举抽取哪一段、移动到更靠后的哪个位置，沿着该分支深入即可。
注意在进入任何状态S后，我们先进行判断，如果当前操作次数加上f（s）已经大于深度限制，直接从当前分支回溯。
注意：把一段书移动到更靠前的某个位置，等价于把跳过的那段书移动到靠后的某个位置。
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#include<queue>
using namespace std;
int n, shell[21];
// swap [x1, x2] and [x2 + 1, x3]
void move (int x1, int x2, int x3)
{
int tmp[21], i, j;
for(i=x2+1,j=0;i<=x3;i++,j++)
tmp[j]=shell[i];
for (i=x1;i<=x2;i++,j++)
tmp[j]=shell[i];
for (i=x1,j=0;i<=x3;i++,j++)
shell[i] = tmp[j];
return;
}
int hfunc(void)
{
int i,ans=0;
for(i=0;i<n-1;i++)
if (shell[i+1]!=shell[i]+1) ans++;
//if (shell[n-1]!=n) ans++;
return ans;
}
int maxdepth;
int dfs (int depth)
{
int x1, x2, x3, h;
for (x1=0;x1<=n-2;x1++)
{
for (x2=x1;x2<=n-2;x2++)
{
for (x3=x2+1;x3<=n-1;x3++)
{
move(x1,x2,x3);
h=hfunc();
if(h==0) return 1;
else if (3*depth+h<=3*maxdepth)
{
if (dfs(depth+1)) return 1;
}
move(x1,x1+x3-x2-1,x3);
}
}
}
return 0;
}
int main ()
{
int kase, i;
scanf("%d", &kase);
for (;kase>0;kase--)
{
scanf("%d",&n);
for (i=0;i<n;i++)
scanf("%d", &shell[i]);
maxdepth=(int)ceil((double)hfunc() / 3);
if (maxdepth) while (maxdepth<5&&dfs(1)==0) maxdepth++;
if (maxdepth == 5) printf("5 or more\n");
else printf("%d\n", maxdepth);
}
return 0;
}
京公网安备 11010502036488号