組合優(yōu)化(歐拉圖)

1、歐拉圖與中國郵遞員問題算法歐拉圖與中國郵遞員問題算法歐拉圖與中國郵遞員問題算法歐拉圖與中國郵遞員問題算法歐拉圖和哈密頓圖的介紹歐拉圖的算法介紹歐拉圖在中國郵遞員問題的運用哈密頓圖的相關介紹哈密頓圖在旅行商問題的運用歐拉圖和哈密頓圖的介紹歐拉圖和哈密頓圖的介紹 圖： 圖是一個有序二元組，其中V稱為頂點集，E稱為邊集。E的元素都是二元組，用(x,y)表示，其中x , y來源于V.歐拉圖和哈密頓圖的介紹歐拉圖和哈密頓圖的介紹 歐拉路： 通過圖G的每條邊一次且僅一次的開路稱為歐拉路。 半歐拉圖： 存在歐拉路的圖稱為半歐拉圖。 歐拉回路： 通過圖G的每條邊一次且僅一次的回路稱為歐拉回路。 歐拉圖： 存在

2、歐拉回路的圖稱為歐拉圖。 哈密頓路： 通過圖G的每個結點一次且僅一次的路徑稱為哈密爾頓路。 半哈密頓圖：存在哈密頓路的圖稱為半哈密頓圖。 哈密頓回路： 通過圖G的每個結點一次且僅一次的回路稱為哈密爾頓回路。 哈密頓圖： 存在哈密頓回路的圖稱為哈密頓圖。歐拉圖和哈密頓圖的介紹歐拉圖和哈密頓圖的介紹歐拉圖的算法介紹歐拉圖的算法介紹 定理1： 無向圖G為歐拉圖的充要條件G是連通圖且沒有奇度頂點。 定理2： 無向圖G是半歐拉圖的充要條件G是連通的且恰有兩個奇度的頂點。 無向圖中尋找歐拉回路歐拉圖的算法介紹歐拉圖的算法介紹要輸出的歐拉回路隊列當前訪問的節(jié)點已經訪問的邊節(jié)點的鄰近節(jié)點從當前訪問節(jié)點的鄰居中

3、找一個節(jié)點 例：歐拉圖的算法介紹歐拉圖的算法介紹 定理3： 由上述的算法框架可以找到一條歐拉回路。 定理1： 無向圖G為歐拉圖的充要條件G是連通圖且沒有奇度頂點。歐拉圖的算法介紹歐拉圖的算法介紹 有向圖中尋找歐拉回路的預備知識點 這兒我們使用逆向思維(如果可以找到歐拉回路，那么這個圖肯定是歐拉圖。當然，如果是歐拉圖，也肯定能找到歐拉回路) Spanning out-tree歐拉圖的算法介紹歐拉圖的算法介紹 定理4： If G is a connected, balanced diagraph with spanning out-tree T rooted at u , then an Eule

4、rian circuit can be traced in reverse direction as follows: (a) The initial edge is any edge incident to u; (b) Subsequent edges are chosen so as to be incident to the current vertex and such that： No edge is traversed more than once. No edge of T is chosen if another edge is still available. The pr

5、ocess stops when a vertex is reached which has no unused edges incident to it.歐拉圖的算法介紹歐拉圖的算法介紹時間復雜度：O(|E|) 有向圖中尋找歐拉回路歐拉圖的算法介紹歐拉圖的算法介紹要輸出的歐拉回路隊列節(jié)點的鄰近節(jié)點Av鏈表的下標對Av隊列進行賦值進行尋找歐拉回路 例：歐拉圖的算法介紹歐拉圖的算法介紹歐拉圖在中國郵遞員問題的運用歐拉圖在中國郵遞員問題的運用 中國郵遞員問題 如何走完一個城市的所有路徑，然后回到原地。 首先，對于一個歐拉圖不止一條歐拉回路。 對于無向歐拉圖 對于有些歐拉圖歐拉圖在中國郵遞員問題的運

6、用歐拉圖在中國郵遞員問題的運用n-ii = 1count = (d (v ) - 1)!n-ii = 1count = T(G) * (d (v ) - 1)! 問題： 如何在一個有權重、無向的、非歐拉圖中找到一條最短的路徑?(所有的路徑都要至少走一遍，并且回到原點) 解決方法： 在將原本的非歐拉圖G基礎加入路徑后形成歐拉圖G。 由于是求最短路徑，故加入的路徑長度應該越短越好。歐拉圖在中國郵遞員問題的運用歐拉圖在中國郵遞員問題的運用 算法框架：歐拉圖在中國郵遞員問題的運用歐拉圖在中國郵遞員問題的運用 例：歐拉圖在中國郵遞員問題的運用歐拉圖在中國郵遞員問題的運用 問題： 如何在一個有權重、有向的

7、、非歐拉圖中找到一條最短的路徑?(所有的路徑都要至少走一遍，并且回到原點) 與無向圖的區(qū)別： 可能形成不了環(huán)。歐拉圖在中國郵遞員問題的運用歐拉圖在中國郵遞員問題的運用XY 定理4： 有些圖有郵遞員回路，當且僅當它是強連通的。 解決方法： 在將原本的有向非歐拉圖G基礎加入路徑后形成有向歐拉圖G。 由于是求最短路徑，故加入的路徑長度應該越短越好。歐拉圖在中國郵遞員問題的運用歐拉圖在中國郵遞員問題的運用 算法框架：歐拉圖在中國郵遞員問題的運用歐拉圖在中國郵遞員問題的運用 例：歐拉圖在中國郵遞員問題的運用歐拉圖在中國郵遞員問題的運用哈密頓圖的相關介紹哈密頓圖的相關介紹 哈密頓路： 通過圖G的每個結點一

8、次且僅一次的路徑稱為哈密爾頓路。 半哈密頓圖：存在哈密頓路的圖稱為半哈密頓圖。 哈密頓回路： 通過圖G的每個結點一次且僅一次的回路稱為哈密爾頓回路。 哈密頓圖： 存在哈密頓回路的圖稱為哈密頓圖。 一些現(xiàn)有的知識理論： 完全圖是哈密頓圖。 基本圖是完全圖的有向圖，包含了哈密頓路徑。 基本圖是完全圖的強連通圖，是一個哈密頓圖。 如果G是一個無向圖，并且它的邊數(shù)n大于3，每個頂點的度都大于1/2 n，則G是哈密頓圖。 如果G=(V,E)是一個哈密頓圖，那么對于它的每一子圖都有：C(G V) b - c - a 52. a - b - a - b - a 4 問題所在： 就是在帶有權重的圖中，存在這樣

9、的情況：三個點形成的三角形不滿足三角形不等式，即兩邊之和不大于第三邊。 然而，在第二種情況下，我們所得的解并不是一個環(huán)了，可能有多個。給我們對問題求解帶來很多麻煩。 解決方法： 對圖進行調整。 總結： 對于那些滿足三角形不等式的圖形，我們可以直接求其回路。(相對應于第一種定義) 對于那些不滿足三角形不等式的圖形，我們進行調整后在求其回路。 (相對應于第二種定義)哈密頓圖在旅行商問題的運用哈密頓圖在旅行商問題的運用 定理5： 對圖形進行調整前后，旅行商問題的最短路徑長度是相同的。 前提： 對圖形計算最短哈密頓回路的時間復雜度為O(N)。哈密頓圖在旅行商問題的運用哈密頓圖在旅行商問題的運用由于準確

10、求解所需時間過長，我們采取近似求解。假設準確求解結果為L,近似求解結果為L，我們定義：則，a越趨近于1，結果越好。哈密頓圖在旅行商問題的運用哈密頓圖在旅行商問題的運用01L/L Nearest-neighbour method 即每次都從鄰居中選擇最短的路徑 哈密頓圖在旅行商問題的運用哈密頓圖在旅行商問題的運用1( ln( )1)2n An approximation algorithm for the travelling salesman problem哈密頓圖在旅行商問題的運用哈密頓圖在旅行商問題的運用2 例：哈密頓圖在旅行商問題的運用哈密頓圖在旅行商問題的運用L(v1)=1 L(v2)=2 L(v3)=3 L(v4)=4 L(v5)=5 L(v6) =6 An improved approximation algorithm for the travelling salesman problem哈密頓圖在旅行商問題的運用哈密頓圖在旅行商問題的運用32 例：哈密頓圖在旅行商問題的運用哈密頓圖在旅行商問題的運用L(v1)=