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]
[百宝箱] [返回首页] [上级目录] [根目录] [返回顶部] [刷新] [返回]
Powered by KBS BBS 2.0 (http://dev.kcn.cn)
页面执行时间:2.505毫秒