跳到主要內容

臺灣博碩士論文加值系統

(3.231.230.177) 您好!臺灣時間:2021/07/28 15:42
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:許宏敏
論文名稱:多重選區劃分之分析與研究
論文名稱(外文):Multi-district electoral redistricting
指導教授:何瑁鎧何瑁鎧引用關係
學位類別:碩士
校院名稱:國立政治大學
系所名稱:資訊科學學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2009
畢業學年度:97
語文別:中文
論文頁數:75
中文關鍵詞:選區劃分
相關次數:
  • 被引用被引用:5
  • 點閱點閱:187
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
當選舉制度改變或行政區域調整的時候,選舉區域必須因應這些變更而重新劃分。傳統的選區劃分方式常需花費大量的人力與時間,同時易產生公平性的爭議,透過電腦的分析並採取有系統的選區劃分方式可以有效地節省人力、時間等資源並減少爭議性。以電腦自動分析來劃分選區有許多議題值得探討,諸如如何在有限的時間內完成選區劃分、如何規劃並維持選區形狀的完整性、如何產生足夠有代表性的解集合但又能避免解集合過於龐大、如何評估選區的優劣、如何偵測並避免重覆解等,都是目前有待分析的問題。我們嘗試以資訊科技的觀點來看選區劃分,並嚐試為上述問題提供看法與解答。
一般而言,影響選區劃分的因素大體可歸納為下列六類:人口一致性、選區連接性、形狀完整性、避免過度切割行政區域、保障少數族群利益以及尊重自然疆界等。並非所有的因素都適合以電腦來分析或處理,我們將針對人口一致性、選區連接性、形狀完整性等問題做討論。
過去我們曾提出人口比例二分法來劃分簡單的選區,透過計算幾何學和人工智慧的技巧可將選區依人口比例劃分成兩份。然而採用此法處理多重選區劃分時所產生的解集合數量過於龐大,目前的電腦無法有效處理。本論文中,我們提出了「不可分割」的觀念,透過事先設定的不可分割區並輔以砌磚法與重覆地使用人口比例法,我們成功的將多重選區劃分問題的解集合數目控制在電腦能處理的範圍之內。此外我們對選區形狀完整性提出了新的評估方式,可以更有效地篩選出較佳的解集合作進一步的分析。
實作中我們以台中市和桃園縣為對象來檢驗我們的方法,實驗結果顯示我們的方法成功地為台中市(劃分成三個選區)與桃園縣(劃分成六個選區)找到了數以十萬計的選區劃分方式。我們從通過高標準評估的解集合中,挑選出若干個解與中選會公佈的選區劃分方式比較,結果顯示我們的劃分方式有明顯的優勢。另外,我們將歷史選舉資料中選民投票的傾向套入實驗的選區劃分結果中,可以分析並預測未來的選舉結果。
總結而言,我們提出了一套系統化的方式成功地為多重選區劃分的問題找到了大量的合理解,透過進一步的評估,不同的劃分方式能滿足不同的需求。另外,我們所提出的不可分割的觀念,不僅能有效的降低解集合的數目,未來還可以應用到避免行政區域之過度切割、保障少數族群利益與尊重自然疆界等問題上。
第一章 緒論 1
1.1 前言 1
1.2 研究動機 1
1.3 選區劃分原則與問題描述 2
1.4 多重選區劃分之概述 4

第二章 相關研究 5
2.1 矩形劃分法 5
2.2 人口均等法 6
2.3 線性規劃法 6
2.4 分治法 7
2.5 砌磚法 7
2.6 鄉村包圍城市法 8
2.7 基因演算法 8

第三章 選區劃分 9
3.1 人口比例二分法 10
3.2 連接性檢查 10
3.3 形狀完整性 11
3.3.1 最小包圍矩形 12
3.3.2 凸包面積比 13
3.3.3 最小外接圓形面積比 14
3.4 重複性偵測 14

第四章 多重選區劃分 16
4.1 重複使用人口比例二分法 16
4.2 複雜度分析 18
4.3 人口誤差 19
4.4 多重選區劃分之特性 19

第五章 系統架構 22
5.1 資料前處理 23
5.2 多重選區劃分之步驟 24

第六章 實驗結果 26
6.1 巨量的解集合 26
6.1.1 台中市之解集合數 26
6.1.2 桃園縣之解集合數 29
6.2 不可分割區 33
6.2.1 台中市之不可分割區 33
6.2.2 桃園縣之不可分割區 36
6.3 形狀完整性之檢查 43
6.4 代入過去選舉結果 50

第七章 問題討論 62
7.1 選區形狀對連接性的影響 62
7.2 形狀完整性的評估方式 62
7.3 選票差距 63

第八章 結論 66
8.1 結論 66
8.2 未來發展 67

參考文獻 69
附錄一 70
附錄二 71






圖目錄

圖 1.1 傑利蠑螈之現象 3
圖 2.1 矩形劃分法產生之選區 6
圖 2.2 砌磚法產生之選區 8
圖 3.1 人口比例二分法產生的破碎選區 11
圖 3.2 滿足人口均等與連接性的選區 11
圖 3.3 最小包圍矩形 13
圖 3.4 最小包圍矩形加入座標轉換及旋轉 13
圖 3.5 利用凸包來評估選區的使用效率 13
圖 3.6 最小外接圓形 14
圖 3.7 台中市的6個村里 15
圖 3.8 人口比例二分法產生的選區 15
圖 4.1 人口比例二分法劃分之選區 20
圖 4.2 人口比例二分法多重劃分之選區 20
圖 4.3 飛地經第二階段劃分後 21
圖 4.4 飛地經第三階段劃分後 21
圖 5.1 系統架構圖 22
圖 6.1 台中市二級行政區圖 26
圖 6.2 台中市2:1劃分,人口誤差0.1%,滿足連接性檢查之解 27
圖 6.3 台中市1:1劃分,人口誤差0.1%,滿足連接性檢查之解 28
圖 6.4 桃園縣二級行政區圖 29
圖 6.5 桃園縣5:1劃分,人口誤差0.01%,滿足連接性檢查之解 30
圖 6.6 桃園縣4:1劃分,人口誤差0.01%,滿足連接性檢查之解 31
圖 6.7 桃園縣3:1劃分,人口誤差0.01%,滿足連接性檢查之解 32
圖 6.8 中選會在台中市之選區劃分 33
圖 6.9 台中市之不可分割區 35
圖 6.10 北區做橫向砌磚法 35
圖 6.11 北區做橫向砌磚法之後做1:1劃分,人口誤差0.01%之解 36
圖 6.12 桃園縣之二級行政區及桃園縣之不可分割區 37
圖 6.13 桃園縣補足人口後產生之三個選區 39
圖 6.14 桃園市橫向砌磚法後產生之四個選區 40
圖 6.15 桃園市砌磚法之後做1:1劃分,人口誤差1%之解 41
圖 6.16 桃園市及八德市縱向砌磚法後產生之四個選區 42

圖 6.17 桃園市和八德市縱向砌磚法之後做1:1劃分,人口誤差1%之解 43
圖 6.18 實驗1人口誤差0.1%,凸包面積比70%之解 45
圖 6.19 實驗1兩階段形狀完整性檢查之解 46
圖 6.20 實驗2兩階段形狀完整性檢查之解 48
圖 6.21 實驗3兩階段形狀完整性檢查之解 50
圖 6.22 中選會與實驗1的5個劃分方式 51
圖 6.23 中選會與實驗2的5個劃分方式 55
圖 6.24 中選會與實驗3的5個劃分方式 59
圖 7.1 台中市2:1劃分,滿足連接性檢查之解 62
圖 7.2 凸包面積比為70%而最小外接圓形面積比為50%的情況 63





























表目錄

表 6.1 台中市在2:1劃分之下找到的解數目 27
表 6.2 台中市在1:1劃分之下找到的解數目 28
表 6.3 桃園縣在5:1劃分之下找到的解數目 30
表 6.4 桃園縣在4:1劃分之下找到的解數目 31
表 6.5 桃園縣在3:1劃分之下找到的解數目 32
表 6.6 台中市二級行政區人口數目表 34
表 6.7 中選會在台中市之選區劃分的人口資料及人口誤差百分比 34
表 6.8 北區做橫向砌磚法之後做1:1劃分的解數目 36
表 6.9 桃園縣二級行政區人口數目表 37
表 6.10 桃園縣不可分割區的人口資料及人口誤差百分比 38
表 6.11 桃園市橫向砌磚法之後做1:1劃分的解數目 40
表 6.12 桃園市和八德市縱向砌磚法之後做1:1劃分的解數目 42
表 6.13 三個實驗之內容表 44
表 6.14 實驗1經凸包面積比檢查的解數目 44
表 6.15 實驗1兩階段形狀完整性檢查的解數目 45
表 6.16 實驗2經凸包面積比檢查之解數目 46
表 6.17 實驗2兩階段形狀完整性檢查的解數目 47
表 6.18 實驗3經凸包面積比檢查之解數目 48
表 6.19 實驗3兩階段形狀完整性檢查的解數目 49
表 6.20 實驗1台中市各選區大致涵蓋之二級行政區 52
表 6.21 中選會與實驗1的5個劃分方式代入第六屆立委選舉結果 52
表 6.22 中選會與實驗1的5個劃分方式代入第七屆立委選舉結果 53
表 6.23 實驗2桃園縣各選區大致涵蓋之二級行政區 55
表 6.24 中選會與實驗2的5個劃分方式代入第六屆立委選舉結果 56
表 6.25 中選會與實驗2的5個劃分方式代入第七屆立委選舉結果 57
表 6.26 實驗3桃園縣各選區大致涵蓋之二級行政區 59
表 6.27 中選會與實驗3的5個劃分方式代入第六屆立委選舉結果 60
表 6.28 中選會與實驗3的5個劃分方式代入第七屆立委選舉結果 61
表 7.1 台中市第六屆選票分析 64
表 7.2 台中市第七屆選票分析 64
表 7.3 桃園縣第六屆選票分析 65
表 7.4 桃園縣第七屆選票分析 65
[1] 李俊瑩,「應用基因演算法重劃選區」,國立政治大學資訊科學學系碩士論文,民國95年9月。
[2] 何瑁鎧、李俊瑩、劉克壙與游清鑫,「選區重劃之分析與探討」,第十一屆人工智慧與應用研討會,高雄,民國94年12月。
[3] 謝相慶,「我國第7屆立法委員單一名額選舉區界線劃分之決定過程與影響因素分析」,2007年台灣政治學會年會暨學術研討會,民國96年11月。
[4] 謝長紘,「計算幾何學在選區劃分之分析與應用」,國立政治大學資訊科學學系碩士論文,民國97年10月。
[5] Gerry E., “The Gerry-mander,” Boston Gazette, 1812.
[6] Harris, Curtis C. ,Jr., “ Scientific Method of Districting,” Behavioral Science , 1964.
[7] Kaiser, H. F., “A Measure of the Population Quality of Legislative Apportionment,” American Political Science Review, Vol. 62, No.1, pp208-215, 1968.
[8] Hess, S., Weaver, J., Siegfeldt, H., Whelan, J., and Zitlau, P., “Nonpartisan Political Redistricting by Computer,” Operations Research 13, 1965.
[9] Helbig, R.E., Patrick O.K., and Robert, R.R. Roediger., “Political Redistricting By Computer,” Comm. ACM, Vol. 15, pp.735–741, 1972.
[10] Leach, Stephen P. and Abraham Kandel., “Expert Systems In Government: A Look At The Redistricting Problem,” Washington University, Communications of the ACM, Vol. 15, pp.8, 1972.
[11] Corman, T. H ., Charless, E.L., Ronald, L.R., and Clifford, S., “Introduction to
Algorithms,” Second Edition. MIT Press, 2001.
[12] The ResDistricting Game, http://www.redistrictinggame.org/
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top