Algorithm 版 (精华区)

发信人: shs (花雨飘), 信区: Algorithm
标  题: Re: 平面点覆盖问题求教
发信站: 哈工大紫丁香 (Sat Sep  9 12:56:54 2000), 转信

既然邻域大小是固定的。你可以得到这样的信息：
  每个点的邻域包含那些点。
这样问题就转换为： 求最小个数子集 它们能覆盖全集。
这样的问题是很难解决的，不过尽可能的少的个数可用贪婪法来做：
  1: 找包含元素最多的子集将之添入覆盖集 。
  2: 在所有剩下的子集中减去刚找出的集合的元素 。
  3: 如果全集还没有被覆盖 GoTo 1
【 在 aijing (秋风掠过山梁) 的大作中提到: 】
:   问题是这样的：给定平面上一系列的点，再从中找出一系列的点，然后对
: 这些点找其邻域，其中邻域的大小是固定的，要求这样做后能包含所有的点
: 并且使得覆盖整个点的邻域数尽可能的少，邻域中的点可以相互重复，但最
: 开始用来生成邻域的点却不能被其它领域所包含。
:   我是这样做的。首先，随机找一个点，检查该点是否已被用于生成邻域，
: 然后找其邻域，并检查邻域中的点被用于生成邻域，如果都不冲突的话，就
: 生成了一个邻域，如果冲突，就再重新找邻域。大体思路是这样的，实现中
: 也加了一些防止死循环的措施，虽然最后能够找到，但耗费了大量的机时。
: 有一次点数选多了，就运行了将近2个小时，如果不是坚信不会陷入死循环，
: 也许中途就终止了。
:   显然我的算法有问题，但一时又想不出什么好的算法，所以，我想请教一
: 下大家，对于我这个问题到底有什么好的算法，希望能够得到你的帮助！
: 

--
※ 来源:　武汉白云黄鹤站 bbs.whnet.edu.cn. [FROM: 202.114.113.240] 
※ 修改:．shs 于 Sep  9 12:54:33 修改本文．[FROM: as.hit.edu.cn]
--
※ 转寄:．武汉白云黄鹤站 bbs.whnet.edu.cn．[FROM: as.hit.edu.cn]

--
☆ 来源:．哈工大紫丁香 bbs.hit.edu.cn．[FROM: shs.bbs@bbs.whnet.ed]