单源最短路径贪心算法
㈠ 数学最短路径问题最方便的解法是什么
用于解决最短路径问题的算法被称做“最短路径算法” ，有时被简称作“路径算法” 。最常用 的路径算法有： Dijkstra 算法、 A*算法、 SPFA 算法、 Bellman-Ford 算法和 Floyd-Warshall 算法， 本文主要介绍其中的三种。 最短路径问题是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两 结点之间的最短路径。 算法具体的形式包括： 确定起点的最短路径问题：即已知起始结点，求最短路径的问题。 确定终点的最短路径问题：与确定起点的问题相反，该问题是已知终结结点，求最短路径的 问题。 在无向图中该问题与确定起点的问题完全等同， 在有向图中该问题等同于把所有路径 方向反转的确定起点的问题。 确定起点终点的最短路径问题：即已知起点和终点，求两结点之间的最短路径。 全局最短路径问题：求图中所有的最短路径。 Floyd 求多源、无负权边的最短路。用矩阵记录图。时效性较差，时间复杂度 O(V^3)。 Floyd-Warshall 算法（Floyd-Warshall algorithm）是解决任意两点间的最短路径的一种算法， 可以正确处理有向图或负权的最短路径问题。 Floyd-Warshall 算法的时间复杂度为 O(N^3)，空间复杂度为 O(N^2)。 Floyd-Warshall 的原理是动态规划： 设 Di,j,k 为从 i 到 j 的只以(1..k)集合中的节点为中间节点的最短路径的长度。 若最短路径经过点 k，则 Di,j,k = Di,k,k-1 + Dk,j,k-1； 若最短路径不经过点 k，则 Di,j,k = Di,j,k-1。 因此，Di,j,k = min(Di,k,k-1 + Dk,j,k-1 , Di,j,k-1)。 在实际算法中，为了节约空间，可以直接在原来空间上进行迭代，这样空间可降至二维。 Floyd-Warshall 算法的描述如下： 1.for k ← 1 to n do 2.for i ← 1 to n do 3.for j ← 1 to n do 4.if (Di,k + Dk,j<Di,j) then 5.Di,j ← Di,k + Dk,j; 其中 Di,j 表示由点 i 到点 j 的代价，当 Di,j 为∞表示两点之间没有任何连接。 Dijkstra 求单源、无负权的最短路。时效性较好，时间复杂度为 O（V*V+E） 。 源点可达的话，O（V*lgV+E*lgV）=>O（E*lgV） 。 当是稀疏图的情况时，此时 E=V*V/lgV，所以算法的时间复杂度可为 O（V^2） 。若是斐波那 契堆作优先队列的话，算法时间复杂度，则为 O（V*lgV + E） 。 Bellman-Ford 求单源最短路，可以判断有无负权回路（若有，则不存在最短路） ，时效性较好，时间复杂 度 O（VE） 。 Bellman-Ford 算法是求解单源最短路径问题的一种算法。 单源点的最短路径问题是指：给定一个加权有向图 G 和源点 s，对于图 G 中的任意一点 v， 求从 s 到 v 的最短路径。 与 Dijkstra 算法不同的是，在 Bellman-Ford 算法中，边的权值可以为负数。设想从我们可以 从图中找到一个环路（即从 v 出发，经过若干个点之后又回到 v）且这个环路中所有边的权 值之和为负。那么通过这个环路，环路中任意两点的最短路径就可以无穷小下去。如果不处 理这个负环路，程序就会永远运行下去。而 Bellman-Ford 算法具有分辨这种负环路的能力。 SPFA是 Bellman-Ford 的队列优化，时效性相对好，时间复杂度 O（kE）（k<<V） 。 。 与 Bellman-ford 算法类似， SPFA 算法采用一系列的松弛操作以得到从某一个节点出发到达图 中其它所有节点的最短路径。所不同的是，SPFA 算法通过维护一个队列，使得一个节点的 当前最短路径被更新之后没有必要立刻去更新其他的节点， 从而大大减少了重复的操作次数。 SPFA 算法可以用于存在负数边权的图，这与 dijkstra 算法是不同的。 与 Dijkstra 算法与 Bellman-ford 算法都不同，SPFA 的算法时间效率是不稳定的，即它对于不 同的图所需要的时间有很大的差别。 在最好情形下，每一个节点都只入队一次，则算法实际上变为广度优先遍历，其时间复杂度 仅为 O(E)。另一方面，存在这样的例子，使得每一个节点都被入队(V-1)次，此时算法退化为 Bellman-ford 算法，其时间复杂度为 O(VE)。 SPFA 算法在负边权图上可以完全取代 Bellman-ford 算法， 另外在稀疏图中也表现良好。 但是 在非负边权图中，为了避免最坏情况的出现，通常使用效率更加稳定的 Dijkstra 算法，以及 它的使用堆优化的版本。通常的 SPFA 算法在一类网格图中的表现不尽如人意。
㈡ 各边的权值为0~N-1之间的整数,N为一非负整数。修改Dijkstra算法使其能在O(Nn
摘要 您好，，给定带权有向图G =(V,E)，其中每条边的权是非负实数。另外，还给定V中的一个顶点，称为源。现在要计算从源到所有其他各顶点的最短路长度。这里路的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。
㈢ 贪婪启发式和贪婪算法的区别是什么
马踏棋盘的问题很早就有人提出，且早在1823年，J.C.Warnsdorff就提出了一个有名的算法。在每个结点对其子结点进行选取时，优先选择‘出口’最小的进行搜索，‘出口’的意思是在这些子结点中它们的可行子结点的个数，也就是‘孙子’结点越少的越优先跳，为什么要这样选取，这是一种局部调整最优的做法，如果优先选择出口多的子结点，那出口少的子结点就会越来越多，很可能出现‘死’结点（顾名思义就是没有出口又没有跳过的结点），这样对下面的搜索纯粹是徒劳，这样会浪费很多无用的时间，反过来如果每次都优先选择出口少的结点跳，那出口少的结点就会越来越少，这样跳成功的机会就更大一些。这种算法称为为贪心算法，也叫贪婪算法或启发式算法，它对整个求解过程的局部做最优调整，它只适用于求较优解或者部分解，而不能求最优解。这样的调整方法叫贪心策略，至于什么问题需要什么样的贪心策略是不确定的，具体问题具体分析。实验可以证明马遍历问题在运用到了上面的贪心策略之后求解速率有非常明显的提高，如果只要求出一个解甚至不用回溯就可以完成，因为在这个算法提出的时候世界上还没有计算机，这种方法完全可以用手工求出解来，其效率可想而知。
贪心算法当然也有正确的时候。求最小生成树的Prim算法和Kruskal算法都是漂亮的贪心算法。
贪心法的应用算法有Dijkstra的单源最短路径和Chvatal的贪心集合覆盖启发式
所以需要说明的是，贪心算法可以与随机化算法一起使用，具体的例子就不再多举了。其实很多的智能算法（也叫启发式算法），本质上就是贪心算法和随机化算法结合——这样的算法结果虽然也是局部最优解，但是比单纯的贪心算法更靠近了最优解。例如遗传算法，模拟退火算法。
㈣ 单源最短路径可以用贪心算法得到最优解吗
可以。对于权值大于等于零的有相或无相图，可以使用基于贪心思想的Dijkstra算法求解单源最短路径问题。
㈤ dijakstra算法和分支限算法在解决单源最短路径问题的异同
记dijakstra算法为D算法
D算法为贪心算法,每一步的选择为当前步的最优,复杂度为O(n*n) (又叫爬山法)
分支限界算法,每一步的扩散为当前耗散度的最优,复杂度为(没算)
都是A算法的极端情况
(说错了哈,下面我的文字中的的分支限界算法实际上是在说动态规划法,我查了一下书,动态规划法是对分支限界法的改进,分支限界法不属于A算法(启发式搜索算法),但是这时用动态规划法和D算法比较也是有可比性的,而直接用分支限界算法和D算法比较也是可以的)
关键词:耗散度 评估函数
即:对当前优先搜索方向的判断标准为,有可能的最优解
而最优解可以用一个评估函数来做,即已经有的耗散度加上以后有可能的耗度
A算法就是把两个耗散度加在一起,作为当前状态的搜索搜索方向;
但是对以后的耗散度的评估是麻烦的,D算法就是把当前有的路的最短的作为,以后耗散度的评估.
分支限界算法就是只以以前的耗散度为评估函数
你给的两个算法当然是A算法的特例
你还可以参考一下 A*算法 修正的A*算法,相信对你的编程水平有帮助
参考:
队列式分支限界法的搜索解空间树的方式类似于解空间树的宽度优先搜索，不同的是队列式分支限界法不搜索以不可行结点（已经被判定不能导致可行解或不能导致最优解的结点）为根的子树。按照规则，这样的结点不被列入活结点表。
优先队列式分支限界法的搜索方式是根据活结点的优先级确定下一个扩展结点。结点的优先级常用一个与该结点有关的数值p来表示。最大优先队列规定p值较大的结点点的优先级较高。在算法实现时通常用一个最大堆来实现最大优先队列，体现最大效益优先的原则。类似地，最小优先队列规定p值较小的结点的优先级较高。在算法实现时，常用一个最小堆来实现，体现最小优先的原则。采用优先队列式分支定界算法解决具体问题时，应根据问题的特点选用最大优先或最小优先队列，确定各个结点点的p值。
㈥ 关于Dijkstra算法
楼上正解，你找个图自己用此算法实践一下就知道了，从A点出发，发现离A最近的点是B点，那么我们就已经认为A到B的最短距离就是AB了，如果有负数，就指不定冒出个C点,AC+CB<AB;或者冒出个DE为很大的负值，AC+CD+DE+EF+FB<AB;等等诸如此类的情况。
简单说来，你驾车从家出发到某地沿某条路只需经过一个收费站，但是远在外省某地有个站不但不收你的费，你去了还会给你个千八百万的欢迎光临费，你能说你直接沿着这条路去某地是最省费用的？不计时间成本，绕到外省那个给你钱的地方，再绕回到你的目的地，还能赚钱呢。
而且一般权值为负的图研究也比较少。有些带负权的图，某些点间还没有最小距离呢。中间出个带某条负权很大的边的环圈，绕此一圈所经过的距离反而减少了，那就一直在此圈上绕啊绕啊绕到负的足够大溢出为止。
当然考虑各种自己随便假设出来的变种问题也是很有趣的。比如说边带有多个权值对应多次经过改变的消费，上面的问题有可能变成有解的。话说那个站会后悔，第二次经过它会收回100万，第三次经过收回250万，这样的话你只需要经过一次就够了，问题也是有解的。再比如说对于多权重图，从A点出发经过B点到达C点的最短路线，就不是简单的AB最短路线+BC最短路线了，说不定两者有重合边，第二次经过来个天价就傻眼了。其实这种图貌似应该可以转化成单权重图的，我直觉估计啊，刚随便想出这个问题，还没去思考这个问题的解^_^
㈦ 求单源最短路径的程序设计（要贪心算法的哟）
迪杰斯特拉算法
// dijsktra.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#define N 12
#include <iostream>
using namespace std;
const static int soure[N][N] =
{
/*
*这里填邻接矩阵
*/
};
int min(int arr[N],bool bj[])
{
int tmp = 999;
int temp = 0;
for(int i=0; i<N; i++)
{
if((arr[i]<tmp)&&(bj[i]==true))
{
tmp = arr[i];
temp = i;
}
}
return temp;
}
class dijsktra
{
private:
int dist[N][N];
int path[N][N];
int final[N][N];
bool flag[N];
public:
void Doing()
{
for(int i=0; i<N; i++)
{
int temp = 0;
for(int j=0; j<N; j++)
{
flag[j] = true;
}
for(int j=0; j<N; j++)
{
dist[i][j] = soure[i][j];
path[i][j] = i;
}
flag[i] = false;
temp = min(dist[i],flag);
flag[temp] = false;
for(int j=1; j<N; j++)
{
for(int k=0; k<N; k++)
{
if((flag[k] == true)&&((soure[temp][k]+dist[i][temp])<dist[i][k]))
{
dist[i][k] = soure[temp][k]+dist[i][temp];
path[i][k] = temp;
}
}
temp = min(dist[i],flag);
flag[temp] = false;
}
}
}
void print()
{
for(int i=0; i<N; i++)
{
for(int j=0; j<N; j++)
{
cout<<dist[i][j]<<","<<path[i][j]<<" ";
}
cout<<endl;
}
}
void l_print()
{
int i,j;
cout<<"请输入i,j的值:";
cin>>i>>j;
cout<<"最短路径长度为："<<dist[i][j]<<endl;
cout<<"路径为";
int temp = j;
while(path[i][temp]!=i)
{
cout<<temp<<"<-";
temp = path[i][temp];
}
cout<<temp<<"<-";
cout<<i<<endl;
}
};
int _tmain(int argc, _TCHAR* argv[])
{
dijsktra test;
test.Doing();
test.print();
test.l_print();
system("pause");
return 0;
}
㈧ 用动态规划解决矩阵链乘法问题时，最优子结构问题是什么
1、两种重要算法思想： 动态规划，贪心算法
2、动态规划：
基本原理：动态规划英文名dynamic programming。其中pogramming指的是表格法，而非编写计算机程序。因此，可以初步得出动态规划的基本思想：将一个具有最优子结构性质的问题分成若干个子问题，在求解过程中，记录下子问题的结果，存储在一个表格中，使得公共的子问题只需要计算一次。书中给出的基本原理：动态规划将问题分成若干个相互重叠的子问题，递归的求解子问题，保存子问题的解，再将它们的解组合起来，求出原问题的解。
从基本原理中可以看出动态规划需要满足两个条件，最优子结构和子问题重叠。
最优子结构：书中定义：问题的最优解由相关子问题的最优解组合而成，一个问题的最优解包含其子问题的最优解。典型的有背包问题和钢条切割我问题。所谓子问题就是一中组合，将一个问题分成许多子问题的集合。某个子问题转化为问题时，所需要的代价是固定的。
一般这类问题的解题过程：（自己总结）
画出子问题图（类似于逆拓扑排序的图，子问题必须在问题前面完成）
用数学表达式构建出问题的最优解和子问题最优解之间的代数表达式
通常采用自底向上的方法进行递归地求解问题的解，自底下上的含义是从最小的子问题求起。
保存每一步求出的子问题的最优解
利用计算出的信息构造一个最优解
3、贪心算法：
基本原理：从初始状态出发，每步都经过贪心选择，最终得到问题的最优解。
含义： 将每一步都看成是当前最佳的选择，做到局部最优化，直到无法选择为止。寄希望于局部最优的选择能够导致全局最优解。
两个实例：最小生成树算法和单源最短路径算法，以及集合覆盖问题的贪心启发式算法。
prim算法：将集合A看成是一棵树，每次选择剩余的节点中与这棵树形成的边的权值最小的点加入到集合A中形成新的树，循坏调用该过程，知道所有的点都已经放入到集合A中。初始时随机选择一个节点放入到集合A中。
kruskal算法：在所有连接森林中两颗不同树的边里面，找到权重最小的边（u，v），并将其加入到集合A中，循环调用该过程，直到所有的点已经放入到集合A中
贪心选择：当进行选择时，我们直接作在当前问题看来是最优的选择，而不必考虑子问题的解。这与动态规划不同，动态规划当前问题依赖于较小的子问题。而贪心算法中做当前问题最优选择，这样每步之后只需要做一个子问题的解。
也必须满足最优子结构的性质，即一个问题的最优解包含其子问题的最优解。
那么，如何区分什么时候使用动态规划，什么时候使用贪心算法呢？
典型的两个问题，0-1背包和分数背包。两者都具有最优子结构性质，但是贪心算法只能用来求分数背包的问题，而不能用来求0-1背包的问题。即只有分数背包具有贪心选择性。
我得总结（不一定对）：具有贪心选择性的一类问题是：每次做选择时只有性能不同，而代价是一样的。那么这样每次的选择都是最好的，最终会得到最好的结果。
哈夫曼编码也使用贪心选择算法。每次选择待编码的字符都选择在剩余的字符中出现次数最多的
㈨ 算法分析与设计这门课程第四章贪心算法的知识点有哪些
算法分析与设计这门课第四章贪心算法的知识点包含章节导引,第一节活动安排问题,第二节贪心算法基本要素,第三节最优装载,第四节单源最短路径,第五节多机调度问题,课后练习,。
㈩ 贪心算法中的matlab算法怎么做
1.数论算法
求两数的最大公约数
function gcd(a,b:integer):integer;
begin
if b=0 then gcd:=a
else gcd:=gcd (b,a mod b);
end ;
求两数的最小公倍数
function lcm(a,b:integer):integer;
begin
if a< b then swap(a,b);
lcm:=a;
while lcm mod b >0 do inc(lcm,a);
end;
素数的求法
A.小范围内判断一个数是否为质数：
function prime (n: integer): Boolean;
var I: integer;
begin
for I:=2 to trunc(sqrt(n)) do
if n mod I=0 then
begin
prime:=false; exit;
end;
prime:=true;
end;
B.判断longint范围内的数是否为素数（包含求50000以内的素数表）：
procere getprime;
var
i,j:longint;
p:array[1..50000] of boolean;
begin
fillchar(p,sizeof(p),true);
p[1]:=false;
i:=2;
while i< 50000 do
begin
if p then
begin
j:=i*2;
while j< 50000 do
begin
p[j]:=false;
inc(j,i);
end;
end;
inc(i);
end;
l:=0;
for i:=1 to 50000 do
if p then
begin
inc(l);
pr[l]:=i;
end;
end;{getprime}
function prime(x:longint):integer;
var i:integer;
begin
prime:=false;
for i:=1 to l do
if pr >=x then break
else if x mod pr=0 then exit;
prime:=true;
end;{prime}
2．
3．
4.求最小生成树
A.Prim算法：
procere prim(v0:integer);
var
lowcost,closest:array[1..maxn] of integer;
i,j,k,min:integer;
begin
for i:=1 to n do
begin
lowcost:=cost[v0,i];
closest:=v0;
end;
for i:=1 to n-1 do
begin
{寻找离生成树最近的未加入顶点k}
min:=maxlongint;
for j:=1 to n do
if (lowcost[j]< min) and (lowcost[j]< >0) then
begin
min:=lowcost[j];
k:=j;
end;
lowcost[k]:=0; {将顶点k加入生成树}
{生成树中增加一条新的边k到closest[k]}
{修正各点的lowcost和closest值}
for j:=1 to n do
if cost[k,j]< lwocost[j] then
begin
lowcost[j]:=cost[k,j];
closest[j]:=k;
end;
end;
end;{prim}
B.Kruskal算法：(贪心)
按权值递增顺序删去图中的边，若不形成回路则将此边加入最小生成树。
function find(v:integer):integer; {返回顶点v所在的集合}
var i:integer;
begin
i:=1;
while (i< =n) and (not v in vset) do inc(i);
if i< =n then find:=i
else find:=0;
end;
procere kruskal;
var
tot,i,j:integer;
begin
for i:=1 to n do vset:=;{初始化定义n个集合，第I个集合包含一个元素I}
p:=n-1; q:=1; tot:=0; {p为尚待加入的边数，q为边集指针}
sort;
{对所有边按权值递增排序，存于e[I]中，e[I].v1与e[I].v2为边I所连接的两个顶点的序号，e[I].len为第I条边的长度}
while p >0 do
begin
i:=find(e[q].v1);j:=find(e[q].v2);
if i< >j then
begin
inc(tot,e[q].len);
vset:=vset+vset[j];vset[j]:=[];
dec(p);
end;
inc(q);
end;
writeln(tot);
end;
5.最短路径
A.标号法求解单源点最短路径：
var
a:array[1..maxn,1..maxn] of integer;
b:array[1..maxn] of integer; {b指顶点i到源点的最短路径}
mark:array[1..maxn] of boolean;
procere bhf;
var
best,best_j:integer;
begin
fillchar(mark,sizeof(mark),false);
mark[1]:=true; b[1]:=0;{1为源点}
repeat
best:=0;
for i:=1 to n do
If mark then {对每一个已计算出最短路径的点}
for j:=1 to n do
if (not mark[j]) and (a[i,j] >0) then
if (best=0) or (b+a[i,j]< best) then
begin
best:=b+a[i,j]; best_j:=j;
end;
if best >0 then
begin
b[best_j]:=best；mark[best_j]:=true;
end;
until best=0;
end;{bhf}
B.Floyed算法求解所有顶点对之间的最短路径：
procere floyed;
begin
for I:=1 to n do
for j:=1 to n do
if a[I,j] >0 then p[I,j]:=I else p[I,j]:=0;
{p[I,j]表示I到j的最短路径上j的前驱结点}
for k:=1 to n do {枚举中间结点}
for i:=1 to n do
for j:=1 to n do
if a[i,k]+a[j,k]< a[i,j] then
begin
a[i,j]:=a[i,k]+a[k,j];
p[I,j]:=p[k,j];
end;
end;
C. Dijkstra 算法：
类似标号法，本质为贪心算法。
var
a:array[1..maxn,1..maxn] of integer;
b,pre:array[1..maxn] of integer; {pre指最短路径上I的前驱结点}
mark:array[1..maxn] of boolean;
procere dijkstra(v0:integer);
begin
fillchar(mark,sizeof(mark),false);
for i:=1 to n do
begin
d:=a[v0,i];
if d< >0 then pre:=v0 else pre:=0;
end;
mark[v0]:=true;
repeat {每循环一次加入一个离1集合最近的结点并调整其他结点的参数}
min:=maxint; u:=0; {u记录离1集合最近的结点}
for i:=1 to n do
if (not mark) and (d< min) then
begin
u:=i; min:=d;
end;
if u< >0 then
begin
mark:=true;
for i:=1 to n do
if (not mark) and (a[u,i]+d< d) then
begin
d:=a[u,i]+d;
pre:=u;
end;
end;
until u=0;
end;
D.计算图的传递闭包
Procere Longlink;
Var
T:array[1..maxn,1..maxn] of boolean;
Begin
Fillchar(t,sizeof(t),false);
For k:=1 to n do
For I:=1 to n do
For j:=1 to n do
T[I,j]:=t[I,j] or (t[I,k] and t[k,j]);
End;