<h1 id="dijlkstra">Dijlkstra算法</h1>
<blockquote>
Dijkstra算法是一种常见的计算正权图上的单源最短路的算法，能同时用在有向图和无向图上。
</blockquote>
<a href="/post/Algorithm/Dijkstra.html">&gt;Dijkstra算法的解释&lt;</a>
其以BFS为基础进行优化。
<h2 id="bfs">BFS算法</h2>
<blockquote>
宽度优先遍历算法，先从起点向周围拓展，再从拓展后的每个点向外拓展，如果某个节点已经访问过，则不再访问该节点。
</blockquote>
<blockquote>
由于每个节点只访问一次，并且按层逐层向外访问，因此第一次访问到终点时走过的路径就是最短路径。
</blockquote>
<blockquote>
可以用于无权图的最短路搜索。
</blockquote>
<blockquote>
通常使用循环和队列进行搜索。
</blockquote>
<blockquote>
<pre style="background-color:#fff">
</pre></blockquote>
queue<int> Q; 
bool visited[maxn]; 
memset(visited,flase,sizeof(visited));
Q.push(v); 
visited[v]=true; 
while(!Q.empty()){ 
int it=Q.top(); 
Q.pop();
<pre><code> //拓展到终点
 if(it==s){
 ...
 break;
 }

 ...//从it向外拓展到itn
 if(!visited[itn])
 Q.push(itn);
</code></pre>
}
<pre style="background-color:#fff">

## DFS算法

&gt; 深度优先遍历，从起点开始，沿着一条分支一直走到终点。

&gt; 与BFS不同，DFS的在搜索最短路的大多数情况下，是不如BFS的，它更多是用在状态的转移上。

&gt; 根据已有的状态向下一个状态进行转移。

&gt; 在较为复杂的迷宫中（牵扯到时间、方向等各种复杂状态）时，用DFS来传递参数会更有优势

&gt; 由于DFS强调的是状态的转移。因此，更多用递归来实现。

&gt; ``` cpp
void DFS(...){
 //不符合要求的拓展
 if(...)
 return;
 //达到叶节点
 if(...)
 return;
 ...//向下拓展到itn(n=1、2、……)
 DFS(it1);
 ...
 DFS(itn);
}
</pre>当图为有权图时，如果我们想要走最短的路径，就要优先走权值更小的路，这样才能走出最小的解（可证明）
因此，在BFS中，我们在队列中不应该选取先进队的节点，而应该走权值最小的节点。
将BFS的队列(queue)改成优先队列(priority_queue)即可。
然后每次拓展节点后，更新每个节点的权值(取最小)
最后终点的权值就是最小路的距离。
<h1 id="bellman-ford">Bellman-Ford算法</h1>
Dijkstra算法只适用于正权图上最短路，而Bellman-Ford还可计算副权存在时的最短路。
首先要明确：
<ul>
<li>
如果最短路存在，一定存在一个不含环的最短路。
</li>
<li>
最短路最多只经过(不含起点)n-1个节点，可以通过n-1轮松弛操作得到。
</li>
</ul>
<pre style="background-color:#fff">将起点权值设置为0，其他点权值设置为无穷大。

循环节点个数-1次

　　循环边的个数次(i)

　　　　对第i条边进行松弛操作

　　　　检测是否存在负权回路

　　　　　　存在

　　　　　　　返回false

　　　　　　不存在

　　　　　　　继续
</pre><h1 id="spfa">SPFA算法</h1>
Bellman-Ford算法虽然解决了负权路的问题，但是其效率过于底下，并不常使用。
而SPFA算法，是其高效率的替代方法。
其与无权图的BFS较为相近。
不同的是，visited数组记录的不是是否已经访问过，而是是否在队列Q中
每次松弛操作更新估计值(d[i])，如果i点不在队列中，则要把i点入队
如果有边入队的次数超过N次，则说明存在负环。
<h1 id="floyd">Floyd算法</h1>
如果需要求出每两点之间的最短路，则可以使用Floyd算法，这是一个非常简洁的算法
不断进行松弛操作，即可得到最短路径
<pre style="background-color:#fff">for(int k=0;k&lt;n;k++)
 for(int i=0;i&lt;n;i++)
 for(int j=0;j&lt;n;j++)
 d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
</pre>迭代加深搜索、A*、IDA*是三种相似并且很有用的算法。
他们是一种解题的思路，并没有具体的实现代码，在脑海中有这种思路，有可能会帮助我们获取解题的思路
<h1 id="heading">迭代加深搜索</h1>
迭代加深搜索是一种不断拓展搜索范围的搜索方式。
可以将其形象成一棵树，这棵树有无数层（深度无限深），每一层有无限个节点（无限广）
因此，无论是DFS还是BFS，都不能拓展一支，拓展一层。
而其答案可能就在第二层第二支上……
为了求解这种问题，有了迭代加深搜索。
顾名思义，迭代加深就是逐渐增加搜索的范围。
最初我们只搜索maxd的范围，当maxd内没有我们需要的答案时，我们将maxd+1，而后继续搜索。
<pre style="background-color:#fff">for(maxd=1;;maxd++)
 if(dfs(...))
 break;
</pre>埃及分数问题，是经典的迭代加深问题
在古埃及，人们使用单位分数的和（形如 1/a 的，a 是正整数）表示一切有理数。
如：<code>2/3 = 1/2 + 1/6</code>，但不允许 <code>2/3 = 1/3 + 1/3</code>，因为加数中有相同的。
首先，加数少的比加数多的好，其次，加数个数相同的，最小的分数越大越好。
首先BFS无法求解这个问题，我们不知道有几个加数；其次DFS也不能求解这个问题，我们不知道加数没有最小值（分母可以无限大）。
因此，我们需要使用迭代加深算法。先让每个加数都大于1/10，进行DFS，如果没有答案，再搜索每个加数都大于1/20……
很显然，每次maxd的增加，都导致了重复搜索，不过相比搜索总数指数级的增加，重复搜索的这部分可以忽略……
<h1 id="a">A*算法</h1>
A*算法，又称启发式搜索。
用公式表示为
<blockquote>
f(n)=g(n)+h(n)
</blockquote>
其中
<blockquote>
f(n)是初始点经由节点n到目标点的估价函数
</blockquote>
<blockquote>
g(n)是在状态空间中从初始节点到n节点的实际代价
</blockquote>
<blockquote>
h(n)是从n到目标结点的最佳路径的估计代价
</blockquote>
具体是什么意思呢，就是我们要优先选择一条我们估计最好的分支进行拓展，对于我们估计不是很好的分支进行剪枝。
由于最好只是我们的估计，因此，如果估计的不合理，可能会丢失最优解或者并没有有效提升效率。
与Dijkstra对比，我们可以发现，Dijkstra其实是简化的一种A*算法：
它与A*相比少了剪枝的部分，与BFS相比，多了估价的部分
<h1 id="ida">IDA*算法</h1>
将迭代加深的有上限的搜索和A算法的剪枝与估价结合，就得到了IDA算法
IDA*算法有以下优缺点：
<ul>
<li>优化了A*对空间的小号</li>
<li>在每一次迭代的过程中避免了判重</li>
<li>比普通的DFS相比更加明确目标，并能够有效剪枝</li>
<li>迭代加深会导致重复搜索内容</li>
</ul>

初窥Dijkstra算法、Bellman-Ford、SPFA算法、Floyd算法、迭代加深搜索、A*、IDA*

初窥Dijkstra算法、Bellman-Ford、SPFA算法、Floyd算法、迭代加深搜索、A、IDA