作者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