论文资料：网路模式(Network.doc

精品文档 免费阅读 免费分享 如需请下载！第九章 網路模式(Network Models)本章內容：9.1 最短路徑問題9.2 最小展開樹問題9.3 最大流量問題9.1最短路問題最短路徑問題係在一個網路中找尋節點1到每個其他節點間的最短路徑。若網路中所有的弧(arcs)為非負值，則以標籤法(Label)來找網路中一特定節點至所有其他節點之最短路徑。最短路徑問題中不限於求距離之極小化，其亦可解決時間或成本之極小化問題。標籤法：以一中括號為標籤，如下圖所示： 從節點1至本節點之距離是20路徑上從節點1到本節點的前一個節點為節點4 20,4節點標籤節點圖9.2 節點標籤之例第一個數字表示從節點1到此節點的距離。第二數字從節點1到本節的路徑上，本節點的前一個節點。已找出從節點1至某節點的最短距離，這個節點稱為有一個永久的標籤(permanent label)，由節點1至某節點的最短距離的尚未找出來，這個節點就說有一個暫時的標節籤(tentative label)。一開始給節點1永久標籤O,S。O表示從節點1到它自己的距離是零，S表示節點1為起始節點。用一個箭頭指著某永久標籤,正研究這個永久標籤。请下载！ 例：哥曼公司有幾個建築計劃，下圖說明辦公室與6個工地的關係，兩個位置之間的距離，寫在弧上，哥曼要找出路徑，使公司到各工地之旅行 距離最短。23456711531042517646道路長度(哩)哥曼的辦公室圖9.1 哥曼公司最短路徑問題網路圖解：開始時只有節點1為永久標籤234567115310425176460,S圖9.3 哥曼最短路徑問題起始網路標籤考慮所有可由節點1直接到達的節點(節點2,3)：節點2：節點1至節點2的直接距離為15里，所以節點2的暫時標籤為15,1。節點3：節點1到節點3的直接距離是10里。所以節點3的暫時標籤為10,1。234567115310425176460,S15,110,1圖9.4 哥曼網路之中，節點2及3有暫時標籤234567115310425176460,S15,110,1考慮所有暫時標籤的節點(節點2,3)，並找出在標籤中距離最小者為永久標籤；所以節點3是永久標籤，距離是10里。用一箭頭指著它，表示標籤法的下一步由它開始。圖9.5 哥曼網路，節點為永久標籤節點考慮所有可由節點3直接到達的節點：節點2：到節點3的最短距離是10里節點3到節點2的直接距離是10+3=13里，所以節點2的暫時標籤改為13,3。234567115310425176460,S15,110,114,313,3節點5：到節點的最短距離是10里節點3到節點5的直接距離是10+4=14里，所以節點5的暫時標籤改為14,3。圖9.6 哥曼網路，節點2及5有新暫時標籤19,2234567115310425176460,S10,114,313,330,2考慮所有暫時標籤的節點(節點2,5)，並找出其距離值最小者為永久標籤。所以節點2變成永久標籤，距離是13里。用一箭頭指著它，表示標籤法的下一步由它開始。圖9.7 哥曼網路，節點2有永久標籤，節點4及有新暫時標籤考慮所有可由節點2直接到達的節點(節點4,7)：節點4：到節點2的最短距離是13里節點2到節點4的直接距離是13+6=19里，所以節點4的暫時標籤為19,2節點7：到節點2的最短距離是13里節點2到節點7的直接距離是13+17=30里，所以節點7的暫時標籤為30,2考慮所有可由節點3直接到達的節點(節點5)節點5：到節點3的最短距離是10里節點3到節點5的直接距離是10+4=14里，所以節點5的暫時標籤為15,3在所有暫時標籤節點(節點4,5,7)選最小者為永久標籤，所以標籤5變成永久標籤，用一個箭頭指著它，表示標籤法的下一步由它開始。因此節點4的暫時標籤需從19,2，改為18,5234567115310425176460,S10,114,313,330,216,519,218,5圖9.8 節點5有永久標籤，節點4，6有新暫時標籤234567115310425176460,S10,114,313,330,216,522,6從所有暫時標籤節點(節點4,6)找最小距離，結果節點6變為永久標籤節點。從節點6再找到節點7的新暫時標籤，距離22(見下圖)。18,5圖9.9 節點6有永久標籤，節點7有新暫時標籤現在只剩兩個非永久標籤節點（節點4,7），節點4的距離小於節點7，所以節點4變成永久標籤節點。因為節點7是唯一非永久標籤節點，可以直接由節點4到達，將距離值22，與由節點4過來的距離18+5=23比較，因為22,6暫時標籤的距離值比較小，所以不必改變。234567115310425176460,S10,114,313,316,522,618,5圖9.11 所有節點均有永久標籤節點從節點1的最短路徑距離(里)234567131018141622最短路徑標籤法步驟：第一步：給節點永久標籤O,S；O表示從節點至自己的距離為零，S表示節點是起點。第二步：計算可以直接由節點到達的節點的暫時標籤，在每個標籤的第個數字代表從節點至此節點的距離；第個數字代表從節點到此節點的路徑的前一個節點。在這一步，在前節點值是，因為我們只考慮直接從過來的節點。第三步：在暫時標籤中找出距離值最小者，將之稱為永久標籤節點，如果所有節點均為永久標籤節點，到第五步。第四步：考慮其他剩下非永久標籤節點，而又可以由第三步所得之新的永久標籤節點直接到達者，計算這些節點的暫時標籤如下：(a)如果此節點已有暫時標籤，將新永久標籤節點之距離加上此直接距離，如果此和小於此節點之原有距離，將此節點之距離改為這個較小的和的數字，而將在前節點的數值改為這個有較小距離的節點，然後到第三步。(b) 如果此節點仍未標注，給它一個暫時標籤，將新永久標籤的距離值加上直接距離，就是這個節點的距離值，在前節點就是這個新的永久標籤節點，然後到第三步。第五步：永久標籤指出從節點到每個節點的最短距離及在最短路徑的前一個節點。到某個節點的最短路徑，可以由該節點向前移到它的前一個節點，繼續這樣倒推回去，就可找出從節點到各節點的最短路徑。最短路徑可以找到從節點1到每一個其他節點最短距離，這個方法也可修改為從任何節點，K點，到所有其他節點的最短距離。這種改變只要節點K的標籤改為永久標籤O,S開始，就可找到從節點K到網路其他節點的最短路徑了。 9.2 最小展開樹問題樹是一組連接的弧，它不會形成一循環(cyele)。展開樹是連接網路所有節點的樹。展開樹係尋找連接網路中所有節點的最短總弧長(即一個展開樹是在N個節點的網點中，以N-1個弧使所有節點都連接起來。最小展開樹中最小的準則不限於距離，其他準則包括時間與成本。最小展開樹步驟：第1步：自任意節點開始連接最近的節點，這兩點節點稱為已連接節點(connected)。其他剩餘節點稱為未連接節點。第2步：找出未連接節點中與已連接節點最近者，如有兩個相同則任取一個。將此新節點加入已連接節點集合，重覆此步驟直至所有節點均已連接為止。12345距離哩數405040304020304030區域電腦中心 206例：西南區域電腦中心為5個使用者建立聯到中心電腦的新通訊網路，中心希望新通訊線的長度儘量的短。讓各用戶互相接連的聯結下去，要比直接由中心聯到各用戶便宜。下圖即為這種最短的通訊系統設計，試找出最短距離。1012345距離哩數405040304020304030區域電腦中心 20610圖9.13 地區電腦中心通訊網路圖解：任取一節點開始，此處取節點1為開始，最近點為節點2，其距離是20，以一條黑粗線連線節點1及節點2，如下圖所示：1012345405040304020304030206在未連接節點中，與已連接節點(節點1,2)最近者是節點4，它與節點1的距離是30里。將節點4加入已連接節點集合之中，如下圖所示：1234540504030402030403020610在未連接節點中，與已連接節點(節點1,2,4)最近者是節點3，它與節點4的距離是10里。將節點3加入已連接節點集合之中，如下圖所示：1240504030402030403020103465在未連接節點中，與已連接節點(節點1,2,4,3)最近者是節點6，它與節點4的距離是20里。將節點6加入已連接節點集合之中，如下圖所示：1240504030402030403020103465圖9.14 區域電腦中心通路的最小擴張樹在未連接節點中，與已連接節點(節點1,2,4,3,6)最近者是節點5，它與節點3的距離是30里。將節點5加入已連接節點集合之中，其總長度為20+30+10+20+30=110里。1240504030402030403020103465圖9.14 地區電腦中心通訊網路最小展開樹9.3 最大流量問題最大流量考慮僅有一個輸入(或供應)節點及僅有一個輸出(流出)節點的網路問題。最大流量問題是找出進入及流通過網路的最大流量。最大流量是尋找從一個節點（稱為輸入節點）至另一節點（稱為輸出節點）之最大流量。最大流量中，每一弧有一最大弧流容量(arc flow capacity)，此最大弧流容量是弧上流量的上限。從i節點至j節點與從j節點至i節點也許會有不同流量。最大流量問題解題步驟：第1步：找從輸入節點至輸出節點的任何路徑，而在路徑上沿流通方向各弧的流容量均大於零(即為正值)，如果找不到，最適解就達到了。第2步：在第1步所選的路徑中，找最小的流容量，指派流通量到第步所選的路徑，以增加網路的流量。第3步：在第步所選的路徑中，將各弧在流量方向的流容量減少，在相反方向流容量增加。回到第步。第4步：當無法找到能使輸入節點到輸出節點之流量增加的路徑就停止。最大流量問題步驟說明：最大流量方法允許在反方向增加虛構的流容量，以改變先前指定的流容量，例如在3-6弧。3670原來在3-6方向為7000輛/時，不允許6-3方向，若指派6000輛在3-6方向，則將流容量改變為3616在3-6方向的流容量1000輛表示弧上剩下的流容量。6-3方向原來流容量為零，現在變為6000輛/時。事實上係假想允許在這方向流通6000輛/時。在6-3方向的假想流量，並不真的派車通過，而只代表減少原來3-6方向的原來允許流容量。例：南北州際高速路系統，通過辛辛那堤，南北車流尖峰時刻達到每小時15000輛，預計的網路及其流容量見下圖。試問每小時的最大流量是多少？每個弧有多少流量？圖9.16 辛辛那堤高速路系統流容量(千輛/小時)註：節點1為輸入節點，節點7為輸出節點。解：重覆1所選路徑1367；最小弧容量在弧13，為6。修改過之網路如下：重覆2所選路徑1257；最小弧容量在弧25，為3。修改過之網路如下：將各重覆步驟的值相加，即得通過網路的總流量。重覆3所選路徑12357；最小弧容量在弧12(或23)，為2。修改過之網路如下：重覆4所選路徑1467；最小弧容量在弧67，為1。修改過之網路如下：重覆5所選路徑14657；最小弧容量在弧65，為1。修改過之網路如下：重覆6所選路徑146357；最小弧容量在弧35，為1。所以最大流量為14,000輛/時。在重覆6中，有1000輛/時的流量允許在6-3方向通過，但是從起始的網路來看，我們知道6-3方向流容量為零；所以這在6-3方向的1000輛代表假想流量，實際的影響是原來給3-6弧1000輛轉向到3-5弧。最大流量問題之各弧的流量，可由最後弧容量與起始弧容量比較而得，如果最後容量小於起始流容量，該弧的流量就是這兩個容量的差。例如在3-6弧，其起始及最後弧容量如下：3670起始容量 3625最後容量 3653-6方向的最後流容量小於