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。