广度优先算法
纪念一下本站的第一篇文章，希望之后可以定期坚持写些自己感兴趣的东西，不局限于算法。
Dijkstra算法
本质基于广度搜索
init：创建一个队列 ,优化可以用优先队列,v平方的时间复杂度优化到vlogv的复杂度 优先列队中放的数据结构为 pair<离起点距离，点index> dist[i] 表示当前i点到起点的距离
- 将点的孩子结点，未访问过的，全放入优先队列 （距离，点index）
- 每次找到距离起点最近距离的点，优先队列队首 (原因:如果先访问远的点，后续更新还要更新该点能到达的点),pop()
- 遍历当前选中的点能到的，(设为j，当前点为i)，(虽然未访问过，但是dist值可能被提前更新)，更新dist值，dist[j]=min(dist[j].dist[i]+G[i][j])，放入队列
- 重复 2，3
inline void Dijkstra() {
REP(i, 1, n) dis[i] = 2147483647;
dis[s] = 0;
Q.push(P(0, s));
while (!Q.empty()) {
long long u = Q.top().second;//取出dis最小的点
Q.pop();//弹出
if (vis[u]) continue;
vis[u] = 1;
for (long long e = head[u]; e; e = nxt[e])
if (dis[to[e]]>dis[u] + val[e]) {
dis[to[e]] = dis[u] + val[e];
Q.push(P(dis[to[e]], to[e]));//插入
}
}
return;
}
Greed-Best-First-Search算法
也是基于广度搜索 ，但是这里没有权重值
她总是尝试向离目标点更近的方向探索
在只能上下左右移动的情况下，我们用曼哈顿距离来进行判断
（x，y）到（x1，y1）的曼哈顿距离为 abs(x-x1)+abs(y-y1)
算法流程如下：
说明：起始节点记作S，目标节点记作E，对于任意节点G，从当前节点G到目标节点E的曼哈顿距离记作MG，优先队列openList中数据为(G,MG)（节点，当前节点到目标节点E的曼哈顿距离）。
- 将起始节点S放入openList，openList是一个优先队列，曼哈顿距离越小的节点，优先级越高。
- 判断openList是否为空，如果为空，搜索失败，目标节点E不可达；如果不为空，从openList中拿出优先级最高的节点G;
- 遍历节点G的上下左右四个相邻节点N1-N4，如果N在openList或closeList中，忽略节点N；否则，令N的父节点为G，计算N到E的曼哈顿距离MN，将(N,MN)放入openList。
- 判断节点G是不是目标节点E，如果是，搜索成功，获取节点G的父节点，并递归这一过程（继续获得父节点的父节点），直至找到初始节点S，从而获得从G到S的一条路径；否则，重复步骤2。
A星算法
A星算法与最好优先贪婪算法一样都通过计算一个值来判断探索的方向。对于节点N，计算公式如下：
F(N)=G(N)+H(N)
G（N）就是dijkstra中的dist值，距离起点的距离，而H值是当前结点到目标结点的曼哈顿距离，因此，当节点间距离移动小号非常笑得时候，G对F的影响微乎其微，比如权值都为1的时候，就退化为最好优先贪婪算法，当节点间移动小号非常大以至于H对F的影响微乎其微时，A星算法就退化为Dijkstra算法
算法流程如下：
说明：起始节点记作S，目标节点记作E，对于任意节点P，从S到当前节点P的总移动消耗记作GP，节点P到目标E的曼哈顿距离记作HP，从节点P到相邻节点N的移动消耗记作DPN，用于优先级排序的值F(N)记作FP。
- 选择起始节点S和目标节点E，将(S,0)（节点，节点F(N)值）放入openList，openList是一个优先队列，节点F(N)值越小，优先级越高。
- 判断openList是否为空，若为空，则搜索失败，目标节点不可达；否则，取出openList中优先级最高的节点P;
- 遍历P的上下左右四个相邻接点N1-N4，对每个节点N，如果N已经在closeList中，忽略；否则有两种情况， 1)如果N不在openList中，令GN=GP+DPN，计算N到E的曼哈顿距离HN，令FN=GN+HN，令N的父节点为P，将(N,FN)放入openList； 2)如果N已经在openList中，计算GN1= GP+DPN，如果GN1小于GN，那么用新的GN1替换GN，重新计算FN，用新的(N,FN)替换openList中旧的(N,FN)，令N的父节点为P；如果GN1不小于GN，不作处理。
- 将节点P放入closeList中。判断节点P是不是目标节点E，如果是，搜索成功，获取节点P的父节点，并递归这一过程（继续获得父节点的父节点），直至找到初始节点S，从而获得从P到S的一条路径；否则，重复步骤2;
B星算法
在此把这个算法称作B star 寻路算法（Branch Star 分支寻路算法，且与A star对应），本算法适用于游戏中怪物的自动寻路，其效率远远超过A star算法，经过测试，效率是普通A star算法的几十上百倍。
