Algorithm 版 (精华区)

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

  问题是这样的：给定平面上一系列的点，再从中找出一系列的点，然后对
这些点找其邻域，其中邻域的大小是固定的，要求这样做后能包含所有的点
并且使得覆盖整个点的邻域数尽可能的少，邻域中的点可以相互重复，但最
开始用来生成邻域的点却不能被其它领域所包含。
  我是这样做的。首先，随机找一个点，检查该点是否已被用于生成邻域，
然后找其邻域，并检查邻域中的点被用于生成邻域，如果都不冲突的话，就
生成了一个邻域，如果冲突，就再重新找邻域。大体思路是这样的，实现中
也加了一些防止死循环的措施，虽然最后能够找到，但耗费了大量的机时。
有一次点数选多了，就运行了将近2个小时，如果不是坚信不会陷入死循环，
也许中途就终止了。
  显然我的算法有问题，但一时又想不出什么好的算法，所以，我想请教一
下大家，对于我这个问题到底有什么好的算法，希望能够得到你的帮助！

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

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