计算机工程与应用
計算機工程與應用
계산궤공정여응용
COMPUTER ENGINEERING AND APPLICATIONS
2013年
17期
15-17,72
,共4页
集合覆盖%近似算法%0-1规划%对偶规划%线性交互式通用优化器(LINGO)
集閤覆蓋%近似算法%0-1規劃%對偶規劃%線性交互式通用優化器(LINGO)
집합복개%근사산법%0-1규화%대우규화%선성교호식통용우화기(LINGO)
set cover%approximation algorithm%0-1 program%dual program%Linear Interactive and General Optimizer(LINGO)
集合覆盖问题在网络设计领域中有着良好的应用背景，但它在算法复杂性上却是NP-困难问题。建立了集合覆盖问题的0-1规划模型，给出了源于贪心思想的近似算法，并从原始-对偶规划的角度进行了证明，基于LINGO软件的传感器网络最优设计案例验证了模型的正确性和算法的有效性。
集閤覆蓋問題在網絡設計領域中有著良好的應用揹景，但它在算法複雜性上卻是NP-睏難問題。建立瞭集閤覆蓋問題的0-1規劃模型，給齣瞭源于貪心思想的近似算法，併從原始-對偶規劃的角度進行瞭證明，基于LINGO軟件的傳感器網絡最優設計案例驗證瞭模型的正確性和算法的有效性。
집합복개문제재망락설계영역중유착량호적응용배경，단타재산법복잡성상각시NP-곤난문제。건립료집합복개문제적0-1규화모형，급출료원우탐심사상적근사산법，병종원시-대우규화적각도진행료증명，기우LINGO연건적전감기망락최우설계안례험증료모형적정학성화산법적유효성。
The set cover problem has favourable applications in areas of network design, but it is NP-hard in computational com-plexity. A 0-1 program model is formulated for the set cover problem. An approximation algorithm deriving from greedy idea is put forward, and is proved from the angle of primal-dual program. A case study of sensor network optimal design based on LINGO software demonstrates correctness of the model and effectiveness of the algorithm.
