求解一道信息学竞赛中图的问题！
一张由n个堡垒组成的交通图，任意两个堡垒之间只有一条通行路线。为了确保路线通畅，必须在某些堡垒上建立火力中心。每个火力中心都能够对其相连的所有交通线进行全天候的监控，防止敌人侵略。现在的问题是如何设置火力中心的布局，才能用最少的火力中心控制所有交通路线。
输入：堡垒数n（1<=n<=10000）。以下每行为i，j，表示堡垒i与堡垒j连接。以“0 0”标志结束
求算法！
问题点数：80、回复次数：23Top
1 楼yuequnfan（Canty）回复于 2005-06-12 11:06:32 得分 0
upTop
2 楼mmmcd（超超）回复于 2005-06-12 12:11:37 得分 10
是不是要找最小支配集啊？Top
3 楼mysword（一怒拔剑）回复于 2005-06-12 22:05:31 得分 10
最小覆盖集吧Top
4 楼yuequnfan（Canty）回复于 2005-06-19 09:08:57 得分 0
upTop
5 楼sitanda（yansida）回复于 2005-06-19 09:48:16 得分 0
关注Top
6 楼Zephyrzzz（）回复于 2005-06-19 18:57:50 得分 30
最小覆盖集,由于是图比较特殊,是一棵树,可以用贪心的方法实现.每次寻找一个叶子结点,找出其父亲结点,将其设为中心点.然后将与该中心点连接的所有结点都删去.重复寻找叶子结点的过程,直到所有结点都删去,可以证明,该法所需中心点是最少的.Top
7 楼virm（查无此人）回复于 2005-06-19 23:03:49 得分 0
这个图未必是一棵树，用贪心算法未必能得到最优解
基本上这个问题的最终解是 NP 问题，求较优解倒是容易Top
8 楼Zephyrzzz（）回复于 2005-06-20 10:15:55 得分 0
"任意两个堡垒之间只有一条通行路线"Top
9 楼yuequnfan（Canty）回复于 2005-06-20 13:53:46 得分 0
后来我阅读题目也发现，此题实际上的确应该是一颗树。既然是树，我想我能解决了。
现在是如果"任意两个堡垒之间只有一条通行路线"这句话没有，也就是说是一个图的话，有没有最优解？
请不吝指教Top
10 楼Zephyrzzz（）回复于 2005-06-20 19:32:18 得分 0
任意图则是NP难问题了Top
11 楼minlingtianxia（敏凌天下）回复于 2005-06-25 21:40:29 得分 30
对于任意图问题不知道这样的算法行不行:
事实上我们可以把图的顶点分成两部分,一类是染色的顶点,另一类是不染色的顶点.易知对于不染色的点集中的任意两个顶点都不能有边相连.现在的问题就是去找这样的一个划分.把所有的顶点划成两类.而最优解就是要求那个被染色的集合的元素个数最少.
先构造一对集合A,B.其中A是被染色的点集.构造规则如下:
(1)把第一个顶点放入B.
(2)假定有K个顶点已被划分好,则对于第K+1个顶点,若放入B不与B中其他的顶点冲突,即这个顶点不与B中的任意一个顶点之间有边相连.则放入B,否则放入A.
当然,这样的顶点未必是最优的.但我们现对其做如下修改:
考察B中的每一个顶点,对与B中的某一顶点P,若所有的与P相连的顶点(必在A中),至少有两个顶点与B中的顶点只有一边相连(即B中除P外无顶点与这顶点相连),则把P放入到A中,把与所有与P相连的但不与B中其他任一顶点相连的顶点放到A中,这样可以优化这个解.
依这个规则不断地对解进行优化.直到不能再优化为止.
对于最后的这个解,我不知道是否符合要求,但有一点是肯定的,最优解一定不能再优化,而我不知道不能再优化的解是否是最优的,我没法有数学来证明,但凭直觉这似乎是对的.
请大家发表一下意见,给出反例也欢迎!
Top
12 楼jettylee（要学的还很多~~~）回复于 2005-06-25 21:43:52 得分 0
贪心
每次染色一个度最大的结点
然后去除这个结点和与这个结点有关的任何边
边的另一头的结点的度减一
循环
就是这样会比较慢 n^2级的Top
13 楼minlingtianxia（敏凌天下）回复于 2005-06-25 21:45:30 得分 0
...
则把P放入到A中,把与所有与P相连的但不与B中其他任一顶点相连的顶点放到Ａ中,这样可以优化这个解.
...
更正为：
...
则把P放入到A中,把与所有与P相连的但不与B中其他任一顶点相连的顶点放到B中,这样可以优化这个解.
...
Top
14 楼minlingtianxia（敏凌天下）回复于 2005-06-25 21:52:16 得分 0
to: jettylee(要学的还很多~~~)
你的算法显然错了．反例：一棵深度为３的树，根有５个子女，每个子女又都有一个子女，对于这张图
根虽然度最大，但不必染色．Top
15 楼yuequnfan（Canty）回复于 2005-06-26 09:18:32 得分 0
支持Top
16 楼Zephyrzzz（）回复于 2005-06-26 20:49:12 得分 0
to minlingtianxia(敏凌天下):
说一下你的解法对于完全图的情况.Top
17 楼minlingtianxia（敏凌天下）回复于 2005-06-30 19:25:55 得分 0
to Zephyrzzz() :
对于完全图,按规则构造出的那个解是染色集有N-1个顶点,非染色集则有1个顶点.而且不能再优化了.(这很明显,你可以按规则模仿一下)而事实上最优解的确是这个,因为假如有两个顶点未被染色,由于它是完全图,那么这条边的两个顶点就都未被染色,这个解就不符合!Top
18 楼minlingtianxia（敏凌天下）回复于 2005-06-30 19:51:52 得分 0
...
考察B中的每一个顶点,对与B中的某一顶点P,若所有的与P相连的顶点(必在A中),至少有两个顶点与B中的顶点只有一边相连(即B中除P外无顶点与这顶点相连),则把P放入到A中,把与所有与P相连的但不与B中其他任一顶点相连的顶点放到A中,这样可以优化这个解.
...
对于这里,忘了加上一个条件:"至少有两个顶点与B中的顶点只有一边相连(即B中除P外无顶点与这顶点相连),则把P放入到A中"这里的放入B几个顶点任两点不能有边相连,否则的话放入B后B集合中的顶点就会出现有边相连的两个顶点,而这是不能被允许的.Top
19 楼languagec（各有所求）回复于 2005-07-01 16:33:55 得分 0
20 楼Zephyrzzz（）回复于 2005-07-01 23:00:59 得分 0
。。。。。。你不是说“最优解就是要求那个被染色的集合的元素个数最少”吗？ 后面的“对于完全图,按规则构造出的那个解是染色集有N-1个顶点,非染色集则有1个顶点.而且不能再优化了.”不是矛盾？染色集不是应该只有一个顶点吗？Top
21 楼minlingtianxia（敏凌天下）回复于 2005-07-02 17:06:36 得分 0
可能是我没说清楚,在操作时染色集是确定的,就是A.“最优解就是要求那个被染色的集合的元素个数最少”指的是解与解之间集合A元素之间的比较.而在一个解中,染色集的元素个数可以多于非染色集的个数,因为有时这是必须的.例如在这完全图的情况下,A可以多于B(且是必须的).而如果你拿出其它的解,只要这可行,那这个解的A集(染色集)的元素个数肯定多于N-1.不知道这样说你是否能理解我的意思.Top
22 楼ihsgnep（石头－>信心最重要 努力是王道）回复于 2005-07-03 00:12:21 得分 0
Mark 学习Top
23 楼minlingtianxia（敏凌天下）回复于 2005-07-06 19:11:32 得分 0
up
Top
