|本期目录/Table of Contents|

[1]江世宏.闭区间有限覆盖的算法[J].武汉工程大学学报,2014,(04):76-78.[doi:103969/jissn16742869201404016]
　JIANG Shi hong.Implementation of algorithm covering closed intervals with finite lines[J].Journal of Wuhan Institute of Technology,2014,(04):76-78.[doi:103969/jissn16742869201404016]
点击复制

闭区间有限覆盖的算法(/HTML)
分享到：

《武汉工程大学学报》[ISSN:1674-2869/CN:42-1779/TQ]

卷:
期数:
2014年04期
页码:
76-78
栏目:
机电与信息工程
出版日期:
2014-04-30

文章信息/Info

Title:
Implementation of algorithm covering closed intervals with finite lines
文章编号:
16742869(2014)04007603
作者:
江世宏
武汉工程大学理学院,湖北 武汉 430205
Author(s):
JIANG Shihong
School of Science,Wuhan Institute of Technology,Wuhan 430205，China
关键词:
闭区间; 覆盖; 贪心法
Keywords:
closed interval; coverage; greedy method
分类号:
TP 391.41
DOI:
103969/jissn16742869201404016
文献标志码:
A
摘要:
许多经济、管理、军事、计算机和数学领域中的实际问题，可以抽象成为闭区间（或闭区域）的有限覆盖问题.为了获得这类问题在某种优化约束条件下的局部最优解，需要设计计算机求解算法.基于贪心法原理，对m个闭区间，用n（m>n）条线段去覆盖，在覆盖线段总长最小的条件下，给出了如何选取覆盖线段的算法；给出了一个开区间集S是否覆盖闭区间［a,b］的判定，在可以覆盖的条件下，从中挑选具有最小个数的开区间使之仍能覆盖闭区间［a,b］的算法.为了检验所给算法的正确性，进行了计算机模拟测试.
Abstract:
Many problems in fields of economic,management,military,computer and mathematics can be described by covering closed intervals (or closed areas) with finite lines.To obtain a local optimal solution of the problem subjected to constraints,it is necessary to design a computer algorithm.Based on the principle of greedy method,an algorithm selecting n line segments with a minimal total length covering m(m>n) closed intervals was proposed,then it was extended to cover a closed interval with a set of opened intervals;a generalized algorithm selecting the fewest opened intervals to cover the given closed intervals was put forward.Finally,computer simulation was carried out to test the validity of these algorithms.

参考文献/References:

［1］郭改慧，李兵方.有限覆盖定理的应用\[J\].牡丹江大学学报，2013,22(10):103104.［2］关金玉,徐永春,祁建芳.用完全覆盖证明实数系中若干定理［J］.河北北方学院学报:自然科学版,2006,22(3):67.GUAN Jinyu,XU Yongchun,QI Jianfang.To prove several theorems in real number field by using full covering theorem［J］.Journal of Hebei North University:Natural Science Edition,2006,22(3):67.（in Chinese）［3］常友渠,肖贵元,曾敏.贪心算法的探讨与研究［J］.重庆电力高等专科学校学报,2008,13(3):4142，47.CHANG Youqu,XIAO Guiyuan,ZENG Min.Exploration of greedy algorithm［J］.Journal of Chongqing Electric Power College,2008,13(3):4142，47.（in Chinese） ［4］崔鹏，刘红静.测试集问题的综合覆盖贪心算法的深入近似［J］.软件学报，2006，17（7）：14941500.CUI Peng,LIU Hongjing.Deep approximation of set cover greedy algorithm for test set［J］.Journal of Software,2006,17(7):14941500.(in Chinese)

相似文献/References:

备注/Memo

备注/Memo:
收稿日期：20140317基金项目：国家教学研究项目（FIB070335A210）作者简介：江世宏（1958），男，湖北仙桃人，硕士，副教授．研究方向：计算数学、现代教育技术应用.
更新日期/Last Update: 2014-05-15