计算机研究与发展
計算機研究與髮展
계산궤연구여발전
JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT
2007年
5期
790-797
,共8页
设施定位%计算复杂性%集合覆盖%近似算法%局部搜索
設施定位%計算複雜性%集閤覆蓋%近似算法%跼部搜索
설시정위%계산복잡성%집합복개%근사산법%국부수색
设施定位问题即UFL问题是NP-hard的组合优化问题,是聚类问题领域的热点问题之一,在数据挖掘和分类识别方面有着重要应用.多年来其近似算法研究一直是计算机科学工作者关注的焦点,然而现有研究结果大多关于Metric空间,一般距离空间中该问题结果始终未见.针对最大连接费用至多是最小连接费用ω＞1倍的一般距离空间中设施定位问题,简称一般设施定位问题,借助集合覆盖问题,利用问题归约方法证明其不存在近似性能比小于1.243+0.316ln(ω-1)的多项式时间近似算法,除非NPDTIME(nO(log log n));设计了一般设施定位问题的局部搜索算法,证明算法近似性能比是(1+ω)/α,ω＞1,1≤α≤2.仿真实验表明,一般设施定位问题局部搜索算法的求解质量极高;通过实验进一步研究了该算法并给出了改进方法.
設施定位問題即UFL問題是NP-hard的組閤優化問題,是聚類問題領域的熱點問題之一,在數據挖掘和分類識彆方麵有著重要應用.多年來其近似算法研究一直是計算機科學工作者關註的焦點,然而現有研究結果大多關于Metric空間,一般距離空間中該問題結果始終未見.針對最大連接費用至多是最小連接費用ω＞1倍的一般距離空間中設施定位問題,簡稱一般設施定位問題,藉助集閤覆蓋問題,利用問題歸約方法證明其不存在近似性能比小于1.243+0.316ln(ω-1)的多項式時間近似算法,除非NPDTIME(nO(log log n));設計瞭一般設施定位問題的跼部搜索算法,證明算法近似性能比是(1+ω)/α,ω＞1,1≤α≤2.倣真實驗錶明,一般設施定位問題跼部搜索算法的求解質量極高;通過實驗進一步研究瞭該算法併給齣瞭改進方法.
설시정위문제즉UFL문제시NP-hard적조합우화문제,시취류문제영역적열점문제지일,재수거알굴화분류식별방면유착중요응용.다년래기근사산법연구일직시계산궤과학공작자관주적초점,연이현유연구결과대다관우Metric공간,일반거리공간중해문제결과시종미견.침대최대련접비용지다시최소련접비용ω＞1배적일반거리공간중설시정위문제,간칭일반설시정위문제,차조집합복개문제,이용문제귀약방법증명기불존재근사성능비소우1.243+0.316ln(ω-1)적다항식시간근사산법,제비NPDTIME(nO(log log n));설계료일반설시정위문제적국부수색산법,증명산법근사성능비시(1+ω)/α,ω＞1,1≤α≤2.방진실험표명,일반설시정위문제국부수색산법적구해질량겁고;통과실험진일보연구료해산법병급출료개진방법.
