(3.236.214.19) 您好!臺灣時間:2021/05/10 04:41
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:謝長紘
研究生(外文):Hsieh, Chang Hung
論文名稱:計算幾何學在選區劃分上之分析與應用
論文名稱(外文):Electoral Redistricting using Computational Geometry
指導教授:何瑁鎧何瑁鎧引用關係
指導教授(外文):Hor, Maw Kae
學位類別:碩士
校院名稱:國立政治大學
系所名稱:資訊科學學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2008
畢業學年度:97
語文別:中文
論文頁數:53
中文關鍵詞:選區劃分人工智慧選舉制度計算幾何學動態規劃
外文關鍵詞:Electoral RedistrictingArtificial IntelligenceComputational GeometryDynamic programmingelection regulations
相關次數:
  • 被引用被引用:7
  • 點閱點閱:123
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
選舉是實行民主政治最有效的方法之一,而選區劃分的方式將直接或間接的影響投票結果與民主政治理念的施行。

然而在選舉法規或行政區域發生變動時,舊有的選區劃分方式需要隨之調整。而傳統人工的方式具有許多缺點,如:耗費人力資源、人口分配不均、難以兼顧形狀及行政區完整等等。若每次行政區域發生變動,都需要重新劃分,將花費許多不必要的人力、物力及時間,因此利用電腦以完成自動劃分的技術逐漸受到重視。

本論文中我們打破現有的政治與人文鴻溝,嘗試以系統化的方法對選區劃分作全面性的查驗。我們利用計算幾何學的特性與人工智慧搜尋的技巧,儘量找出可能的劃分方式再進行評估。我們依據中選會的建議採用村裡為劃分之最小行政區域,從數以十萬計之合理解中,根據形狀等客觀條件篩選出較佳之劃分方式,進而將歷史投票行為加入考量,以對篩選出的劃分方式作進一步評估與分析。

實作中我們以台南市為對象,在不同的人口限制及形狀條件下,分別比較所能找到的合理解數目。同時選出一部分的劃分方式,和中選會的劃分方式比較,結果顯示我們的方法可以全面性的分析選區劃分,不同的劃分方式可能產生不同的選舉結果。
Election is one of the most effective way of conducting democratic politics, and mean of electoral redistricting shall post effect, either directly or indirectly, on electoral outcome as well as delivering ideas of democratic politics.

As election regulations or administrational districts experience alterations, the present electoral districting is forcefully accompanied with adjustments. Electoral redistricting using traditional human labor works reveal several flaws such as: human resource wastage, uneven population distributions, hard to maintain shape contiguity and compactness, as well as the completeness of administration districts. Every single alteration experience in administration district requires redistribution, thus expensing on unnecessary human labor, resources and time. As such, it had brought great attention on techniques of automatic redistribution by means of modern computer technologies.

In this thesis, we shall breakthrough a giant gap between politics and humanity; conduct a thorough examination on systematic approach on electoral redistricting. We are going to utilize characteristics of computational geometry and artificial intelligence searching techniques to find out every conceivable means of redistricting then evaluation the performance of them. By recommendation of Central Election Commission (hence CEM), we will adopt the classification of township as basic unit of administrational district, from counts of thousand adequate explanations, by objective factors of shape accordance and others, select the better means of redistricting methods, and afterward put into concern of historical voting behavior, conduct a further evaluation and analysis upon chosen redistricting method.

In actual practices we had selected Tainan City as the experiment target, under different population limitations and factors of form, compare the searchable numbers of decent explanation respectively. We choose some redistricting outcomes, and put into comparison with redistricting method of the CEM. The results indicated our approach is able to conduct a thorough redistricting analysis, as well as more diversified comparing to CEM's outcome.

The result of this experiment also reveals different election outcome with adoption of different redistricting methods.
第一章 緒論 1
1.1 選區劃分之原則 1
1.2 選區劃分對投票結果之影響 2
1.3 自動化的劃分方式 4
1.4 問題描述 5
第二章 相關研究 7
2.1 砌磚法 7
2.2 鄉村包圍城市法 7
2.3 模擬退火法 7
2.4 統計物理 8
2.5 基因演算法 8
第三章 系統說明 10
3.1選區之圖示法 10
3.2 系統架構 12
3.2.1資料前處理 13
3.2.2 人口二分劃法 13
3.2.3 連接性檢查 13
3.2.4 形狀完整性檢查 14
3.2.5 套用投票統計結果 14
第四章 選區劃分演算法 15
4.1 人口均等劃分 15
4.2 相鄰關係 18
4.3 選區形狀的完整性 19
4.3.1 最小包圍矩形之長寬比 19
4.3.2最小包圍矩形之面積比 20
4.3.3 凸包之面積比 20
4.3.4 凸包之周長比 21
4.4歷史投票行為之影響 21
第五章 實驗結果 22
5.1 滿足人口條件的解數目 23
5.2 滿足連接性的解 25
5.3 滿足形狀完整的解 25
5.3.1 滿足完整性的解數目 26
5.3.2 滿足完整性的解形狀 27
5.4 對選舉結果之影響 31
第六章 問題討論 35
6.1等分劃法的改進 35
6.1.1 連接比例的提高 35
6.1.2形狀完整比例之提高 37
6.2 村裡中心點的計算 38
6.3 截斷點所代表的意義 39
第七章 結論 41
7.1 結論 41
7.2 未來發展 41
參考文獻 43
附錄一 未能滿足連接性的解 45
[1]. 中央選舉委員會, 第7屆立法委員直轄市縣市選舉區劃分公聽會會議資料, 2006年3月28日。
[2]. 李俊瑩, 應用基因演算法重劃選區, 碩士論文, 國立政治大學, 台灣, 台北, 2006年9月。
[3]. 何瑁鎧、劉克壙、李俊瑩、游清鑫, "選區重劃之分析與討論", 第十屆人工智慧與應用研討會, 2005年12月。
[4]. 徐永明, "單一選區兩票制政治衝擊的模擬", 新世紀智庫論壇,17期, 頁6-15, 2002年3月。
[5]. 鄒忠毅、李定國, "簡介導引模擬退火法及其應用", 物理雙月刊(二十四卷二期) , 頁307-319, 2002年4月。
[6]. 鄒忠毅、李世炳, "Potts模型與傑利蠑螈:將統計物理方法運用在選區劃分問題上", 2006中華民國物理學會年會暨研究成果發表會, 2006年1月。
[7]. 謝相慶, "我國第7屆立法委員單一名額選舉區界線劃分之決定過程與影響因素分析", 2007年台灣政治學會年會暨學術研討會, 2007年11月。
[8]. Arend Lijphart, "Democracies: Patterns of Majoritarian and Consensus Government in Twenty-One Countries", 陳坤森(譯), 當代民主類型與政治(桂冠,1993年), 頁161-179。
[9]. Robert E. Helbig, Patrick K. Orr, and Robert R. "Roediger,Political Redistricting by Computer", Communications of the ACM, August 1972.
[10]. Harris, Curtis C. "A Scientific Method of Districting", June 1964, Behavioral Science 9:219-225
[11]. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. Section 22.3: Depth-first search, pp.540–549. MIT Press and McGraw-Hill, 2001
[12]. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. Chapter17: Greedy Algorithms, pp.370–404. MIT Press and McGraw-Hill, 2001
[13]. http://en.wikipedia.org/wiki/Gerrymandering, February 2008
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔