[[alternative]]Retracing and adjusting edge algorithm for crossing reduction

碩士[[abstract]]「最小化交叉點問題」是指將網路節點配置在平面上，試著去找出一個較佳的配置方式，使得網路連線與連線之間產生的交叉點最少。在許多的應用中，例如Circuit Board Layout、VLSI Circuit Layout、Automated Graph Drawing等，「最小化交叉點問題」一直是相當重要的一環，愈低的交叉點數量，往往代表著愈低的成本。在這篇論文中，我們研究的題目比「最小化交叉點問題」更特定，我們僅討論FLCNP（Fixed Linear Crossing Number Problem）。FLCNP類似k-pages book crossing number中的兩頁交叉點問題，指將所有的節點排成一條直線，我們稱之為「節點線」，由節點線所區隔開的上下兩個區域我們稱之為「頁面」。節點與節點在連接時，該連線必須以弧線的方式在上下兩個頁面做連接，連線不可從任一邊的頁面跨越節點線到另一邊的頁面。另外還需符合兩個條件，一是節點為有順序性而且是預先就知道的；二是節點的位置是固定不可變動的。我們藉由實作幾個現有的演算法，分析其優缺點，進而提出利用回顧調整的方式來有效降低交叉點的數量[[abstract]]This thesis studies the problem of crossing number reduction in drawing a graph on a two dimensional plane. Crossing number reduction problem is an important part among many applications, such as circuit board layout, VLSI circuit layout and automated graph drawing and so on. For those applications, lower crossing number means lower cost. This thesis focus on the reduction of crossing number in FLCNP (Fixed Linear Crossing Number Problem). The problem of fixed linear crossing number is to arrange all network nodes along a “node line” according to a pre-arranged order. Each edge is drawn as a semicircle above or below the node line. Existing heuristic algorithm of crossing reduction are analyzed and a “retracing and adjusting edge algorithm” for effective crossing reduction are proposed in this thesis.[[tableofcontents]]目錄 第一章 緒論 1 1.1 研究背景 1 1.2 研究動機與目的 2 1.3 相關研究 3 1.3.1 尼可森之經驗法則 3 1.3.2 分支限制演算法 3 1.3.3 最大切割解法 4 1.3.4 Cimikowski的演算法 5 第二章 演算法介紹與實作 7 2.1 交叉點定義 7 2.2 實驗環境 8 2.3 Greedy Algorithm 9 2.3.1 介紹 9 2.3.2 演算法 10 2.3.3 演算法說明 10 2.4 Edge-Length Algorithm 11 2.4.1 介紹 11 2.4.2 演算法 12 2.4.3 演算法說明 12 2.5 Maximal Planar Algorithm 13 2.5.1 介紹 13 2.5.2 演算法 14 2.5.3 演算法說明 15 2.6 One-Page Algorithm 16 2.6.1 介紹 16 2.6.2 演算法 18 2.6.3 演算法說明 19 2.7 Crossing-Probability Algorithm 20 2.7.1 介紹 20 2.7.2 演算法 21 2.7.3 演算法說明 21 2.8 相關Function 22 2.8.1 讀取網路圖 22 2.8.2 新增連線 23 2.8.3 取得交叉點數量 23 2.8.4 傳回任一Edge的內外節點 24 2.9 實驗步驟及分析 25 2.10 各演算法重新配置網路圖後之實驗數據 28 2.10.1 各演算法重新配置隨機網路數據 28 2.10.2 各演算法重新配置小世界網路數據 37 2.11 各演算法特性分析 46 2.11.1 Greedy Algorithm 46 2.11.2 Edge-Length Algorithm 47 2.11.3 Maximal Planar Algorithm 48 2.11.4 One-Page Algorithm 49 2.11.5 Crossing-Probability Algorithm 49 第三章 回顧調整方法 50 3.1 由來 50 3.2 演算法介紹 52 3.3 演算法列表及說明 54 3.4 實驗步驟及結果比較 58 3.4.1 實驗步驟 58 3.4.2 結果比較 58 3.5 回顧調整方法重新配置網路圖後之實驗數據 63 3.5.1 利用回顧調整方法重新配置隨機網路數據 63 3.5.2 利用回顧調整方法重新配置小世界網路數據 81 第四章 結論與展望 99 4.1 結論 99 4.2 未來展望 99 參考文獻 100 附錄－英文論文 101 圖目錄 圖1.1.1 磚塊工廠磚窯與倉庫的鐵軌連接方式 1 圖1.2.1 FLCNP示意圖 2 圖1.3.3.1 對網路圖G的所有連線進行編號 4 圖1.3.3.2 反矩陣圖形G'' 5 圖2.1 與連線E{i,j}發生交叉點的條件 7 圖2.3.1 Greedy演算法說明圖 9 圖2.4.1 Edge-length演算法說明圖 11 圖2.5.1 Maximal planar演算法說明圖 13 圖2.6.1 One-page演算法說明圖 17 圖2.7.1 Crossing-Probability演算法說明圖 20 圖2.8.4 內外部節點說明 24 圖2.9.1 隨機網路示意圖 26 圖2.9.2 規則網路示意圖 26 圖2.9.3 小世界網路示意圖 26 圖2.10.1.1 節點數為10之隨機網路經各演算法重新配置後的交叉點曲線圖 29 圖2.10.1.2 節點數為20之隨機網路經各演算法重新配置後的交叉點曲線圖 32 圖2.10.1.3 節點數為30之隨機網路經各演算法重新配置後的交叉點曲線圖 35 圖2.10.2.1 節點數10之小世界網路經各演算法重新配置後之交叉點曲線圖 38 圖2.10.2.2 節點數20之小世界網路經各演算法重新配置後之交叉點曲線圖 41 圖2.10.2.3 節點數30之小世界網路經各演算法重新配置後之交叉點曲線圖 44 圖2.11.2 Edges{i,j} 47 圖2.11.3 節點１與節點２的連線各別分佈在上頁面及下頁面 48 圖2.11.5 Edges{i,j} 49 圖3.1.1 （a）為原始網路圖（b）為最佳配置圖 51 圖3.1.2 Edges{1,4}及Edges{2,5}包住了其它所有的連線 51 圖3.1.3 因節點３連線的頁面選擇不佳，造成大量的交叉點 51 圖3.2.1 回顧調整方法選擇需調整的連線 53 圖3.5.1.1 各演算法使用回顧調整方法後交叉點曲線圖 64 圖3.5.1.2 各演算法使用回顧調整方法後交叉點曲線圖 66 圖3.5.1.3 各演算法使用回顧調整方法後交叉點曲線圖 68 圖3.5.1.4 各演算法使用回顧調整方法後交叉點曲線圖 70 圖3.5.1.5 各演算法使用回顧調整方法後交叉點曲線圖 72 圖3.5.1.6 各演算法使用回顧調整方法後交叉點曲線圖 74 圖3.5.1.7 各演算法使用回顧調整方法後交叉點曲線圖 76 圖3.5.1.8 各演算法使用回顧調整方法後交叉點曲線圖 78 圖3.5.1.9 各演算法使用回顧調整方法後交叉點曲線圖 80 圖3.5.2.1 各演算法使用回顧調整方法後交叉點曲線圖 82 圖3.5.2.2 各演算法使用回顧調整方法後交叉點曲線圖 84 圖3.5.2.3 各演算法使用回顧調整方法後交叉點曲線圖 86 圖3.5.2.4 各演算法使用回顧調整方法後交叉點曲線圖 88 圖3.5.2.5 各演算法使用回顧調整方法後交叉點曲線圖 90 圖3.5.2.6 各演算法使用回顧調整方法後交叉點曲線圖 92 圖3.5.2.7 各演算法使用回顧調整方法後交叉點曲線圖 94 圖3.5.2.8 各演算法使用回顧調整方法後交叉點曲線圖 96 圖3.5.2.9 各演算法使用回顧調整方法後交叉點曲線圖 98 表目錄 表2.10.1.1 節點數為10之隨機網路經各演算法重新配置後的相關數據 29 表2.10.1.2 節點數為20之隨機網路經各演算法重新配置後的相關數據 32 表2.10.1.3 節點數為30之隨機網路經各演算法重新配置後的相關數據 35 表2.10.2.1 節點數為10之小世界網路經各演算法重新配置後的相關數據 38 表2.10.2.2 節點數為20之小世界網路經各演算法重新配置後的相關數據 41 表2.10.2.3 節點數為30之小世界網路經各演算法重新配置後的相關數據 44 表3.4.2.1 節點數為10之隨機網路數據比較 60 表3.4.2.2 節點數為20之隨機網路數據比較 60 表3.4.2.3 節點數為30之隨機網路數據比較 61 表3.4.2.4 節點數為10之小世界網路數據比較 61 表3.4.2.5 節點數為20之小世界網路數據比較 62 表3.4.2.6 節點數為30之小世界網路數據比較 62 表3.5.1.1 各演算法使用回顧調整方法後相關數據 64 表3.5.1.2 各演算法使用回顧調整方法後相關數據 66 表3.5.1.3 各演算法使用回顧調整方法後相關數據 68 表3.5.1.4 各演算法使用回顧調整方法後相關數據 70 表3.5.1.5 各演算法使用回顧調整方法後相關數據 72 表3.5.1.6 各演算法使用回顧調整方法後相關數據 74 表3.5.1.7 各演算法使用回顧調整方法後相關數據 76 表3.5.1.8 各演算法使用回顧調整方法後相關數據 78 表3.5.1.9 各演算法使用回顧調整方法後相關數據 80 表3.5.2.1 各演算法使用回顧調整方法後相關數據 82 表3.5.2.2 各演算法使用回顧調整方法後相關數據 84 表3.5.2.3 各演算法使用回顧調整方法後相關數據 86 表3.5.2.4 各演算法使用回顧調整方法後相關數據 88 表3.5.2.5 各演算法使用回顧調整方法後相關數據 90 表3.5.2.6 各演算法使用回顧調整方法後相關數據 92 表3.5.2.7 各演算法使用回顧調整方法後相關數據 94 表3.5.2.8 各演算法使用回顧調整方法後相關數據 96 表3.5.2.9 各演算法使用回顧調整方法後相關數據 98[[note]]學號: 795410165, 學年度: 9