最小生成樹及應(yīng)用課件

1、最小生成樹及應(yīng)用生成樹指沒有任何回路的圖圖由點、線和長度構(gòu)成以前的網(wǎng)絡(luò)圖，求關(guān)鍵路徑為求最長路。煤氣管道的鋪設(shè)某新建小區(qū)著手鋪設(shè)煤氣管道，已知每一幢樓的接入位置和距離，請求出最短的鋪設(shè)方案。ABCDO1386549910破圈法ABCDO6549最短路：問題最短生成樹唯一嗎？如果是求最長生成樹，如何解決？123練習求最短生成樹123451253-423動態(tài)規(guī)劃(Dynamic Programming)動態(tài)規(guī)劃(Dynamic Programming)1、動態(tài)規(guī)劃解決的問題可解決運輸問題（p165例3）、生產(chǎn)問題（p165例4）、庫存問題、定價問題和資金運用等問題。2、涉及學科3、Bellman最

2、優(yōu)化原理P1634、圖上作業(yè)法5、表上作業(yè)法Bellman最優(yōu)化原理Bellman方程(最短路方程、動態(tài)規(guī)劃基本方程 ) 每一點最優(yōu)都是上一點最優(yōu)加上這段長度。即當前最優(yōu)只與上一步有關(guān)。例1 從上海到伊犁間有一個鐵路網(wǎng)，某學生暑假打算到伊犁旅游，出于經(jīng)濟關(guān)系只能坐火車，而且要求費用最少。下圖標出了各種可能的行車路線，請為這位同學的決策做出指導。圖上作業(yè)法上海伊犁AB45CDE425FH56753G43654546求費用最小的方案如果用窮舉法，先要計算從上海到伊犁的所有路徑的費用，再取最小的路徑。Dijkstra算法計算過程 正向圖上作業(yè)法RAm=4,RBm=5,RCm=minRAm-C8,RB

3、m-C12=8RDm=minRAm-D,RBm-D=6REm=minRAm-E9,RBm-E8=8RFm=minRCm-F13, RDm-F10,REm-F14=10RGm=minRDm-G9,REm-G13=9RHm=minRCm-H14,REm-H12=12RSm=minRFm-S15,RGm-S13,RHm18-S=13G943RS13A4B545C8D6E8425F10H1256546753654RBm-E8REm-H12RGm-S13RDm-G9RDm-F10RAm-C8RAm-DRAmRSmRGmRDmRAm計算過程 逆向FSm=5,GSm=4,HSm=6CSm=minC-FSm,

4、C-HSm=10DSm=minD-FSm,D-GSm=7ESm=minE-FSm,E-GSm,E-HSm=9ASm=minA-CSm,A-DSm,A-ESm=9BSm=minB-CSm,B-DSm,B-ESm=12RSm=minR-ASm,R-BSm=13圖上作業(yè)法G443R13SA9B1245C10D7E9425F5H656546753654圖上作業(yè)法R上海S伊犁AB45CDE425FH56753G43654546費用最小的方案為RADGS13有時可能有幾條費用最小方案，也可一同求出。表上作業(yè)法對于狀態(tài)很多的問題，圖上表示不易，適宜采用表上作業(yè)法。見P164-165表上作業(yè)法Q：如何求效益最大問題？在計算中采用MAX函數(shù)課后練習再網(wǎng)上搜索Dijkstra的信息，為他作一份網(wǎng)頁，你怎樣和他取得聯(lián)系？動態(tài)規(guī)劃除了Dijkstra算法之外還有其他方法嗎？作業(yè)：下表表示一個AK城的運輸任務(wù)，數(shù)字表示10公里數(shù)，請為司機選擇最短的路線（分別用圖上和表上作業(yè)法）。http:/ S.Introduction to Stochastic Dynamic Program