Loading...
|
Please use this identifier to cite or link to this item:
https://nccur.lib.nccu.edu.tw/handle/140.119/32687
|
| Title: | 計算幾何學在選區劃分上之分析與應用
Electoral Redistricting using Computational Geometry |
| Authors: | 謝長紘
Hsieh, Chang Hung |
| Contributors: | 何瑁鎧
Hor, Maw Kae
謝長紘
Hsieh, Chang Hung |
| Keywords: | 選區劃分
人工智慧
選舉制度
計算幾何學
動態規劃
Electoral Redistricting
Artificial Intelligence
Computational Geometry
Dynamic programming
election regulations |
| Date: | 2008 |
| Issue Date: | 2009-09-17 14:03:42 (UTC+8) |
| Abstract: | 選舉是實行民主政治最有效的方法之一，而選區劃分的方式將直接或間接的影響投票結果與民主政治理念的施行。
然而在選舉法規或行政區域發生變動時，舊有的選區劃分方式需要隨之調整。而傳統人工的方式具有許多缺點，如：耗費人力資源、人口分配不均、難以兼顧形狀及行政區完整等等。若每次行政區域發生變動，都需要重新劃分，將花費許多不必要的人力、物力及時間，因此利用電腦以完成自動劃分的技術逐漸受到重視。
本論文中我們打破現有的政治與人文鴻溝，嘗試以系統化的方法對選區劃分作全面性的查驗。我們利用計算幾何學的特性與人工智慧搜尋的技巧，儘量找出可能的劃分方式再進行評估。我們依據中選會的建議採用村裡為劃分之最小行政區域，從數以十萬計之合理解中，根據形狀等客觀條件篩選出較佳之劃分方式，進而將歷史投票行為加入考量，以對篩選出的劃分方式作進一步評估與分析。
實作中我們以台南市為對象，在不同的人口限制及形狀條件下，分別比較所能找到的合理解數目。同時選出一部分的劃分方式，和中選會的劃分方式比較，結果顯示我們的方法可以全面性的分析選區劃分，不同的劃分方式可能產生不同的選舉結果。
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. |
| Reference: | [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 |
| Description: | 碩士
國立政治大學
資訊科學學系
94753035
97 |
| Source URI: | http://thesis.lib.nccu.edu.tw/record/#G0094753035 |
| Data Type: | thesis |
| Appears in Collections: | [資訊科學系] 學位論文
|
All items in 政大典藏 are protected by copyright, with all rights reserved.
|
