| dc.contributor.advisor | 何瑁鎧 | zh_TW |
| dc.contributor.advisor | Hor, Maw Kae | en_US |
| dc.contributor.author (Authors) | 謝長紘 | zh_TW |
| dc.contributor.author (Authors) | Hsieh, Chang Hung | en_US |
| dc.creator (作者) | 謝長紘 | zh_TW |
| dc.creator (作者) | Hsieh, Chang Hung | en_US |
| dc.date (日期) | 2008 | en_US |
| dc.date.accessioned | 17-Sep-2009 14:03:42 (UTC+8) | - |
| dc.date.available | 17-Sep-2009 14:03:42 (UTC+8) | - |
| dc.date.issued (上傳時間) | 17-Sep-2009 14:03:42 (UTC+8) | - |
| dc.identifier (Other Identifiers) | G0094753035 | en_US |
| dc.identifier.uri (URI) | https://nccur.lib.nccu.edu.tw/handle/140.119/32687 | - |
| dc.description (描述) | 碩士 | zh_TW |
| dc.description (描述) | 國立政治大學 | zh_TW |
| dc.description (描述) | 資訊科學學系 | zh_TW |
| dc.description (描述) | 94753035 | zh_TW |
| dc.description (描述) | 97 | zh_TW |
| dc.description.abstract (摘要) | 選舉是實行民主政治最有效的方法之一，而選區劃分的方式將直接或間接的影響投票結果與民主政治理念的施行。然而在選舉法規或行政區域發生變動時，舊有的選區劃分方式需要隨之調整。而傳統人工的方式具有許多缺點，如：耗費人力資源、人口分配不均、難以兼顧形狀及行政區完整等等。若每次行政區域發生變動，都需要重新劃分，將花費許多不必要的人力、物力及時間，因此利用電腦以完成自動劃分的技術逐漸受到重視。本論文中我們打破現有的政治與人文鴻溝，嘗試以系統化的方法對選區劃分作全面性的查驗。我們利用計算幾何學的特性與人工智慧搜尋的技巧，儘量找出可能的劃分方式再進行評估。我們依據中選會的建議採用村裡為劃分之最小行政區域，從數以十萬計之合理解中，根據形狀等客觀條件篩選出較佳之劃分方式，進而將歷史投票行為加入考量，以對篩選出的劃分方式作進一步評估與分析。實作中我們以台南市為對象，在不同的人口限制及形狀條件下，分別比較所能找到的合理解數目。同時選出一部分的劃分方式，和中選會的劃分方式比較，結果顯示我們的方法可以全面性的分析選區劃分，不同的劃分方式可能產生不同的選舉結果。 | zh_TW |
| dc.description.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. | en_US |
| dc.description.tableofcontents | 第一章 緒論 11.1 選區劃分之原則 11.2 選區劃分對投票結果之影響 21.3 自動化的劃分方式 41.4 問題描述 5第二章 相關研究 72.1 砌磚法 72.2 鄉村包圍城市法 72.3 模擬退火法 72.4 統計物理 82.5 基因演算法 8第三章 系統說明 103.1選區之圖示法 103.2 系統架構 123.2.1資料前處理 133.2.2 人口二分劃法 133.2.3 連接性檢查 133.2.4 形狀完整性檢查 143.2.5 套用投票統計結果 14第四章 選區劃分演算法 154.1 人口均等劃分 154.2 相鄰關係 184.3 選區形狀的完整性 194.3.1 最小包圍矩形之長寬比 194.3.2最小包圍矩形之面積比 204.3.3 凸包之面積比 204.3.4 凸包之周長比 214.4歷史投票行為之影響 21第五章 實驗結果 225.1 滿足人口條件的解數目 235.2 滿足連接性的解 255.3 滿足形狀完整的解 255.3.1 滿足完整性的解數目 265.3.2 滿足完整性的解形狀 275.4 對選舉結果之影響 31第六章 問題討論 356.1等分劃法的改進 356.1.1 連接比例的提高 356.1.2形狀完整比例之提高 376.2 村裡中心點的計算 386.3 截斷點所代表的意義 39第七章 結論 417.1 結論 417.2 未來發展 41參考文獻 43附錄一 未能滿足連接性的解 45 | zh_TW |
| dc.format.extent | 94049 bytes | - |
| dc.format.extent | 117060 bytes | - |
| dc.format.extent | 118456 bytes | - |
| dc.format.extent | 127184 bytes | - |
| dc.format.extent | 343447 bytes | - |
| dc.format.extent | 134240 bytes | - |
| dc.format.extent | 452403 bytes | - |
| dc.format.extent | 607682 bytes | - |
| dc.format.extent | 1413740 bytes | - |
| dc.format.extent | 655100 bytes | - |
| dc.format.extent | 125671 bytes | - |
| dc.format.extent | 115808 bytes | - |
| dc.format.extent | 1453559 bytes | - |
| dc.format.mimetype | application/pdf | - |
| dc.format.mimetype | application/pdf | - |
| dc.format.mimetype | application/pdf | - |
| dc.format.mimetype | application/pdf | - |
| dc.format.mimetype | application/pdf | - |
| dc.format.mimetype | application/pdf | - |
| dc.format.mimetype | application/pdf | - |
| dc.format.mimetype | application/pdf | - |
| dc.format.mimetype | application/pdf | - |
| dc.format.mimetype | application/pdf | - |
| dc.format.mimetype | application/pdf | - |
| dc.format.mimetype | application/pdf | - |
| dc.format.mimetype | application/pdf | - |
| dc.language.iso | en_US | - |
| dc.source.uri (資料來源) | http://thesis.lib.nccu.edu.tw/record/#G0094753035 | en_US |
| dc.subject (關鍵詞) | 選區劃分 | zh_TW |
| dc.subject (關鍵詞) | 人工智慧 | zh_TW |
| dc.subject (關鍵詞) | 選舉制度 | zh_TW |
| dc.subject (關鍵詞) | 計算幾何學 | zh_TW |
| dc.subject (關鍵詞) | 動態規劃 | zh_TW |
| dc.subject (關鍵詞) | Electoral Redistricting | en_US |
| dc.subject (關鍵詞) | Artificial Intelligence | en_US |
| dc.subject (關鍵詞) | Computational Geometry | en_US |
| dc.subject (關鍵詞) | Dynamic programming | en_US |
| dc.subject (關鍵詞) | election regulations | en_US |
| dc.title (題名) | 計算幾何學在選區劃分上之分析與應用 | zh_TW |
| dc.title (題名) | Electoral Redistricting using Computational Geometry | en_US |
| dc.type (資料類型) | thesis | en |
| dc.relation.reference (參考文獻) | [1]. 中央選舉委員會， 第7屆立法委員直轄市縣市選舉區劃分公聽會會議資料， 2006年3月28日。 | zh_TW |
| dc.relation.reference (參考文獻) | [2]. 李俊瑩， 應用基因演算法重劃選區， 碩士論文， 國立政治大學， 台灣， 台北， 2006年9月。 | zh_TW |
| dc.relation.reference (參考文獻) | [3]. 何瑁鎧、劉克壙、李俊瑩、游清鑫， "選區重劃之分析與討論"， 第十屆人工智慧與應用研討會， 2005年12月。 | zh_TW |
| dc.relation.reference (參考文獻) | [4]. 徐永明， "單一選區兩票制政治衝擊的模擬"， 新世紀智庫論壇，17期， 頁6-15， 2002年3月。 | zh_TW |
| dc.relation.reference (參考文獻) | [5]. 鄒忠毅、李定國， "簡介導引模擬退火法及其應用"， 物理雙月刊(二十四卷二期) ， 頁307-319， 2002年4月。 | zh_TW |
| dc.relation.reference (參考文獻) | [6]. 鄒忠毅、李世炳， "Potts模型與傑利蠑螈:將統計物理方法運用在選區劃分問題上"， 2006中華民國物理學會年會暨研究成果發表會， 2006年1月。 | zh_TW |
| dc.relation.reference (參考文獻) | [7]. 謝相慶， "我國第7屆立法委員單一名額選舉區界線劃分之決定過程與影響因素分析"， 2007年台灣政治學會年會暨學術研討會， 2007年11月。 | zh_TW |
| dc.relation.reference (參考文獻) | [8]. Arend Lijphart, "Democracies: Patterns of Majoritarian and Consensus Government in Twenty-One Countries", 陳坤森(譯), 當代民主類型與政治(桂冠,1993年), 頁161-179。 | zh_TW |
| dc.relation.reference (參考文獻) | [9]. Robert E. Helbig, Patrick K. Orr, and Robert R. "Roediger,Political Redistricting by Computer", Communications of the ACM, August 1972. | zh_TW |
| dc.relation.reference (參考文獻) | [10]. Harris, Curtis C. "A Scientific Method of Districting", June 1964, Behavioral Science 9:219-225 | zh_TW |
| dc.relation.reference (參考文獻) | [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 | zh_TW |
| dc.relation.reference (參考文獻) | [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 | zh_TW |
| dc.relation.reference (參考文獻) | [13]. http://en.wikipedia.org/wiki/Gerrymandering, February 2008 | zh_TW |
