给定一棵无向树，其无权边具有 N 个顶点和 N-1 个边，并且数量为 K，找到 K 个节点，以便树中的每个节点与 K 个节点中的至少一个节点的距离在 S 范围内。另外，S 必须是尽可能小的 S，因此，如果 S'
我尝试解决这个问题，但是，我觉得我的解决方案不是很快。
我的解决方案：
设x=1
查找距每个节点 x 距离的节点
设距离内节点最多的节点为 K 个节点之一。
重新计算每个节点，同时不计算已经覆盖的节点。
这样做直到找到 K 个 K 个节点。然后，如果每个节点都被覆盖，我们就完成了，否则增加 x。
这个问题称为 p-center，你可以在网上找到几篇关于它的论文，例如this。对于一般图来说，它确实是 NP，但是对于树来说，它是多项式，无论是加权的还是未加权的。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
