摘要
设欧氏平面上直线L的一侧有n个点的点集N,L上则有一个禁区集合F,现要在L上禁区集合以外找一点p,使得联结N∪{p}的最小网络之长达到最短。文章对这一问题提出了一个O(n2)的近似算法,其性能比为32。
Let L be a straight line in an Euclidean plane, and N be a set of n points on the same side of L, F be a forbidden region in L consisting of some intervals. The problem is to find a point P in L outside F such that the length of the network interconnecting the set N∪｛p｝ is minimized. An O(n^2) approximation algorithm is presented, whose performance ratio is shown to be 32 .
出处
《杭州电子工业学院学报》
2004年第4期6-9,共4页
Journal of Hangzhou Institute of Electronic Engineering
基金
国家自然科学基金(10371028)
浙江省教育厅重点项目(20030622)
关键词
选址问题
最小生成树
分治法
性能比
Location problem
Minimum spanning tree
Divide and Conquer
Performance ratio
