usch算法

1. vc环境 最短路径算法

单源最短路径算法---Dijkstra算法
转自:http://space.flash8.net/space/html/07/14107_itemid_400760.html

算法介绍
Dijkstra算法是由荷兰计算机科学家艾兹格·迪科斯彻发现的。算法解决的是有向图中最短路径问题。

举例来说，如果图中的顶点表示城市，而边上的权重表示着城市间开车行经的距离。 Dijkstra算法可以用来找到两个城市之间的最短路径。

Dijkstra 算法的输入包含了一个有权重的有向图G，以及G中的一个来源顶点S。我们以V表示G中所有顶点的集合。每一个图中的边，都是两个顶点所形成的有序元素对。 (u,v)表示从顶点u到v有路径相连。我们以E所有边的集合，而边的权重则由权重函数w: E → [0, ∞]定义。因此，w(u,v)就是从顶点u到顶点v的非负花费值(cost)。边的花费可以想象成两个顶点之间的距离。任两点间路径的花费值，就是该路径 上所有边的花费值总和。已知有V中有顶点s及t，Dijkstra算法可以找到s到t的最低花费路径(i.e. 最短路径)。这个算法也可以在一个图中，找到从一个顶点s到任何其他顶点的最短路径。

算法描述
这个算法是通过为每个顶点v保留目前为止所找到的从s到v的最短路径来工作的。 初始时，源点s的路径长度值被赋为0（d[s]=0），同时把所有其他顶点的路径长度设为无穷大，即表示我们不知道任何通向这些顶点的路径（对于V中所有 顶点v除s外d[v]= ∞）。当算法结束时，d[v]中储存的便是从s到v的最短路径，或者如果路径不存在的话是无穷大。 Dijstra算法的基础操作是边的拓展：如果存在一条从u到v的边，那么从s到u的最短路径可以通过将边(u,v)添加到尾部来拓展一条从s到v的路 径。这条路径的长度是d[u]+w(u,v)。如果这个值比目前已知的d[v]的值要小，我们可以用新值来替代当前d[v]中的值。拓展边的操作一直执行 到所有的d[v]都代表从s到v最短路径的花费。这个算法经过组织因而当d[u]达到它最终的值的时候没条边(u,v)都只被拓展一次。

算法维护两个顶点集S和Q。集合S保留了我们已知的所有d[v]的值已经是最短路径的值顶点，而集合Q则保留其他所有顶点。集合S初始状态为空，而后每一步 都有一个顶点从Q移动到S。这个被选择的顶点是Q中拥有最小的d[u]值的顶点。当一个顶点u从Q中转移到了S中，算法对每条外接边(u,v)进行拓展。

伪码
在下面的算法中,u:=Extract_Min(Q)在在顶点集Q中搜索有最小的d[u]值的顶点u。这个顶点被从集合Q中删除并返回给用户。

function Dijkstra(G, w, s)

// 初始化
for each vertex v in V[G] {
d[v] := infinity
previous[v] := undefined
d[s] := 0
}

S := empty set
Q := set of all vertices

while Q is not an empty set { // Dijstra算法主体
u := Extract_Min(Q)
S := S union {u}
for each edge (u,v) outgoing from u
if d[v] > d[u] + w(u,v) // 拓展边(u,v)
d[v] := d[u] + w(u,v)
previous[v] := u
}

如果我们只对在s和t之间寻找一条最短路径的话，我们可以在第9行添加条件如果满足u=t的话终止程序。

现在我们可以通过迭代来回溯出s到t的最短路径

1 S := empty sequence
2 u := t
3 while defined u
4 insert u to the beginning of S
5 u := previous[u]

现在序列S就是从s到t的最短路径的顶点集.

时间复杂度
我们可以用大O符号将Dijkstra算法的运行时间表示为边数m和顶点数n的函数。

Dijkstra算法最简单的实现方法是用一个链表或者数组来存储所有顶点的集合Q,所以搜索Q中最小元素的运算(Extract-Min(Q))只需要线性搜索Q中的所有元素。这样的话算法的运行时间是O(n2)。

对 于边数少于n2稀疏图来说，我们可以用邻接表来更有效的实现Dijkstra算法。同时需要将一个二叉堆或者斐波纳契堆用作优先队列来寻找最小的顶点 (Extract-Min)。当用到二叉堆的时候，算法所需的时间为O((m+n)log n)，斐波纳契堆能稍微提高一些性能，让算法运行时间达到O(m + n log n)。

相关问题和算法
在Dijkstra 算法的基础上作一些改动，可以扩展其功能。例如，有时希望在求得最短路径的基础上再列出一些次短的路径。为此，可先在原图上计算出最短路径，然后从图中删 去该路径中的某一条边，在余下的子图中重新计算最短路径。对于原最短路径中的每一条边，均可求得一条删去该边后子图的最短路径，这些路径经排序后即为原图 的一系列次短路径。

OSPF（open shortest path first, 开放最短路径优先）算法是Dijkstra算法在网络路由中的一个具体实现。

与Dijkstra算法不同，Bellman-Ford算法可用于具有负花费边的图，只要图中不存在总花费为负值且从源点 s 可达的环路（如果有这样的环路，则最短路径不存在，因为沿环路循环多次即可无限制的降低总花费）。

与最短路径问题有关的一个问题是旅行商问题(traveling salesman problem)，它要求找出通过所有顶点恰好一次且最终回到源点的最短路径。该问题是NP难的；换言之，与最短路径问题不同，旅行商问题不太可能具有多项式时间算法。

如果有已知信息可用来估计某一点到目标点的距离，则可改用A*算法 ，以减小最短路径的搜索范围。

另外，用于解决最短路径问题的算法被称做“最短路径算法”， 有时被简称作“路径算法”。 最常用的路径算法有：
Dijkstra算法
A*算法
SPFA算法
Bellman-Ford算法
Floyd-Warshall算法
Johnson算法
所谓单源最短路径问题是指：已知图G＝（V，E），我们希望找出从某给定的源结点S∈V到V中的每个结点的最短路径。
首先，我们可以发现有这样一个事实：如果P是G中从vs到vj的最短路，vi是P中的一个点，那么，从vs沿P到vi的路是从vs到vi的最短路。

2. 51定时器初值计算有什么简便算法吗

51单片机定时器初值计算：

void main（void）

{

s1=1;

TMOD=0x01; //使用定时器T0的模式1

TH0=（65536-46083）/256; //定时器T0的高8位设置初值

TL0=（65536-46083）%256; //定时器T0的低8位设置初值

函数功能：定时器T0的中断服务函数

void Time0（void ） interrupt 1 using 0 //定时器T0的中断编号为1，使用第1组工作寄存器

{

count++; //每产生1次中断，中断累计次数加1

if（count==20） //如果中断次数计满20次

count=0; //中断累计次数清0

s++; //秒加1

定时器初值 46083 是怎么计算出来的？ 一般我们如用 AT892051的话 定时50MS 就是 TH0=（65536-50000）/256。使用的12M晶体 ，20次为1S。

(2)usch算法扩展阅读：

使用说明

以12M晶振为例：每秒钟可以执行1000000次机器周期个机器周期。而T 每次溢出最多65536 个机器周期。我们尽量应该让溢出中断的次数最少（如50ms），这样对主程序的干扰也就最小。

开发的时候可能会根据需要更换不同频率的晶振（比如c51单片机，用11.0592M的晶振，很适合产生串口时钟，而12M晶振很方便计算定时器的时间），使用插接式比较方便。

对12MHz 1个机器周期 1us 12/fosc = 1us，方式0 13位定时器最大时间间隔 = 2^13 = 8.192ms，方式1 16位定时器最大时间间隔 = 2^16 = 65.536ms，方式2 8位定时器最大时间间隔 = 2^8 = 0.256ms =256 us。

定时5ms，计算计时器初值 M = 2^K-X*Fosc/12 12MHz。方式0： K=13，X=5ms，Fosc=12MHz 则 M = 2^13 - 5*10^（-3）*12*10^6/12= 3192 = 0x0C78。

THx = 0CH，TLx = 78H，方式1： K=16，X=5ms，Fosc=12MHz 则 M = 2^16 - 5*10^（-3）*12*10^6/12= 60536 = 0xEC78。

THx = ECH，TLx = 78H，50ms 12MHz THx = 3CH，TLx = B0H，10ms THx = D8H，TLx = F0H。