作者howay0516 (小浩浩)
看板Programming
標題[問題] 這該用什麼演算法解題最便利呢？
時間Thu Jun 1 09:30:57 2006
選區重劃
1. 問題：假設村里為最小切割單元，找出10個分割結果，將台南市的232個村里，劃分成2個區域，使得
(a) 每個區域的人口數大致相同，
(b) 每個區域中，所有的里相互連接。
2. 人口大致相同表示人口誤差在指定之範圍之內，即誤差小於 d %。
(a) 台南市總人口數約為75萬5千人，分成2個區域，平均人口約在37~38萬人之間。
(b) 如誤差小於 5%，則人口約在35 ~ 40萬人之間大約都可以接受。
(c) 輸入資料中包含每個里的人口數(每個里的識別碼與人口數)。
3. 所有的里相互連接：
(a) 輸入資料中包含232個里的相鄰關係(adjacency relationship)。
(b) one relation per row.
我想要知道 用什麼演算法解此題會最便利？
謝謝願意回答的大大們^^
以及複雜度分析^^
想要知道大家的看法
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 218.161.16.124
1F：推 qrtt1:GA 06/01 11:18
2F：推 PRAM:用旅行推銷員解法 06/01 22:45
3F：推 howay0516:什麼是旅行推銷員解法？ 06/02 09:44
4F：推 anpig:自己去查吧.... 06/02 12:15
5F：推 hellgod:SA 06/02 14:50
6F：→ peyton87:第一題用 k-means 可得答案？140.124.181.123 07/11 11:33