中国国家住房和城乡建设部网站首页,ui网页界面设计素材,wordpress小说网站模板,科研平台网站建设计划1 A*算法 A*算法在人工智能中是一种典型的启发式搜索算法#xff0c;启发中的估价是用估价函数表示的#xff1a; 其中f(n)是节点n的估价函数#xff0c;g(n)表示实际状态空间中从初始节点到n节点的实际代价#xff0c;h(n)是从n到目标节点最佳路径的估计代价。另外定义h(n… 1 A*算法 A*算法在人工智能中是一种典型的启发式搜索算法启发中的估价是用估价函数表示的 其中f(n)是节点n的估价函数g(n)表示实际状态空间中从初始节点到n节点的实际代价h(n)是从n到目标节点最佳路径的估计代价。另外定义h(n)为n到目标节点最佳路径的实际值。如果h(n)≥h(n)则如果存在从初始状态走到目标状态的最小代价的解那么用该估价函数搜索的算法就叫A*算法。 2 第K最短路的算法 我们设源点为s终点为t我们设状态f(i)的g(i)为从s走到节点i的实际距离h(i)为从节点i到t的最短距离从而满足A*算法的要求当第K次走到f(n-1)时表示此时的g(n-1)为第K最短路长度。C代码如下 CDOJ找的一道例题模板题这里面用到SPFA算法这是中国人创造的用于求单源最短路的一种算法关于SFPA时间复杂度的问题不确定性有时很大有时很小emmmm,貌似外国人不太认可 Time Limit: 10000 MS Memory Limit: 256 MB Submit Status 6·1即将来临游乐园推出了新的主题活动雨过天晴帆宝和乐爷童心未泯准备一探究竟。 兴奋的他们一入园便和孩子们打成一片不知不觉便走散了。 当他们意识到的时候只能通过手机来确认对方的位置。 他们当然想尽快找到对方然而由于孩子们实在是太多只能选择距离稍远的但是游客稀少的路会合。 帆宝希望找到第kk短的路径这条路径是他认为的幸运路径。 帆宝迫切地想知道该条路径的长度而乐于助人的你也一定会帮助她的。 Input 第一行三个整数n,m,kn,m,k分别表示游乐园的景点数目、景点之间的道路数目以及路径长度从小到大排列时希望选择的序号。 第二行两个整数S,TS,T分别表示帆宝和乐爷所在景点的编号。 接下来mm行每行三个整数u,v,wu,v,w表示编号为uu和vv的景点之间有一条长度为ww的单向通路。 1≤n≤1000,0≤m≤100000,1≤k≤1000,1≤S,T,u,v≤N,1≤w≤1001≤n≤1000,0≤m≤100000,1≤k≤1000,1≤S,T,u,v≤N,1≤w≤100 Output 第一行一个整数xx表示所选路径的长度 无解输出−1−1 Sample input and output Sample InputSample Output 3 3 2
1 2
1 2 2
1 3 4
3 2 15 题意给你起点终点以及要求的第K短路 题解首先将有向图以终点T为起点计算出T到每一个边的最短距离(到第i条边dis[i]) 然后建立一个优先队列从优先队列中弹出f(p)最小的点p,如果p就是T,则T的次数加一。如果当前次数等于K则当前路即为地K小 的路否则便利每一个p 所连的边将其扩张出的到p临接点的信息加入到优先队列中 AC代码 1 #include bits/stdc.h2 #define INF 0x3f3f3f3f3 using namespace std;4 const int AX 1e566;5 const int MAXN 1e366;6 int n,m,k;7 int s,t;8 int tot;9 int retot;10 struct edge{11 int to,w;12 int next1;13 }G[AX],RG[AX];14 15 struct Node{16 int v;17 int f,h,g;18 bool operator (const Node a) const{ return fa.f? ga.g : fa.f; }19 };20 21 22 int dis[MAXN];23 int head[MAXN];24 int rehead[AX];25 int vis[MAXN];26 27 void add_edge(int u,int v,int c)28 {29 G[tot].tov;30 G[tot].wc;31 G[tot].next1head[u];32 head[u]tot;33 34 RG[retot].tou;35 RG[retot].wc;36 RG[retot].next1rehead[v];37 rehead[v]retot;38 }39 void SPFA()40 {41 for(int i1;in;i) dis[i]INF;42 dis[t]0;43 queueint Q;44 Q.push(t);45 while(!Q.empty())46 {47 int uQ.front();48 Q.pop();49 for(int irehead[u];i!-1;iRG[i].next1)50 {51 int vRG[i].to ;52 int wRG[i].w ;53 if(dis[v]dis[u]w)54 {55 dis[v]dis[u]w;56 Q.push(v);57 }58 }59 } 60 }61 62 int Astar(Node a)63 {64 memset(vis,0,sizeof(vis));65 if(dis[s]INF) return -1;//如果没有与S相连的点 66 if(st) k;67 priority_queueNode Q;68 Q.push(a);69 while(!Q.empty())70 {71 Node tmpQ.top();72 Q.pop();73 int vtmp.v;74 vis[v];75 if(vis[t]k) return tmp.g;76 for(int ihead[v];i!-1;iG[i].next1)77 {78 Node p;79 p.vG[i].to;80 p.hdis[G[i].to];81 p.gtmp.gG[i].w;82 p.fp.gp.h;83 Q.push(p);84 }85 }86 return -1;87 }88 89 int main()90 {91 tot0;92 retot0;93 memset(head,-1,sizeof head);94 memset(rehead,-1,sizeof rehead);95 scanf(%d%d%d,n,m,k);96 scanf(%d%d,s,t);97 int x,y,w;98 for(int i0;im;i)99 {
100 scanf(%d%d%d,x,y,w);
101 add_edge(x,y,w);
102 }
103 SPFA();
104 Node a;
105 a.vs;
106 a.g0;
107 a.hdis[s];
108 a.fa.ga.h;
109 int gAstar(a);
110 printf(%d\n,g);
111 return 0 ;
112 } View Code 后面我还会更新出 关于启发式搜索的讲解以及Dijkstra,,SPFA,Folyd这三种关于不同最短路问题讲解及例题分析。 越努力越幸运 加油 转载于:https://www.cnblogs.com/songorz/p/9386760.html
