[关闭]
@Junlier 2018-10-02T23:57:33.000000Z 字数 2710 阅读 1672

搜索总结

算法——搜索
阅读体验:https://zybuluo.com/Junlier/note/1299772

定义

先复制一则定义

A*算法在人工智能中是一种典型的启发式搜索算法
启发中的估价是用估价函数表示的:
h(n)=f(n)+g(n)
其中f(n)是节点n的估价函数
g(n)表示实际状态空间中从初始节点到n节点的实际代价
h(n)是从n到目标节点最佳路径的估计代价。
另外定义h'(n)为n到目标节点最佳路径的实际值。
如果h'(n)≥h(n)则如果存在从初始状态走到目标状态的最小代价的解
那么用该估价函数搜索的算法就叫A*算法。

有点繁琐,但也看得过去

通俗来讲

的核心在于上面所讲到的估价函数
他是干什么用的呢
就是我们在搜索的过程中,保证更优的先搜用的
还是有些繁琐对不对,嗯,我也不大会讲啊(没事我会加油


嘿,认真看下面,我可认真了的啊。。。

如果一个题目要求我们求前K个代价最小的解(只是一个典型,不是所有题目都这样)
假设我们现在有一个状态在
已经要记录到答案里面的代价是(我喜欢用这个)
我们发现如果爆搜的话状态会是乱的对不对,肯定会使搜索搜到太多
而如果直接把状态按照排序的话不能保证答案就会正确(当然,不然就去贪心去)
所以我们引进一个估价函数
当然要求一般是可以预处理出一个状态到答案状态的最优解
回到前面讲到的当前状态
如果我们把与并列的所有状态按排序呢?
既不影响答案的正确性,又可以减少坏状态的转移
(因为题目要求是K个最优状态,而这样待决策状态会有序且跑完K个就可以结束,所以会变快)

好吧,还有点蒙对不对,那我们看例题

例题

洛谷P2901 [USACO08MAR]牛慢跑Cow Jogging
好像其他很多都有,但是是权限。。。

题目简述

要求我们求出从起点n到终点1的最短K条路径的长度
(只能从编号大的点往编号小的点走&边有边权)

很裸对吧?

  1. 预处理估价函数

先跑一遍反向边的预处理出每个点到1的最短路作为估价函数

  1. 直接跑(这里用实现)

从n号点开始,用堆来代替队列(实现上面所讲的排序)
这时候先到1节点的肯定答案更优(也就是路径更短)
原因很简单吧:估价函数保证答案合法,而排序之后答案有序
搜到K个到达1节点的路径就可以结束,快的飞起。。。

放个代码?

好不容易写一次注释

  1. #include<bits/stdc++.h>
  2. #define lst long long
  3. #define ldb double
  4. #define N 1050
  5. #define M 10050
  6. #define qw ljl[i].to
  7. using namespace std;
  8. const lst Inf=1e15;
  9. int read()
  10. {
  11. int s=0,m=0;char ch=getchar();
  12. while(!isdigit(ch)){if(ch=='-')m=1;ch=getchar();}
  13. while( isdigit(ch))s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
  14. return m?-s:s;
  15. }
  16. int n,m,K,Done;
  17. bool in[N];
  18. lst dis[N];
  19. queue<int> Q;
  20. int hd[N],cnt;
  21. struct EDGE{int to,nxt,v;}ljl[M<<1];
  22. void Add(int p,int q,int o){ljl[++cnt]=(EDGE){q,hd[p],o},hd[p]=cnt;}
  23. void SPFA()
  24. {
  25. for(int i=2;i<=n;++i)dis[i]=Inf;
  26. while(!Q.empty())Q.pop();
  27. Q.push(1),dis[1]=0,in[1]=true;
  28. while(!Q.empty())
  29. {
  30. int now=Q.front();Q.pop(),in[now]=false;
  31. for(int i=hd[now];i;i=ljl[i].nxt)
  32. if(qw>now&&dis[qw]>dis[now]+ljl[i].v)
  33. {
  34. dis[qw]=dis[now]+ljl[i].v;
  35. if(!in[qw])in[qw]=true,Q.push(qw);
  36. }
  37. }
  38. }
  39. //h[i]=g[i]+f[i]---->ans[i]=D+dis[i]
  40. struct NODE{
  41. lst D;int id;
  42. bool operator<(const NODE &X) const
  43. {
  44. return D+dis[id]>X.D+dis[X.id];
  45. }
  46. };priority_queue<NODE> H;
  47. void A_star_Bfs()
  48. {
  49. while(!H.empty())H.pop();
  50. H.push((NODE){0,n});
  51. while(!H.empty())
  52. {
  53. NODE temp=H.top();
  54. int now=temp.id;H.pop();
  55. if(now==1)
  56. {
  57. printf("%lld\n",temp.D);
  58. if(++Done==K)return;continue;
  59. }
  60. for(int i=hd[now];i;i=ljl[i].nxt)
  61. if(qw<now)H.push((NODE){temp.D+ljl[i].v,qw});
  62. }while(Done<K)++Done,puts("-1");
  63. }
  64. int main()
  65. {
  66. n=read(),m=read(),K=read();
  67. for(int i=1;i<=m;++i)
  68. {
  69. int p=read(),q=read(),o=read();
  70. Add(p,q,o),Add(q,p,o);
  71. }
  72. SPFA(),A_star_Bfs();
  73. return 0;
  74. }
  75. /************
  76. 1.A*算法在人工智能中是一种典型的启发式搜索算法
  77. 启发中的估价是用估价函数表示的:
  78. h(n)=f(n)+g(n)
  79. 其中f(n)是节点n的估价函数
  80. g(n)表示实际状态空间中从初始节点到n节点的实际代价
  81. h(n)是从n到目标节点最佳路径的估计代价。
  82. 另外定义h'(n)为n到目标节点最佳路径的实际值。
  83. 如果h'(n)≥h(n)则如果存在从初始状态走到目标状态的最小代价的解
  84. 那么用该估价函数搜索的算法就叫A*算法。
  85. 2.第K最短路的算法
  86. 我们设源点为s,终点为t,我们设状态f(i)的g(i)为从s走到节点i的实际
  87. 距离,h(i)为从节点i到t的最短距离,从而满足A*算法的要求,
  88. 当第K次走到f(n-1)时表示此时的g(n-1)为第K最短路长度。
  89. 3.这里是kuai的xzy的。。。别怪我。。。
  90. *************/

总结

暂时就将这么多吧
主要是看到网上没有写的那么通俗的搜索
就想自己总结一下(其实也不通俗。。。
撤撤撤溜了溜了_

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注