| 求解最小覆盖问题的快速近似算法的进一步研究 |
| |
| 引用本文： | 宋恩民,刘宏.求解最小覆盖问题的快速近似算法的进一步研究[J].华中科技大学学报(自然科学版),1994(10). |
| |
| 作者姓名： | 宋恩民 刘宏 |
| |
| 作者单位： | 武汉无线电工业学校，华中理工大学计算机科学与工程系 |
| |
| 摘 要： | 分析了已有求覆盖平面上给定的若干个点的尽可能小的圆的问题的算法。给出了一个新的求解最小覆盖问题的算法，其计算时间复杂度为平面上给定的点数量的线性函数，该算法已编程实现，通过几万例随机算例的实际计算比较，表明算法所得结果的平均精度比已有的各种快速近似算法所得的精度要高，而且具体每例所需的计算时间均比已有快速近似算法对应的计算时间要短。
|
| 关 键 词： | 最小覆盖问题，计算时间复杂度，精度，算法 |
More on an Approximate Fast Algorithm for Solving Minimum Covering Problems |
| |
| Song Enmin Dept.of Computer Sci.& Engin,HUSTWuhan ,China.,Liu Hong.More on an Approximate Fast Algorithm for Solving Minimum Covering Problems[J].JOURNAL OF HUAZHONG UNIVERSITY OF SCIENCE AND TECHNOLOGY.NATURE SCIENCE,1994(10). |
| |
| Authors: | Song Enmin Deptof Computer Sci& Engin HUSTWuhan China Liu Hong |
| |
| Institution: | Song Enmin Dept.of Computer Sci.& Engin,HUSTWuhan 430074,China.,Liu Hong |
| |
| Abstract: | The famous problem of finding a smallest circle to cover a given number of points on aplane(FSCC)is studied.Existing algorithms are discussed and a new one for solving FSCCis given,The computing complexity of this algorithm is a linear function of the number ofthe given points;This algorithm has been programmed and used for the computation for tensof thousands of random examples,It is shown that the average accuracy of results obtainedwith this algorithm is better than those given by currently used algorithms. |
| |
| Keywords: | minimum covering problem computing complexity accuracy algorithm |
| 本文献已被 CNKI 等数据库收录！ |
