V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
letianqiu
V2EX  ›  程序员

请教一个算法题

  •  
  •   letianqiu · 2018-04-02 15:55:21 +08:00 · 1288 次点击
    这是一个创建于 2187 天前的主题,其中的信息可能已经有所发展或是发生改变。
    You are given a map of cities with roads connecting some of them, as well as the length of each road. You have to choose cities in which you will build schools, such that the distance from any city to the nearest city with a school is at most 10 miles, and so that the total number of schools is as small as possible.
    题目要求用贪心找出一个解,并证明这个解并不是最优的。
    第一反应是求 Minimal Spanning Tree,然后在 Tree 上任意取一个 Vertex,建一个学校,然后把这个节点可以覆盖的 Vertices 去掉,重复,直到没有未覆盖的 Vertex。但是想了以下觉得不对,然后又想是不是对每个 Vertex 作为起点做一次 Dijkstra shortest path,然后每做完一次,从起点建学校,逐步覆盖所有的,然后取所有情况下最优的。无论上述哪一种,都觉得有问题。顺便求教最优解应该怎么求。
    3 条回复    2018-04-08 13:08:06 +08:00
    geelaw
        1
    geelaw  
       2018-04-02 15:59:58 +08:00
    考虑一个特殊情况:任意两个直接连接的城市的距离都是 10 miles。此时问题是 minimum dominating set 问题,这是一个 NP-Hard 的问题,因此目前你随便想一个多项式时间的算法都不是最优的。

    一个 naïve 的算法是这样的:随便选一个点建立学校,然后删除所有已经被 cover 住的点。
    letianqiu
        2
    letianqiu  
    OP
       2018-04-02 16:21:46 +08:00
    @geelaw 感谢指出 minimum dominating set 问题。不过 NP-Hard 的表述不准确吧,应该是 NP-Complete。
    geelaw
        3
    geelaw  
       2018-04-08 13:08:06 +08:00
    @letianqiu 一个问题是 NP-complete 自然代表它是 NP-hard。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   998 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 25ms · UTC 20:04 · PVG 04:04 · LAX 13:04 · JFK 16:04
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.