武汉工程大学学报
武漢工程大學學報
무한공정대학학보
JOURNAL OF WUHAN INSTITUTE OF TECHNOLOGY
2014年
4期
76-78
,共3页
闭区间%覆盖%贪心法
閉區間%覆蓋%貪心法
폐구간%복개%탐심법
closed interval%coverage%greedy method
许多经济、管理、军事、计算机和数学领域中的实际问题,可以抽象成为闭区间(或闭区域)的有限覆盖问题.为了获得这类问题在某种优化约束条件下的局部最优解,需要设计计算机求解算法.基于贪心法原理,对m个闭区间,用n(m>n)条线段去覆盖,在覆盖线段总长最小的条件下,给出了如何选取覆盖线段的算法;给出了一个开区间集S是否覆盖闭区间[a,b]的判定,在可以覆盖的条件下,从中挑选具有最小个数的开区间使之仍能覆盖闭区间[a,b]的算法.为了检验所给算法的正确性,进行了计算机模拟测试.
許多經濟、管理、軍事、計算機和數學領域中的實際問題,可以抽象成為閉區間(或閉區域)的有限覆蓋問題.為瞭穫得這類問題在某種優化約束條件下的跼部最優解,需要設計計算機求解算法.基于貪心法原理,對m箇閉區間,用n(m>n)條線段去覆蓋,在覆蓋線段總長最小的條件下,給齣瞭如何選取覆蓋線段的算法;給齣瞭一箇開區間集S是否覆蓋閉區間[a,b]的判定,在可以覆蓋的條件下,從中挑選具有最小箇數的開區間使之仍能覆蓋閉區間[a,b]的算法.為瞭檢驗所給算法的正確性,進行瞭計算機模擬測試.
허다경제、관리、군사、계산궤화수학영역중적실제문제,가이추상성위폐구간(혹폐구역)적유한복개문제.위료획득저류문제재모충우화약속조건하적국부최우해,수요설계계산궤구해산법.기우탐심법원리,대m개폐구간,용n(m>n)조선단거복개,재복개선단총장최소적조건하,급출료여하선취복개선단적산법;급출료일개개구간집S시부복개폐구간[a,b]적판정,재가이복개적조건하,종중도선구유최소개수적개구간사지잉능복개폐구간[a,b]적산법.위료검험소급산법적정학성,진행료계산궤모의측시.