基于目标增量的无等待流水调度快速迭代贪婪算法_
基于目标增量的无等待流水调度快速迭代贪婪算法
朱夏, 李小平, 王茜
(东南大学计算机科学与工程学院, 南京210096)
(计算机网络和信息集成教育部重点实验室，南京210096)
摘要: 最小化总完工时间无等待流水调度是典型的NP-完全问题，广泛存在于实际生产系统。改变传统求解调度序列目标函数的模式，提出目标增量法，通过目标函数变化量判断新解的优劣，大大降低算法所需计算时间；通过证明启发式算法基本操作的目标增量性质，设计两种基本目标增量法以快速评估新产生解的质量。提出快速迭代贪婪算法FIG（Fast Iterative Greedy algorithm）求解该问题，构造初始解生成算法，提出分段式重构局部搜索方法和迭代改进全局搜索策略以进一步提高解的质量。基于110个经典Benchmark实例，将提出的FIG算法与目前求解该问题较好的启发式算法PH1p和元启发式算法SRTS、DPSOvnd进行比较，实验结果表明FIG在性能上优于SRTS和PH1p，略逊于DPSOvnd；在效率上优于SRTS 和DPSOvnd，略逊于PH1p。
关键字: 无等待流水调度，目标增量，启发式算法，总完工时间最小
Objective Increment based Iterative Greedy Heuristic for No-wait Flowshops with
Total Flowtime Minimization
Xia Zhu, Xiaoping Li, Qian Wang
(School of Computer Science and Engineering, Southeast University, Nanjing, 210096)
(Key Laboratory of Computer Network and Information Integration (Southeast University), Ministry of Education, Nanjing,210096)
Abstract: No-wait flowshops with total flowtime minimization are typical NP-Complete combinatorial optimization problems, widely existing in practical manufacturing systems. Different from traditional methods in which objectives are completely computed for a new generated schedule, objective increment methods are presented in this paper. Whether a new schedule is better or worse than the original one is judged just by the objective increment, which can reduce computational time considerably. Objective increment properties are analyzed for fundamental operations of heuristics. Based on the properties, two fundamental methods are introduced for fast evaluating schedules. FIG (Fast Iterative Greedy algorithm) is proposed for the considered problem, which includes initial solution generating and solution improvement phases. Besides an initial solution generating method being constructed, a segment based reconstructive heuristic and an iterative improvement procedure are developed for local and global search respectively to improve the current solution. FIG is compared with PH1p, SRTS and DPSOvnd algorithms on 110 traditional benchmark instances. Computational results show that FIG outperforms SRTS and PH1p but a little worse than DPSOvnd in effectiveness. In efficiency, FIG is better than SRTS and DPSOvnd but a little worse than PH1p.
Keywords: No-wait flowshops; Objective increment; Heuristic; Total flowtime minimization
本课题得到国家自然科学基金（No.60504029和No.60672092）和国家863项目（No. 2008AA04Z103）资助。朱夏，女，1982生，博士研究生，主要研究领域为调度优化、服务计算，email：zhuxia@https://www.wendangku.net/doc/4b2227266.html,；李小平，男，1970生，博士生导师，博士，副教授，主要研究领域为调度优化、服务计算、企业互操作，email：xpli@https://www.wendangku.net/doc/4b2227266.html,；王茜，女，1946生，博
研究背景
本文研究得到国家自然科学基金No. 60504029、No. 60672092和国家863项目No. 2008AA04Z103资助。
国家自然科学基金项目“基于目标增量的大规模无等待调度复合启发式算法”（No. 60504029）主要考虑无等待流水调度这类重要的约束流水调度问题，它要求任务的加工从开始到结束必须连续进行，不能出现等待，该问题广泛存在于冶金、塑料、化工和食品加工等面向流程的行业；此外，在高级制造环境，如JIT、FMS以及机器之间具有高度协作的加工环境，通常也被模型化为无等待调度。无等待调度的优化目标可以等价转化为相邻任务间“距离”的加权和，这些“距离”可事先确定且相互独立，因此目标函数的变化量只与调度序列变化点的“距离”有关，与调度中其它任务间的“距离”无关，即算法搜索过程中产生的调度是否更优可以通过计算所有变化点的目标增量和来评价，而不需要计算整个调度中所有任务的时间参数。例如对于最小化目标函数问题，如果增量和为正，则新调度更差；如果增量和为负，则新调度优于原调度。另外，由于搜索算法的元操作（产生新调度）仅仅作用于原调度中一点（如插入）或两点（如对换），所以新调度的变化点通常为有限的少数几个。这样新调度的评价就可以从计算n个任务时间参数减少为仅仅计算少数几个变化点的目标增量和，最大可将算法的时间复杂度降低1阶（n的常数倍）。本文基于目标增量法提出一种快速迭代贪婪算法FIG，构造出启发式算法ISG产生初始解，建立用于提高解质量的分段式重构策略和迭代全局搜索算法，采用类似于模拟退火（SA）机制的邻域接收准则以防止算法陷入局部最优。通过大量Benchmark实例将提出的FIG算法与当前比较好的启发式算法PH1p和元启发式算法SRTS、DPSOvnd进行比较，结果表明FIG在性能上优于SRTS和PH1p，略逊于DPSOvnd，在效率上优于SRTS和DPSOvnd，略逊于PH1p。因此，FIG算法适用于求解大规模NWFP问题。
国家自然科学基金项目“基于服务计算的一类不可分解调度问题自适应算法”（No. 60672092）考虑NP-难的总完工时间最小的流水作业排序问题（∑j C
|）。选取总完工时间最小为优化目标，是因为
Fm|
prmu
总完工时间是流水作业排序问题重要的性能指标，它可以促使资源稳定有效地利用、作业的快速周转和在制品库存最小。∑j C
|问题调度算法总体上由一些串行操作步组成，每个操作步由许多基本运算Fm|
prmu
步组成，算法的主要时间开销在于评价基本运算步产生的新调度，这些运算步在操作步中没有依赖关系，可并行化，如在插入（无论RZ插入还是NEH插入）过程中，被插入作业在插入所有可能位置时，这些插入操作不依赖于其他位置的操作，因此可以并行执行；类似的操作还有对换、杂交、变异等操作。另外，基于服务计算的体系架构和任务的自适应分配还可应用于基因预测与分析、机器调度、项目调度、工作流调度和元启发式算法求解其他复杂问题等多个领域，因为绝大多数算法都是迭代搜索，每一代的搜索范围是一个局部区域，而这个局部区域的搜索可并行化，与上述同顺序作业排序类似。该方法为广泛存在的批量生产企业的大量排序问题提供快速、高效的求解方法，其主要目的是缩短算法的计算时间，甚至降低算法的时间复杂度，特别是大规模问题；也可为其他类似问题提供新的解决方法和途径。
1. 引言
调度（排序）是制造和服务等行业中一类重要且普遍存在的问题。调度是为一系列任务在不同机器上安排一个合理的加工时间表，达到某个或某些性能最优，如最小化最大完工时间（makespan ）、总完工时间（total flowtime ）、延迟（tardiness ）等[1]。无等待流水调度问题是一类重要的约束流水调度问题，它广泛存在于流程式企业[2]，如化工制造、钢铁铸造、食品加工、塑料塑造等。此外，高级制造环境如Just-in-time 、柔性制造系统以及机器人之间具有高度协作的加工环境通常也被模型化为无等待调度。
所有任务的完工时间之和称为总完工时间（total flowtime ），它是调度的一个重要评价指标。总完工时间最小可促使资源稳定有效地利用、任务的快速周转和在制品库存最小[3]。最小化总完工时间的无等待流水调度可表示为∑
i
m C nwt F |
|[4]
。Hall and Sriskandarajah [2]和MacCarthy and Liu [5]对该问题的现状做了较
为详细的综述，并指出该问题即使在两台机器的情况也是NP-完全的。Van Deman and Baker [6]提出分枝定界法来寻求最优方案，并提出一系列过程来产生最优值的下界。Adiri and Pohoryles [7]证明2-机问题具有最优调度的一些性质，并给出一些定理作为多项式有界求解具有升序或降序占优机器序列的m -机问题的基础。Van der Veen and Van Dal [8]指出当目标函数限于半序的加工时间矩阵时该问题是可解的。Rajendran and Chaudhuri [9]提出构造启发式算法RC1和RC2，实验结果表明对于任务数在区间[12,20]的小规模问题，RC1优于RC2，且二者性能明显优于Bonney and Gundry [10]和King and Spachis [11]的算法。Bertolissi [12]提出基于成对比较和任务插入的构造启发式算法BE ，实验结果表明BE 优于RC1、RC2[9]和Bonney and Gundry [10]的算法。Chen 等[13]提出采用启发式算法与随机生成方式相结合产生初始种群的遗传算法（简称TGA ），实
验结果表明TGA 在200个实例中有168个结果比RC1好，但在问题规模较大时并不稳定。Fink and Vo?
[14]以Taillard [15]的110个经典Benchmark 实例为基础，分析比较多种元启发式算法，表明以Chins 或Pilot-10产生初始解、移位与自适应禁忌搜索相结合的方法（简称SRTS ）是很有效的算法。Aldowaisan and Allahverdi [16]构造六个复合启发式算法PH1(p) ~PH4(p)，并将其与RC1, RC2[9], BE [12]and TGA [13]进行比较，结果表明PH1p 的性能明显优于其它算法。Akhilesh Kumar 等[17]提出比PH1p 性能更优的心理学克隆选择算法，但该算法难于实现。Quan-Ke Pan [18]提出基于VND 局部搜索和离散微粒群的算法DPSOvnd ，将速度与位置更新策略投影为离散空间的进化算子，并采用任务交换和插入操作加速计算方法，该算法是目前性能最好的算法。
本文基于文献[19]求解∑i m C F ||问题的迭代贪婪算法IG ，构建一个求解∑i
m C nwt F |
|问题的目标增
量的快速迭代贪婪算法FIG 。根据问题的特点构造初始解；通过将序列随机划分为若干子序列并分别采用分解与重构操作产生邻域，扩大局部搜索范围；全局搜索阶段采用first-improvement 准则。更重要的是，本文分析并推导出启发式算法基本操作的目标增量性质，提出目标增量法仅仅计算新解的目标函数增量而不是计算该解的整个目标函数值来降低算法的时间复杂度，大大节省FIG 的计算时间。
2. 问题描述
无等待流水调度问题（简称NWFP ）可以描述为n 个任务{}n J J J ,,,21 连续在m 台机器
},,,{21m M M M 上以相同的顺序加工，所有任务的工艺路线相同，每台机器上任务加工的顺序也完全相同，
任务一旦开始加工不允许等待，即等待只可能发生在第一台机器上。具体约束可描述为：（1）任务在机器上的加工顺序相同且确定；（2）每道工序的加工时间预先给定；（3）每台机器同时只能加工一个任务，一个任务一次只能在一台机器上加工；（4）任务不允许等待，即要求任务一旦开始加工就必须连续进行直到加工完成。
该问题的任何调度都是任务集合{}n J J J ,,,21 元素的一个全排列。为便于描述，引入虚任务]0[π作为
一个调度的初始任务，它在各台机器上加工时间均为0。因此，一个调度π可表示为),,,(][]1[]0[n πππ ，其中∈][i π
{}n J J J ,,,21 （n i ≤≤1）表示π中第i 个位置上的任务。设i k t ,为任务i J （n i ,,1,0 =）在机器k
M （m k ,,2,1 =）上的加工时间，j i D ,为任务i J 与j J 相邻时二者在最后一台机器上的完工时间距离，根据文献[4]有
})({
m ax ,,,,,1,∑==+-=m
k
h i k i h j
h m
k j i t t t
D (1)
显然∑===
m
h j
h j n j t
D 1
,,0),,1( ，容易证明0,>j i D 。记任务对()
][][,j i ππ（n j i ≤≤,0且j i ≠）的完工时间距离
为π]],[[j i D ，调度π中][i π（n i <≤0）及其直接后继]1[+i π间的完工时间距离记为π][i d ，则调度π的total flowtime 可表示为：
∑∑-=-=+-=
-=
10
]
[10
]
1],[[)()()(n i i n i i i d i n D
i n F π
π
π (2)
由此可见，解决∑i
m C nwt F ||问题就是要在所有可能的任务序列集合∏中找到这样一个任务序列*
π
，
使得
∏∈?≤πππ)
()(*F F
从式（1）可看出，j i D ,仅仅取决于i k t ,，而i k t ,是预先给定和确定的，任何两个任务之间的距离j i D ,不会随调度的变化而变化。因此，任务集合{}n J J J ,,,21 中任何两个任务（包括虚任务）之间的距离可以预先求出并存储在矩阵DM 中。由于]0[π不可能出现于任何一个任务之后，故令∞=0,i D ，并规定同一任务间的距离也为∞，即∞=i i D ,。因此，矩阵DM 可表达为
DM )
1()1(2,1
,,21,2,12,1,02,01,0+?+???
?
???
????????
?∞∞∞∞
∞∞∞
=n n n n n n n D D D D D D D D D
由于式（1）中计算j i D ,的时间复杂度为)(m O ，所以计算矩阵DM 的时间复杂度为)(2mn O ；直接从DM 中获取π][i d ，式（2）计算)(πF 的时间复杂度可减少为)(n O 。
3. 目标增量法
启发式算法通常开始于一个活动解，通过一些基本操作产生邻域，在邻域中搜索更接近最优解的新解替换该活动解，迭代该过程直到满足一定的停止条件。对于∑i
m C nwt F ||问题而言，邻域的产生方法基本
上可归纳为任务插入、删除、移位和对换等四个基本操作。
由式（1）、（2）可知，一个调度序列的目标函数值（total flowtime ）等于相邻任务间距离AD （Adjacent Distance ）的加权和，AD 的值仅仅与这两个任务工序的加工时间有关。因此，对调度序列的任何一个基本操作（插入、删除、移位或对换）只会引起目标函数值在操作位置上的增加或减少，序列中其它位置上任务的AD 保持不变，我们称相应的目标函数值变化量为目标增量。由此可见，基本操作是导致调度序列目标函数值发生变化的根本原因。新序列的目标函数值就等于活动解的目标函数值与目标增量的和，如果仅仅计算新序列的目标增量和而不是按传统方法通过式（2）计算目标函数值，可大大节省计算时间，称这
种方法为目标增量法。对于一个6=n ，3=m 的NWFP 例子，图1和图2分别给出将任务2J 移动到任务6J 之后，以及任务2J 和任务4J 对换位置的过程。
1,3
4,5
1,2
0,1
4,5
1,2
0,1
4,5
0,1
图1 将任务2J 移动到任务6J 之后 图2 任务2J 与任务4J 对换位置
图1表明π中任务2J 的移位实际上是先将其从所在位置上删除，再插入到任务6J 之后的位置，将减少2,1D 和3,2D 、增加3,1D 和2,6D ，而1,0D 、4,3D 、5,4D 和6,5D 保持不变。同样，在图2任务2J 和任务4J 的位置互换过程中，将减少2,1D 、3,2D 、4,3D 和5,4D ，增加4,1D 、3,4D 、2,3D 和5,2D ，而1,0D 和6,5D 保持不变。
设'π是某个操作作用于π后产生的一个邻居解，则目标函数值)()()('πππ?+=F F （如果'π比π好，则增量为负值）。不同基本操作具有不同的目标增量性质，为了简化描述，设
??
???--==otherwise d D i n n i o x i j i j i ))(()(][][],[,πππ，?????--==+otherwise d D j n n j o y j j i j i ))(()(][]1[,,πππ，?????≥<=∑
=00)(0
][k d k o
k s k i i π 定理1 若将任务q J 插入到一个∑i
m C nwt F |
|序列),,,(][]1[]0[n πππ
π =中任务][k π（n k ≤≤0）之后，
则total flowtime 将增加)()1()1(),(,],[ππk q q k y D k n k s k n ++-+-=?。
证明：（1）当0=k （即任务q J 插入到π中虚任务]0[π之后成为第一个实任务）时，形成的新序列为
),,,,(][]1[]0['
n q J ππππ =，由公式（2）可知其total flowtime 为∑-=-+++=11
][]1[,],0['
)()1()(n i i q q d i n nD D n F ππ
ππ
)
()1()1()()()1()()1()(0,,00,,0]0[]1[,,0πππππππq q q q q q y D n s F y D n F nd nD D n F +++-+=+++=-+++=)0,()(n F ?+=π
（2）当11-≤≤n k 时，形成的新序列为),,,,,,(][]1[][]0['n k q k J πππππ +=，由公式（2）可知其total flowtime 为 ++-++
=-+
-++-+-+=
∑∑∑-=-+=+-=π
ππ
π
ππ
ππq
k k i i n k i i k q q k k i i D k n d F d
i n D k n D k n d
i n F ],[10
]
[1
1
]
[]1,[],[10
]
['
)1()()()()1()1()(
),()()()1()1()()()(,],[][]1[,k n F y D k n k s F d k n D k n k q q k k k q ?+=++-+-+=---+ππππ
ππ
（3）当n k =（即任务q J 插入到序列π的末端）时，形成的新序列为),,,(][]0['q n J πππ =，由)(,πj i y 知0)(,=πn q y ，所以根据公式（2）可知其total flowtime 为
),()()()()1()(,],[1
][],[1
]
['
n n F y D d F D d
i n F n q q
n n i i q n n i i ?+=+++
=+-+=
∑∑-=-=πππππ
ππ
π
□
以下定理和推论的证明类似于定理1。
定理2 若删除∑i m C nwt F |
|序列),,,(][]1[]0[n πππ
π =中任务][k π（n k ≤≤1），则total flowtime 将减少
)()()1(),(,]1[]1[πππk k k y d k n k s k n ---+-=?-。
推论1 若将∑i
m C nwt F |
|序列)
,,,(][]1[]0[n πππ
π =中位置1k 上的任务][1k π移位到位置2k （,11k ≤≤2k
n ）上，则total flowtime 将增加),()1,1(12k n k n ?---?。
推论2 若将∑i
m C nwt F |
|序列),,,(][]1[]0[n πππ
π =中的任务][i π与][j π位置对换（n j i ≤<≤1），则
total flowtime 将增加????
?++++=--++=---otherwise
y x y x i j d D i n y x j i j i j i j
i i i j j j i i j i )()()()(1
))(()()(),(,,1,,1][][],[,,1][][]
[ππππππωπππ
ππ。
由于启发式算法在搜索解的过程中，需要不断通过上述基本操作产生新解并评价这些新解（计算目标函数值），而算法的主要时间开销在于评价这些新解上。从定理1和定理2可以看出：对于NWFP 问题，插入和删除操作仅仅作用于很少的变化点，引起的目标增量只需要计算少数几个AD 值的和，时间复杂度为)1(O ，而计算整个目标函数值的时间开销为)(n O ，所以在启发式算法中采用目标增量法可以将其时间复杂度降低1阶。同理，由推论1和推论2可知，仅计算移位和对换引起的目标增量也可将算法时间复杂度降低1阶。
根据上述基本操作的目标增量性质，可构造任务最佳点插入（BIP ）和任务对最佳对换（BSP ）这两个基本目标增量方法。BIP 是寻找任务][i π从位置i 移除后插入到另一个位置j （即任务]1[-j π之后）使得目标增量最小，具体描述如下：
1. 根据定理2计算)()()1(),(,]1[]1[πππi i i y d i n i s i n ---+-←?-;
2. 将任务][i π从π中删除形成任务序列τ;
3. For 0=k to 2-n
根据定理1计算τππττ][,,)()()(),1(][][][k k d y D k n k s k n i i k -+-+←-?; 4. ][]1[,)2()1,1(i n D n s n n πτ-+-←--?; 5. {}),(),1(m in
)(1
,,1,0i n k n p n k ?--?←
-= μ;
6. 如果0)(
算法第3步的时间复杂度为)(n O ，第4步为)1(O ，故BIP 的时间复杂度为)(n O 。BSP 依据推论2计算序列),,,(][]1[]0[n πππ 中不同位置上两个任务对换引起的目标增量，在所有2/)1(-n n 个任务对换增量中，如果最小增量小于0，则表明相应的位置为当前最佳对换位置，对换相应任务对。该过程类似于pair-wise exchange [20]，二者的区别在于前者只计算目标增量而后者是计算整个目标函数值，前者的时间复杂度为)(2n O ，后者为)(3n O 。
4. 快速迭代贪婪算法
快速迭代贪婪算法FIG 的基本思想如下：根据问题的特点构造初始解，并置为当前解；对当前解依次采用分段式重构策略和迭代全局搜索进行局部寻优和全局寻优，从产生的邻域中选择较好的新解取代当前解；采用类模拟退火的接收准则判断新解是否取代当前解；迭代上述过程直至满足停止条件；最后将得到的优良解采用任务对最佳对换作进一步改进。
4.1 初始解生成算法
由式（2）知，)(πF 是由序列),,,(][]1[]0[n πππ 中任务][i π与任务]1[+i π之间距离π][i d （10-≤≤n i ）的加权和决定的，其中的权值i n -是i 的反函数。由于越靠近调度序列前面其权越大，为保证total flowtime 越小，应选择越小的π][i d ，其实质是确定一条从虚任务]0[π出发的最短Hamilton 路。为保证距离矩阵DM 不被破坏，预先将DM 保存在DM ’中，即DM ’←DM 。初始解产生法ISG 通过对矩阵DM ’操作产生一条最短Hamilton 路，其基本思想为：设Φ←1μ，{}jobs all ←2μ，1←i ；为防止产生环路，令∞←-π]1,[i j D （n j ≤≤0），在矩阵DM ’中第]1[-i π行寻找}{min ],1[,,1πj i n
j D -= 对应的任务作为][i π，}{][11i πμμ+←，
}{][22i πμμ-←，1+←i i ，重复上述过程直至Φ=2μ为止。确定一条路径),,,(][]1[]0[n πππ 即为初始解0π，
恢复DM 的值即DM ←DM ’。ISG 算法具体描述如下：
算法ISG 1 DM ’←DM;
2 Φ←1μ,}{2jobs
all ←μ,1←i ; 3 While (Φ≠2μ) 3.1 For 0=j to n
∞←-π]1,[i j D ；
3.2 }{min ],1[,,1]],[1[π
πj i n
j i i D D -=-← ,}{][11i πμμ+←,}{][22i πμμ-←,1+←i i ；
4 DM ←DM ’, ),,,(][]1[]0[0n ππππ ←,∑-=-←1
]
[0)()(n i i d i n F ππ；
5 返回0π，算法结束。
算法第1步的时间复杂度为)(2mn O ，第3步为)(2n O ，故上述初始解产生算法的时间复杂度为)(2mn O 。 4.2 分段式重构策略
分段式重构策略SRS （Segment based Reconstruction Strategy ）是一个局部迭代搜索的过程，通过随机分划子序列和逐段邻域搜索，扩大寻优范围，从而提高求解质量。其步骤如下：首先将调度序列π用bN 个断点随机分成1+bN 段（bN 为预先设置的常数，通常很小），第i （bN i ,,1,0 =）个序列段的首尾分别用首指针i start 和尾指针i end 来指示。对每个序列段进行h 次（h 等于该段段长或与之成比例）如下分解与重构操作：从该段中随机抽取d 个任务（d 是段长的d P 倍），将这d 个任务按照其原来在π中位置的倒置形成序列d π，该段中剩下的任务按照原来的顺序形成待重构的部分序列i r π；从d π中逐一取出任务对序列i r π进行BIP 操作，重构出使该段更优的子序列。SRS 算法具体描述如下：
算法)(πSRS
1 将序列π随机分成1+bN 段, 第i 段记作],[i i end start , bN i ,,1,0 =;
2 For 0=i to bN
2.1 ],[i i end start h ←中任务个数，d P h d ?←; 2.2 For 1=j to h
2.2.1 ππ←', Φ←d π; 2.2.2 For 0=k to 1-d
从'π的段],[i i end start 中随机取出一个任务插入d π;
2.2.3 将d π中的任务按其在'π中位置的降序排序，],[i i end start 剩余任务构成待重构序列i
r π;
2.2.4 For 0=k to 1-d
←'π将任务]
[k d
π对i
r π进行BIP 插入操作；
2.2.5 如果)()('ππF F <, 则'ππ←;
3 返回π，算法结束。
由上可知，SRS 算法的时间复杂度集中在第2步，其中第2.2步的时间复杂度为)(3n O ，而bN 为较小常数，故SRS 的时间复杂度为)(3n O 。
对于4,10==m n 调度问题，图3示例了调度实例),,,,,,,,,(10987465312J J J J J J J J J J =π的单次分解与重构过程。
-分解阶段
-
038494562
r
图3 单次分解与重构过程
为便于描述，令数组(2,1,3,5,6,4,7,8,9,10)代表序列π。初始时π的目标函数值为4642；两个断点（短竖线）将π分割成长度分别为3，4，3的三段，分别为(2,1,3) ，(5,6,4,7)和(8,9,10)；取7.0=d P ，中段(5,6,4,7)的分解重构过程如下：从该段中随机抽取??27.04=?个任务6J 和7J ，按照其原来在π中的倒置顺序形成序
列)6,7(=d π，该段中剩下的任务则构成待重构的部分序列)4,5(1=r π；从d π中依次取出任务对1
r π进行BIP
插入直至d π为空，重构后的新子序列依次为(5,7,4)（目标函数值为3849）和(5,6,7,4)（目标函数值为4562），而π经过该段重构后得到的新序列为(2,1,3,5,6,7,4,8,9,10)，对应目标函数值4562。
表1给出了SRS 算法的完整分段重构过程：初始序列(1,2,3,4,5,6,7,8,9,10)的目标函数值为5172，被分割成长度分别为3，4，4三段；对第0段进行迭代分解与重构后的最优解为(2,1,3,4,5,6,7,8,9,10)，对应目标函数值4733；对第1段进行迭代分解与重构后的最优解为(2,1,3,5,6,7,4,8,9,10)，对应目标函数值4562；对第2段进行迭代分解与重构后的最优解为(2,1,3,5,6,7,4,10,9,8)，对应目标函数值4551，即为最终结果。
表1 SRS 算法的实例执行过程
第i 段 迭代 当前序列
d π
i r π
待插任务
子序列
目标函数值
初始序列
)10,9,8|7,6,5,4|3,2,1(
5172
0=i 1 )10,9,8|7,6,5,4|3,2,1(
)2,3( )1( 3J )10,9,8|7,6,5,4|1,3( 4199
)1( 2J )10,9,8|7,6,5,4|2,1,3( 4776 2 )10,9,8|7,6,5,4|2,1,3(
)1,2( )3( 2J )10,9,8|7,6,5,4|,3,2( 3903
)3( 1J )10,9,8|7,6,5,4|3,1,2( 4733 3 )10,9,8|7,6,5,4|3,1,2(
)2,1( )3( 1J )10,9,8|7,6,5,4|1,3( 4199
)3( 2J )10,9,8|7,6,5,4|2,1,3( 4776 1=i 1 )10,9,8|7,6,5,4|3,1,2(
)6,7( )5,4( 7J )10,9,8|7,5,4|3,1,2( 3984
)5,4( 6J )10,9,8|7,5,4,6|3,1,2( 4688 2 )10,9,8|7,5,4,6|3,1,2(
)6,5( )7,4( 5J )10,9,8|7,4,5|3,1,2( 3929
)7,4( 6J )10,9,8|7,4,6,5|3,1,2( 4642 3 )10,9,8|7,4,6,5|3,1,2(
)6,7( )4,5( 7J )10,9,8|4,7,5|3,1,2( 3849
)4,5( 6J )10,9,8|4,7,6,5|3,1,2( 4562 4 )10,9,8|4,7,6,5|3,1,2(
)7,4( )6,5( 4J )10,9,8|4,6,5|3,1,2( 3849
)6,5( 7J )10,9,8|4,7,6,5|3,1,2( 4562 2=i 1 )10,9,8|4,7,6,5|3,1,2(
)9,10( )8( 10J )8,10|4,7,6,5|3,1,2( 3859
)8( 9J )8,9,10|4,7,6,5|3,1,2( 4551 2 )8,9,10|4,7,6,5|3,1,2(
)9,8( )10( 8J )8,10|4,7,6,5|3,1,2( 3859
)10( 9J )8,9,10|4,7,6,5|3,1,2( 4551 3 )8,9,10|4,7,6,5|3,1,2(
)9,8( )10( 8J )8,10|4,7,6,5|3,1,2( 3859
)10(
9J
)8,9,10|4,7,6,5|3,1,2(
4551
4.3 迭代全局搜索
迭代全局搜索法IGS （Iterated Global Search ）采用循环删除-插入操作，对分段式重构后产生的解作进一步改进。IGS 算法的迭代过程如下：随机不重复地从当前序列),,,(][]1[]0[n ππππ =中抽取出一个实任务][k π（n k ≤≤1），依次计算][k π插入π中剩余序列可能位置的目标增量（不可插入虚任务]0[π之前），选择
第一个移位目标增量小于0的插入点，将][k π插入该点得到的新解作为当前解。将π中所有实任务都做上述操作，若当前解在这n 次循环中有至少被改进1次，则继续下一次迭代；否则停止，算法结束。IGS 的单次搜索过程类似BIP ，不同之处在于：前者中邻居解的接收采用first-improvement 准则，即接收邻域中搜索到的第一个有改进的解；而后者采用best-improvement 准则，即接收邻域中搜索到的最优改进解。IGS 算法具体描述如下：
算法)(πIGS 1
true flag ←;
2 While (true flag =) 2.1 false flag ←; 2.2 For 1=i to n
2.2.1 从π中随机且不重复的取出一个实任务][k π; 2.2.2 For 1=j to n
2.2.2.1 根据推论1, 计算插入点j 对应的移位目标增量),()1,1(k n j n ?---?;
2.2.2.2 如果0),()1,1(
*ππ←,true flag ←;
3 返回π，算法停止。
算法IGS 的时间复杂度集中在第2步，第2.2步的时间复杂度为)(2n O ；由于flag 指示的停止条件不定，所以IGS 的时间复杂度需根据外循环次数来确定。 4.4 FIG 算法描述
快速迭代贪婪算法FIG 由初始解产生、分段式重构和迭代全局搜索三个阶段组成：调用ISG 算法构造初始解并赋值给当前解；将当前解随机分成若干段，采用分段式重构策略SRS 进行局部优化和搜索；对改进后的解采用迭代全局搜索IGS 和任务对最佳对换法BSP ，进一步提高解的质量。其中邻域搜索过程均基于基本目标增量法BIP 和BSP ，大大减少了时间开销。
分段式重构和迭代全局搜索后得到的解序列可能比已经得到的最好解差，是否进一步迭代搜索需要根据一定的准则来判断。由于模拟退火算法（SA ）可在保证收敛的情况下以一定概率跳出局部最优，故本文采用一种类模拟退火的接收准则，将π改进后的解'π以概率}/))()((exp{'T F F n n ππ--接收并替换当前活动解，式中T 为控制参数，随着算法的运行逐渐减小。T 的值根据具体实例确定并初始化为()m n t
t T n
i m
k i
k ???
=∑∑==1011
,0，退火过程中的冷却机制采用文献[21]中的)10(1<<=+λλs
s T T 以维持计算速率
与达到低能态二者之间的平衡。FIG 算法具体描述如下：
算法FIG
1 关键参数设置: bN , d P , t , λ;
2 调用ISG 算法产生初始解0π;
3 0ππ←, ππ←b ;
4 While (不满足终止条件) 4.1 )(ππSRS ←； 4.2 )(*ππIGS ←;
4.3 如果)()(*ππF F <, 则*ππ←;
4.3.1 如果)()(b F F ππ<, 则ππ←b ; 否则
4.3.2 如果}/))()((exp{*T F F random ππ--≤, 则*ππ←, T T ?←λ;
5 )(b b BSP ππ←；
6 返回b π, 算法结束。
FIG 算法的时间复杂度集中在第2、4、5步，其中第2步为)(2mn O ；第5步在不采用目标增量法时为)(3n O ，采用时为)(2n O ；尽管第4步的时间复杂度需根据While 循环次数确定，但对于主要步骤4.1和4.2，
在不采用目标增量法时均为)(4n O ，采用时为)(3n O ；由此可见，采用目标增量法的FIG 的时间复杂度比不采用目标增量法可降低1阶。
5. 模拟实验结果及性能分析
为分析本文所提出迭代贪婪算法的性能，将FIG 算法与目前较有效的复合启发式算法PH1p [16]、元启发式算法SRTS [14]和DPSOvnd [18]进行比较。SRTS 和DPSOvnd 将Taillard [15]的110个Benchmark 实例分成
4组进行比较，为给出更详尽的比较结果，本文按照相同的分组方式将110个实例共分成11组，分别记为T1～T11，即每10个实例1组，如T1表示ta001～ta010。FIG 算法主要参数设置如下：当n 为20、50、100和200时，bN 分别取4、5、5、10，7.0=d P , 37.0=t , 99.0=λ, 停止条件为最大迭代次数250次。所有算法均用Visual C++实现，并在Pentium 2.93GHZ 、512M RAM PC 机上执行。
分别从ARPD [4]（单位：％）和所需CPU 计算时间（单位：秒）两方面对以上算法的性能和效率进行比较。每组实例的ARPD （其中10=N ，i B 为四个算法求解实例i 的最小total flowtime ）结果如表2所示。
表2 算法的性能和效率比较
Group n m ARPD CPU ARPD CPU ARPD CPU ARPD CPU T1 20 5 0.151 1.553 1.709 0.091 0.000 0.863 0.000 0.420 T2 20 10 0.000 1.506 2.229 0.151 0.000 0.837 0.000 0.420 T3 20 20 0.000 1.512 1.755 0.392 0.000 0.840 0.000 0.420 T4 50 5 0.323 13.854 4.074 0.746 0.203 7.696 0.000 4.615 T5 50 10 0.482 14.303 3.834 2.441 0.176 7.946 0.000 4.699 T6 50 20 0.567 14.061 3.035 6.768 0.199 7.812 0.008 4.657 T7 100 5 0.970 103.161 4.469 6.137 0.072 57.312 0.268 47.957 T8 100 10 0.510 108.856 4.770 19.971 0.102 60.476 0.183 46.866 T9 100 20 0.404 107.050 4.266 50.493 0.122 59.472 0.041 46.908 T10 200 10 1.812 996.445 4.673 194.685 0.009 553.580 0.445 302.509 T11
200 20
1.042 1003.422 4.503 504.495 0.078 557.457 0.612 303.642 Avg
0.569 3.574 0.087 0.142
从表2可以看出：在性能方面，PH1p 算法随着问题规模的扩大呈上升趋势且波动较大，对所有问题其ARPD 都比其它三个算法大得多，最大值在问题T8达到4.77％，最小值也超过1％，11组实例的平均ARPD 为3.574％。SRTS 算法的平均ARPD 为0.569％，仅优于PH1p ，在问题T2和T3时为最低值0，在问题T10和T11时则分别达到峰值1.812％和1.042％，其变化趋势类似于PH1p 。FIG 的平均ARPD 为0.142％，很接近于DPSO vnd 的平均ARPD （0.087％），二者差值约为0.05％；当问题规模较小时（T1~T5），FIG 的ARPD 始终为0，且等于或小于DPSOvnd 的ARPD ，二者差值在0.2％左右；随着问题规模的扩大，除特殊点T9之外，FIG 的ARPD 相对DPSOvnd 的ARPD 较大，且二者差值呈增长趋势。
在效率方面，PH1p 的效率最高，FIG 其次，SRTS 的效率最差。例如，就规模为10200?的问题T10而言，PH1p 需要的时间为195s ，FIG 需要303s 的时间，DPSOvnd 需要554s 的时间，而SRTS 需要996s 的时间。对于所有问题而言，FIG 的CPU 时间约为DPSOvnd 所需时间的1/2，为SRTS 所需时间的1/3；FIG 的CPU 时间在问题规模较小时接近于PH1p 所需时间，并随着问题规模的扩大而增加，但FIG 的性能远远好于PH1p 。
综上所述，对于所有的任务机器的组合进行的测试，FIG 算法在性能方面优于PH1p 算法和SRTS 算法，略逊于DPSOvnd 算法，在效率方面优于SRTS 算法和DPSOvnd 算法，比PH1p 算法略差。
6. 结论
本文考虑最小化总完工时间的无等待流水调度问题，根据问题的特点分析出调度序列中任务间的时间参数具有相对独立性，并证明出算法基本运算的目标增量性质；根据这些性质提出一种快速迭代贪婪算法FIG ，构造出启发式算法ISG 产生初始解，建立了用于进一步提高解质量的分段式重构策略和迭代全局搜索算法，采用类似于模拟退火机制的邻域接收准则以防止算法陷入局部最优。整个解的搜索过程基于两种目标增量方法BIP 和BSP ，快速评估由插入、删除、移位或对换操作对一个解产生的邻域。通过110个
Benchmark实例将提出FIG算法与当前较好的启发式算法PH1p和元启发式算法SRTS、DPSOvnd进行比较，实验结果表明FIG在性能上优于SRTS和PH1p，略逊于DPSOvnd，在效率上优于SRTS和DPSOvnd，略逊于PH1p。因此，FIG算法适用于求解大规模无等待流水调度问题。
参考文献
[1]Pinedo M. Scheduling: theory, algorithm, and systems. Englewood Chills, NJ: Prentice-Hall, 1995.
[2]Hall NG, Sriskandarajah C. A survey of machine scheduling problems with blocking and no-wait in process. Operations
research, 1996, 44(3): 510-525.
[3]Rajendran C. A no-wait flowshop scheduling heuristic to minimize makespan. Journal of the Operational Research Society,
1994, 45(4): 472-478.
[4]Li Xiaoping. Heuristics for large sacle flowshop problems [Postdoctoral Research Report]. Beijing: Tsinghua University, 2004
(in Chinese).
(李小平. 启发式求解几个大规模流水调度问题[博士后研究报告]. 北京: 清华大学, 2004.)
[5]MacCarthy BL, Liu J. Addressing the gap in scheduling research: a review of optimization and heuristic methods in production
scheduling. International Journal of Production Research, 1993, 31(1): 59-79.
[6]Van Deman JM, Baker KR. Minimizing mean flow time in the flowshop with no intermediate queues. AIIE Transactions, 1974,
6(1): 28-34.
[7]Adiri I, Pohoryles D. Flowshop/no-idle or no-wait scheduling to minimize the sum of completion times. Navel Research
Logistics Quarterly, 1982, 29(3): 495-504.
[8]Van der Veen JAA, Van Dal R. Solvable cases of the no-wait flowshop scheduling problem. Journal of the Operational
Research Society, 1991, 42(11): 971-980.
[9]Rajendran C, Chaudhuri D. Heuristic algorithms for continuous flow-shop problem. Naval Research Logistics, 1990, 37(5):
695-705.
[10]Bonney MC, Gundry SW. Solutions to the constrained flow-shop sequencing problem. Operational Research Quart, 1976, 27(4):
869-883.
[11]King JR, Spachis AS. Heuristics for flow-shop scheduling. International Journal of Production Research, 1980, 18(3): 343-357.
[12]Bertolissi E. Heuristic algorithm for scheduling in the no-wait flow-shop. Journal of Materials Processing Technology, 2000,
107(1-3):459-465.
[13]Chen CL, Neppalli RV, Aljaber N. Generic algorithms applied to the continuous flow shop problem. Computers and Industrial
Engineering, 1996, 30(4): 919-929.
[14]Fink A, Vo?S. Solving the continuous flow-shop scheduling heuristic to minimize makespan. Journal of the Operational
Research, 2003, 151(3): 400-414.
[15]Taillard E. Benchmarks for basic scheduling problems. European Journal of Operational Research, 1993, 64(2): 278-285.
[16]Aldowaisan T, Allahverdi A. New heuristics for m-machine no-wait flowshop to minimize total completion time. OMEGA,
2004, 32(5): 345-352.
[17]Kumar A, Prakash A, Shankar R, Tiwari MK. Psycho-clonal algorithm based approach to solve continuous flowshop scheduling
problem. Expert Systems with Applications, 2006, 31(3): 504-514.
[18]Pan QK, Tasgetirenc MF, Liang YC. A discrete particle swarm optimization algorithm for the no-wait flowshop scheduling
problem. Computers and Operations Research, 2008, 35(9): 2807-2839.
[19]Ruiz R, Stützle T. A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem. European
Journal of Operational Research, 2007, 177(3): 2033-2049.
[20]Wang L, Zheng DZ. An effective hybrid optimization strategy for job-shop scheduling problem. Computers and Operations
Research, 2001, 28(6): 585-596.
[21]Osman IH, Potts CN. Simulated annealing for permutation flow-shop scheduling. Omega, 1989, 17(6): 551-557..
ZHU Xia, born in 1982, Ph.D. Candidate. Her main research interests include scheduling optimization, service oriented computing.
LI Xiaoping, born in 1970, Ph.D., associate professor, Ph.D. supervisor. His main research interests include scheduling optimization, service oriented computing, manufacturing interoperability.
WANG Qian, born in 1946, professor, Ph.D. supervisor. Her main research interests include information integration, database technology, CSCWD.
Background:
The aim of this work is to propose an effective and efficient heuristic algorithm for total flowtime minimization in no-wait flowshop problems. This work is supported mainly by the National Natural Science Foundation of China under grant No.60504029 called “objective increment based composite heuristic s for large scale no-wait flowshops”. It focuses on no-wait flowshop probems (NWFPs for short) which are important kind of constrained flowshop problems. In NWFPs, the operations of each job have to be continuously processed. No interruption is permitted either on or between machines. NWFPs widely exist in metallurgy, plastic molding, chemical processing and food processing industries. Modern manufacturing systems such as JIT systems, flexible manufacturing environments and robotic cells can also be modeled as NWFPs. The optimization objective in NWFPs can be modeled as the weighted sum of “distance” of adjacent jobs in a sequence. The “distance” is related only to the processing times of the related adjacent jobs but independent on other jobs in the sequence. Hence, it can be predetermined. Whether a new generated schedule is better or not than the original one can be judged just by calculating the sum of all the objective increments by the change of job positions, instead of calculating all time parameters of jobs in the whole schedule. Therefore, the time complexity of algorithms can be reduced. Objective increment properties are analyzed for fundamental operations of heuristics. Based on the properties, two fundamental methods are introduced for evaluating schedules fast. A fast iterated greedy algorithm FIG is proposed. In FIG, an initial solution generating method is constructed, and then a segment based reconstruction strategy and an iterative improvement procedure are developed for local and global search respectively to improve the current solution. In addition, an SA-like acceptance criterion is adopted to escape from local optimal. Experimental results show that, FIG outperforms PH1p and SRTS algorithms but it is little worse than DPSOvnd algorithm on effectiveness. On efficiency, FIG is better than SRTS and DPSOvnd but a little worse than PH1p. Therefore, FIG may be suitable for large scale NWFPs. This work is also supported by the National Natural Science Foundation of China under grant No. 60672092 and the National High Technology Research and Development Program of China (863 Program) under grant No. 2008AA04Z103.
贪心算法经典例题
贪心算法经典例题 发布日期：2009-1-8 浏览次数：1180 本资料需要注册并登录后才能下载！ ·用户名密码验证码找回密码·您还未注册？请注册 您的账户余额为元，余额已不足，请充值。 您的账户余额为元。此购买将从您的账户中扣除费用0.0元。 内容介绍>> 贪心算法经典例题 在求最优解问题的过程中，依据某种贪心标准，从问题的初始状态出发，直接去求每一步的最优解，通过若干次的贪心选择，最终得出整个问题的最优解，这种求解方法就是贪心算法。 从贪心算法的定义可以看出，贪心法并不是从整体上考虑问题，它所做出的选择只是在某种意义上的局部最优解，而由问题自身的特性决定了该题运用贪心算法可以得到最优解。 我们看看下面的例子 例1 均分纸牌（NOIP2002tg） [问题描述] 有 N 堆纸牌，编号分别为 1，2，…, N。每堆上有若干张，但纸牌总数必为 N 的倍数。可以在任一堆上取若干张纸牌，然后移动。移牌规则为：在编号为 1 堆上取的纸牌，只能移到编号为 2 的堆上；在编号为 N 的堆上取的纸牌，只能移到编号为 N-1 的堆上；其他堆上取的纸牌，可以移到相邻左边或右边的堆上。现在要求找出一种移动方法，用最少的移动次数使每堆上纸牌数都一样多。例如 N=4，4 堆纸牌数分别为： ①9 ②8 ③17 ④ 6 移动3次可达到目的： 从③取 4 张牌放到④（9 8 13 10） -> 从③取 3 张牌放到②（9 11 10 10）-> 从②取 1 张牌放到①（10 10 10 10）。 [输入]：键盘输入文件名。 文件格式：N（N 堆纸牌，1 <= N <= 100） A1 A2 … An （N 堆纸牌，每堆纸牌初始数，l<= Ai <=10000） [输出]：输出至屏幕。格式为：所有堆均达到相等时的最少移动次数。 [输入输出样例] a.in： 4 9 8 17 6 屏慕显示：3 算法分析：设a[i]为第i堆纸牌的张数（0<=i<=n），v为均分后每堆纸牌的张数，s为最小移到次数。 我们用贪心法，按照从左到右的顺序移动纸牌。如第i堆(0 算法导论——贪心算法 求解最优化问题的算法通常需要经过一系列的步骤，在每个步骤都面临多种选择。对于许多最优化问题，使用动态规划算法来求最优解有些杀鸡用牛刀了，可以使用更简单、更高效的算法。贪心算法(greedy algorithm)就是这样的算法，它在每一步都做出当时看起来最佳的选择。也就是说，它总是做出局部最优的选择，寄希望这样的选择能导致全局最优解。本章介绍一些贪心算法能找到最优解的最优化问题。 贪心算法并不保证得到最优解，但对很多问题确实可以求得最优解。我们首先在16.1节介绍一个简单但非平凡的问题—活动选择问题，这是一个可以用贪心算法求得最优解的问题。首先考虑用动态规划方法解决这个问题，然后证明一直做出贪心选择就可以得到最优解，从而得到一个贪心算法。16. 2节会回顾贪心方法的基本要素，并给出一个直接的方法，可用来证明贪心算法的正确性。16. 3节提出贪心技术的一个重要应用:设计数据压缩编码(Huffman编码)。在16. 4节中，我们讨论一种称为“拟阵"(matroid)的组合结构的理论基础，贪心算法总是能获得这种结构的最优解。最后，16. 5节将拟阵应用于单位时间任务调度问题，每个任务均有截止时间和超时惩罚。 贪心方法是一种强有力的算法设计方法，可以很好地解决很多问题。在后面的章节中，我们会提出很多利用贪心策略设计的算法，包括最小生成树(minimum-spanning-tree)算法(第23章)、单源最短路径的djikstra算法(第24章)，以及集合覆盖问题的Chvatal贪心启发式算法(第35章)。最小生成树算法提供了一个经典的贪心方法的例子。 16.1 贪心选择 假如我们无需求解所有子问题就可以选择出一个活动加人到最优解，将会怎样?这将使我们省去递归式(16. 2)中固有的考查所有选择的过程。实际上，对于活动选择问题，我们只需考虑一个选择:贪心选择。 对于活动选择问题，什么是贪心选择?直观上，我们应该选择这样一个活动，选出它后剩下的资源应能被尽量多的其他任务所用。现在考虑可选的活动，其中必然有一个最先结束。因此，直觉告诉我们，应该选择S中最早结束的活动，因为它剩下的资源可供它之后尽量多的活动使用。(如果S中最早结束的活动有多个，我们可以选择其中任意一个)。换句话说，由于活动已按结束时间单调递增的顺序排序，贪心选择就是活动a,。选择最早结束的活动并不是本问题唯一的贪心选择方法，练习16. 贪心算法的应用 课程名称：算法设计与分析 院系：计算机科学与信息工程学院 学生姓名：**** 学号：********** 专业班级：********************************** 指导教师：****** 201312-27 贪心算法的应用 摘要：顾名思义，贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。贪心算法求问题一般具有两个重要性质：贪心选择性质和最优子结构性质。所谓贪心选择性是指所求问题的整体最优解可以通过一系列局部最优解的选择，即贪心选择达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法主要区别。当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。 背包问题是一个经典的问题，我们可以采用多种算法去求解0/1背包问题，比如动态规划法、分支限界法、贪心算法、回溯法。在这里我们采用贪心法解决这个问题。 关键词：贪心法背包问题最优化 目录 第1章绪论 (3) 1.1 贪心算法的背景知识 (3) 1.2 贪心算法的前景意义 (3) 第2章贪心算法的理论知识 (4) 2.1 问题的模式 (4) 2.2 贪心算法的一般性描述 (4) 第3章背包问题 (5) 3.1 问题描述 (5) 3.2 问题分析 (5) 3.3算法设计 (5) 3.4 测试结果与分析 (10) 第4章结论 (12) 参考文献 (13) 附件 (13) 利用贪婪法实现多种实际问题 《算法设计与分析》课程设计任务书 学院名称：数学与计算机学院专业：信息与计算科学专业年级：2007 一、设计题目 题目十四：利用贪婪算法实现多种实际问题 二、主要内容 给出多种可以用贪婪算法解决的典型问题，并分析、证明、编程。 三、具体要求 （1）贪婪算法的基本思想； （2）给出背包问题的贪婪算法； （3）给出有限期计算机作业调度的贪婪算法； （4）给出上面两个算法的证明； （5）给出上面两个算法的程序。 （6）给出时间复杂度。 四、主要技术路线提示 在用贪婪算法解决资源分配问题、布线问题、0-1背包问题过程中，使用贪婪算法解决问题，通常需要做好以下几个方面的工作： 1、明确问题的求解目标。 2、分析问题所包含的约束条件。 3、建立优化函数。优化函数通常可以通过综合分析问题的求解目标及约束条件归纳出来。 4、制定贪婪准则。 五、进度安排 1、第一周:分析题目的需求，设计抽象数据类型、构思算法、通过类的设计实现抽象数据类型并编写上机程序 2、第二周完成程序开发，进行测试并分析结果，最后撰写课程设计报告 I 利用贪婪法解决实际问题 六、完成后应上交的材料 上交的成果的内容必须由以下四个部分组成，缺一不可。 1．上交源程序：学生按照课程设计的具体要求所开发的所有源程序（应该放到一个文件夹中）。 2．上交程序的说明文件：（保存在.txt中），在说明文档中应该写明上交程序所在的目录，上交程序的主程序文件名，如果需要安装，要有程序的安装使用说明。 3．课程设计报告电子文档：（保存在word 文档中，文件名要求按照“学号姓名算法分析课设报告.doc”起名，如文件名为“200300109张三算法分析课设报告.doc”），按照课程设计的具体要求建立的功能模块，每个模块要求按照如下几个内容认真完成： 其中包括： （1）需求分析： 在该部分中叙述每个模块的功能要求等。 （2）概要设计 在此说明每个部分的算法设计说明（可以是描述算法的流程图），每个程序中使用的存储结构设计说明（如果指定存储结构请写出该存储结构的定义。 （3）详细设计 各个算法实现的源程序，对每个题目要有相应的源程序（可以是一组源程序，每个功能模块采用不同的函数实现）。 源程序要按照写程序的规则来编写。要结构清晰，重点函数的重点变量，重点功能部分要加上清晰的程序注释。 （4）调试分析 包括测试数据，测试输出的结果，时间复杂度分析，和每个模块设计和调试时存在问题的思考（问题是哪些？问题如何解决？），算法的改进设想。 （5）课设总结 总结可以包括：课程设计过程的收获、遇到问题、遇到问题解决问题过程的思考、程序调试能力的思考、对算法设计与分析这门课程的思考、在课程设计过程中对《算法设计与分析》课程的认识等内容。 4．课程设计报告打印稿。 七、推荐参考资料 教材： 《算法设计与分析》 Anany Levitin 著潘彦译清华大学出版社，2007。 《算法设计与分析》宋文等编重庆大学出版社，2001。 参考书：[1] 《算法设计与分析》周培德电子工业出版社，2000。 [2] 《算法设计与分析》王晓东电子工业出版社，2004 指导教师签名日期年月日 系主任审核日期年月日 II 一.迭代算法原理及进展 迭代重建算法的基本原理是：首先对X线光子分布进行原始估计，在此基础上估算每个投影方向上探测器获得的可能计数（即正投影），再将正投影数据与探测器实际采集的投影数据进行比较，用于更新原始估计数据；不断重复此过程，直至下一次迭代结果无限接近由于IR重建时间长，计算复杂，早期IR 法仅在SPECT 和PET等核医学领域得到应用。近年来，得益于计算机技术和图像重建算法的不断发展以及低剂量成像的需求，IR 技术又逐步在CT领域受到广泛关注 目前多家公司推出了多种IR算法，按照迭代计算所利用的数据空间不同，可大致分为3类 （1）仅在图像数据空间进行IR，如IRIS，对原始数据按照传统的 FBP法重建后，再根据噪声模型对获得的图像数据进行多次迭代计算，以降低噪声和伪影。这种方法运算较快，计算时间仅稍长于FBP法，但由于基于FBP图像进行迭代计算，不可避免地具有FBP 法“理想系统”假设的局限性。 （2）在投影数据空间和图像数据空间中均进行IR，如ASIR、SAFIRE、iDose和 AIDR。首先对投影数据以FBP法进行重建，将获得的图像数据与基于统计的、考虑到光子和电子噪声的理想噪声模型进行比较，去除噪声，得到校正图像，对此图像再通过正投影更新原始投影数据，用于下次迭代计算，如此进行多次IR。这种方法重建速度也较快，但同样具有 FBP法的局限性。 （3）仅在投影数据空间进行IR，如 IMR ,MBIR（即Veo技术），对 X线束从焦点到探测器的整个过程建立多个模型，焦点、X线束、体素和探测器的几何形状均被考虑进去，最为复杂，计算量最大，整个重建过程需 10～90min。使用这些技术的意义在于可在大幅降低CT辐射剂量的同时获得与常规FBP法相同、甚至更好的图像质 贪心算法详解 贪心算法思想： 顾名思义，贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。 贪心算法的基本要素： 1.贪心选择性质。所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。 动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。 对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。 2. 当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的 最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。 贪心算法的基本思路： 从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到算法中的某一步不能再继续前进时，算法停止。 该算法存在问题： 1. 不能保证求得的最后解是最佳的； 2. 不能用来求最大或最小解问题； 3. 只能求满足某些约束条件的可行解的范围。 实现该算法的过程： 从问题的某一初始解出发； while 能朝给定总目标前进一步do 求出可行解的一个解元素； 由所有解元素组合成问题的一个可行解； 用背包问题来介绍贪心算法： 背包问题：有一个背包，背包容量是M=150。有7个物品，物品可以分割成任意大小。要 求尽可能让装入背包中的物品总价值最大，但不能超过总容量。 答：贪婪算法（Greedy algorithm）是一种对某些求最优解问题的更简单、更迅速的设计技术。用贪婪法设计算法的特点是一步一步地进行，常以当前情况为基础根据某个优化测度作最优选择，而不考虑各种可能的整体情况，它省去了为找最优解要穷尽所有可能而必须耗费的大量时间，它采用自顶向下，以迭代的方法做出相继的贪心选择，每做一次贪心选择就将所求问题简化为一个规模更小的子问题，通过每一步贪心选择，可得到问题的一个最优解，虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的，所以贪婪法不要回溯。 贪婪算法是一种改进了的分级处理方法。其核心是根据题意选取一种量度标准。然后将这多个输入排成这种量度标准所要求的顺序，按这种顺序一次输入一个量。如果这个输入和当前已构成在这种量度意义下的部分最佳解加在一起不能产生一个可行解，则不把此输入加到这部分解中。这种能够得到某种量度意义下最优解的分级处理方法称为贪婪算法。 对于一个给定的问题，往往可能有好几种量度标准。初看起来，这些量度标准似乎都是可取的，但实际上，用其中的大多数量度标准作贪婪处理所得到该量度意义下的最优解并不是问题的最优解，而是次优解。因此，选择能产生问题最优解的最优量度标准是使用贪婪算法的核心。 一般情况下，要选出最优量度标准并不是一件容易的事，但对某问题能选择出最优量度标准后，用贪婪算法求解则特别有效。最优解可以通过一系列局部最优的选择即贪婪选择来达到，根据当前状态做出在当前看来是最好的选择，即局部最优解选择，然后再去解做出这个选择后产生的相应的子问题。每做一次贪婪选择就将所求问题简化为一个规模更小的子问题，最终可得到问题的一个整体最优解。其有以下特性： ⑴ 有一个以最优方式来解决的问题。为了构造问题的解决方案，有一个候选的对象的集合：比如不同面值的硬币。 ⑵ 随着算法的进行，将积累起其它两个集合：一个包含已经被考虑过并被选出的候选对象，另一个包含已经被考虑过但被丢弃的候选对象。 ⑶ 有一个函数来检查一个候选对象的集合是否提供了问题的解答。该函数不考虑此时的解决方法是否最优。 ⑷ 还有一个函数检查是否一个候选对象的集合是可行的，也即是否可能往该集合上添加更多的候选对象以获得一个解。和上一个函数一样，此时不考虑解决方法的最优性。 ⑸ 选择函数可以指出哪一个剩余的候选对象最有希望构成问题的解。 ⑹ 最后，目标函数给出解的值。 从贪心算法的定义可以看出，贪心法并不是从整体上考虑问题，它所做出的选择只是在某种意义上的局部最优解，而由问题自身的特性决定了该题运用贪心算法可以得到最优解。 我们看看下面的例子 例1 均分纸牌（NOIP2002tg） [问题描述] 有 N 堆纸牌，编号分别为 1，2，…, N。每堆上有若干张，但纸牌总数必为 N 的倍数。可以在任一堆上取若干张纸牌，然后移动。移牌规则为：在编号为 1 堆上取的纸牌，只能移到编号为 2 的堆上；在编号为 N 的堆上取的纸牌，只能移到编号为 N-1 的堆上；其他堆上取的纸牌，可以移到相邻左边或右边的堆上。现在要求找出一种移动方法，用最少的移动次数使每堆上纸牌数都一样多。例如 N=4，4 堆纸牌数分别为： ①9 ②8 ③17 ④6 移动3次可达到目的： 从③取 4 张牌放到④（9 8 13 10） -> 从③取 3 张牌放到②（9 11 10 10）-> 从②取 1 张牌放到①（10 10 10 10）。 [输入]：键盘输入文件名。 文件格式：N（N 堆纸牌，1 <= N <= 100） A1 A2 … An （N 堆纸牌，每堆纸牌初始数，l<= Ai <=10000） [输出]：输出至屏幕。格式为：所有堆均达到相等时的最少移动次数。 [输入输出样例] ： 4 9 8 17 6 屏慕显示：3 算法分析：设a[i]为第i堆纸牌的张数（0<=i<=n），v为均分后每堆纸牌的张数，s为最小移到次数。 我们用贪心法，按照从左到右的顺序移动纸牌。如第i堆(0 贪婪算法在资源分配问题中的应用 彭鹏 贵州财经学院研究生 摘要：贪婪算法的典型应用是解决优化问题，这类算法的策略是只顾眼前，而不考虑以后的影响，它的算法简单容易设计实现，因此在许多实际问题中得到广泛的应用，但是它也存在许多的问题，巧妙的使用贪婪思想，将其融入到资源分配问题中解题中，资源分配问题便焕发出了新的光彩。 本文首先对贪婪算法的基本概念做了介绍，然后通过实例论述了贪婪算法在资源分配问题中的应用。 关键字：贪婪算法研究应用资源分配问题 第一章贪婪算法的概念 1.1什么是贪婪算法 贪婪算法是一种对某些求最优解问题的更简单、更迅速的设计技术。用贪婪法设计算法的特点是一步一步地进行，常以当前情况为基础根据某个优化测度作最优选择，而不考虑各种可能的整体情况，它省去了为找最优解要穷尽所有可能而必须耗费的大量时间，它采用自顶向下,以迭代的方法做出相继的贪心选择,每做一次贪心选择就将所求问题简化为一个规模更小的子问题, 通过每一步贪心选择,可得到问题的一个最优解，虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的，所以贪婪法不要回溯。 贪婪算法是一种改进了的分级处理方法。其核心是根据题意选取一种量度标准。然后将这多个输入排成这种量度标准所要求的顺序，按这种顺序一次输入一个量。如果这个输入和当前已构成在这种量度意义下的部分最佳解加在一起不能产生一个可行解，则不把此输入加到这部分解中。这种能够得到某种量度意义下最优解的分级处理方法称为贪婪算法。 对于一个给定的问题，往往可能有好几种量度标准。初看起来，这些量度标准似乎都是可取的，但实际上，用其中的大多数量度标准作贪婪处理所得到该量度意义下的最优解并不是问题的最优解，而是次优解。因此，选择能产生问题最优解的最优量度标准是使用贪婪算法的核心。 一般情况下，要选出最优量度标准并不是一件容易的事，但对某问题能选择出最优量度标准后，用贪婪算法求解则特别有效。最优解可以通过一系列局部最优的选择即贪婪选择来达到,根据当前状态做出在当前看来是最好的选择，即局部最优解选择，然后再去解做出这个选择后产生的相应的子问题。每做一次贪婪选择就将所求问题简化为一个规模更小的子 贪心算法的应用实例 例2．排队问题 【题目描述】 在一个医院B 超室，有n个人要做不同身体部位的B超，已知每个人需要处理的时间为ti，（0 贪心算法的实际应用 姓名： 班级： 学号： 指导老师： 定义： 贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。 贪婪算法（Greedy algorithm）是一种对某些求最优解问题的更简单、更迅速的设计技术。用贪婪法设计算法的特点是一步一步地进行，常以当前情况为基础根据某个优化测度作最优选择，而不考虑各种可能的整体情况，它省去了为找最优解要穷尽所有可能而必须耗费的大量时间，它采用自顶向下，以迭代的方法做出相继的贪心选择，每做一次贪心选择就将所求问题简化为一个规模更小的子问题，通过每一步贪心选择，可得到问题的一个最优解，虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的，所以贪婪法不要回溯。 贪婪算法是一种改进了的分级处理方法。其核心是根据题意选取一种量度标准。然后将这多个输入排成这种量度标准所要求的顺序，按这种顺序一次输入一个量。如果这个输入和当前已构成在这种量度意义下的部分最佳解加在一起不能产生一个可行解，则不把此输入加到这部分解中。这种能够得到某种量度意义下最优解的分级处理方法称为贪婪算法。 对于一个给定的问题，往往可能有好几种量度标准。初看起来，这些量度标准似乎都是可取的，但实际上，用其中的大多数量度标准作贪婪处理所得到该量度意义下的最优解并不是问题的最优解，而是次优解。因此，选择能产生问题最优解的最优量度标准是使用贪婪算法的核心。 一般情况下，要选出最优量度标准并不是一件容易的事，但对某问题能选择出最优量度标准后，用贪婪算法求解则特别有效。最优解可以通过一系列局部最优的选择即贪心选择来达到，根据当前状态做出在当前看来是最好的选择，即局部最优解选择，然后再去解做出这个选择后产生的相应的子问题。每做一次贪婪选择就将所求问题简化为一个规模更小的子问题，最终可得到问题的一个整体最优解。 一、引言核医学影像设备如单光子断层扫描仪(SinglePositronEmissionComputeTomography，SPECT)、正电子发射断层扫描仪(PositronEmissionTomo-graphy，PET)融合了当今最高层次的核医学技术，是目前医学界公认的极为先进的大型医疗诊断成像设备，在肿瘤学、心血管疾病学和神经系统疾病学研究中，以及新医药学开发研究等领域中已经显示出它卓越的性能。随着核医学断层影像设备的广泛应用和计算机技术的迅速发展，图像重建方法作为该类设备中的一个关键技术，其研究工作越来越受到人们的重视。本文概述了传统的图像重建方法，并详细介绍了一种具有较高图像质量和较短计算时间的重建算法—有序子集最大期望值方法(Ord-eredSubsetsExpectationMaximization，OSEM)在核医学影像设备中的应用。二、传统的图像重建方法在核医学影像设备中，需要根据物体某一层面在不同探测器上检测到的投影值来重建该断层图像层面，即二维图像重建。传统的图像重建方法主要分为解析法和迭代法。解析法是以中心切片定理(CentralSliceTheorem)为理论基础的求逆过程。常用的一种解析法称为滤波反投影法(FilteredBack-Projection，FBP)。FBP法首先在频率空间对投影数据进行滤波，再将滤波后的投影数据反投影得到重建断层图像。滤波器选为斜坡函数和某一窗函数的乘积，窗函数用于控制噪声，其形状权衡着统计噪声和空间分辨。常用的窗函数有Hanning窗，Hamming窗，Butterworth窗以及Shepp-Logan窗。解析法的优点是速度快，可用于临床实时断层重建。但当测量噪声较大或采样不充分时，这类算法的成像效果不甚理想，尤其是在核医学断层图像重建中对小尺寸源的成像效果差(即所谓偏体积效应)。在滤波中如果对高频信号不做抑制，截止频率高，此时空间分辨最好，但所重建的图像不平滑，易产生振荡和高频伪影;反之，采用较低截止频率，过多压抑高频成分的低通窗函数会造成重建图像的模糊，故在变换法中低噪声和高分辨对滤波器的要求是矛盾的，需折衷选择。且难以在重建中引入各种校正和约束，如衰减校正等。迭代法是从一个假设的初始图像出发，采用迭代的方法，将理论投影值同实测投影值进行比较，在某种最优化准则指导下寻找最优解。迭代求解方法的基本过程是: (1)假定一初始图像f(0); (2)计算该图像投影d; (3)同测量投影值d对比; (4)计算校正系数并更新f值; (5)满足停步规则时，迭代中止; (6)由新的f 作为f(0)从(2)重新开始。该方法最大优点之一是可以根据具体成像条件引入与空间几何有关的或与测量值大小有关的约束和条件因子，如可进行对空间分辨不均匀性的校正、散射衰减校正、物体几何形状约束、平滑性约束等控制迭代的操作。其中实现对比的方法有多种，施加校正系数的方法也有多种。在某些场合下，比如在相对欠采样、低计数的核医学成像中可发挥其高分辨的优势。但是迭代法收敛速度慢，运算时间长，运算量大，而且重建图像会随着迭代次数的增加而趋于“老化”甚至发散，出现高频伪影，这些缺点极大地限制了它在临床中的应用。 [!--empirenews.page--]三、OSEM迭代算法为了加快收敛速度，减少运算时间，提高图像质量，人们提出了很多快速算法，其中有序子集最大期望值法是很有应用前景的一种快速迭代重建算法，它是在最大似然期望法(MaximumLike-lihoodExpectationmaximization，MLEM)的基础上发展起来的。 MLEM方法旨在寻找与测量的投影数据具有最大似然性(ML)的估计解，其迭代过程是由最大期望值算法(EM)来实现的。由于是以统计规律为基础，MLEM重建法具有很好的抗噪声能力，是目前公认为最优秀的迭代重建算法之一，尤其是在处理统计性差的数据时，更能显示出它相对于解析法的优越性，但是这种方法仍然存在迭代法的运算量大、运算时间长等缺点。MLEM方法在每一次迭代过程中，使用所有的投影数据对重建图像每一个象素点的值进行校正，重建图像只被替换一次。 OSEM方法在每一次迭代过程中将投影数据分成N个子集，每一个子集对重建图像各象素点值校正以后，重建图像便被更新一次，所有的子集运算一遍，称为一次迭代过程，它所需要的运算时间与FBP重建的时间基本相等。在ML-EM方法一次迭代过程中，重建图像被更新一次，而在OSEM方法中重建图像被更新N次，所以OSEM方法具有加快收敛的作用。 压缩感知重构算法之子空间追踪(SP) 如果掌握了压缩采样匹配追踪(CoSaMP)后，再去学习子空间追踪(Subspace Pursuit)是一件非常简单的事情，因为它们几乎是完全一样的。 SP的提出时间比CoSaMP提出时间略晚，首个论文版本是参考文献[1]，后来更新了两次，最后在IEEE Transactions on Information Theory发表[2]。从算法角度来讲，SP与CoSaMP差别非常小，这一点作者也意识到了，在文献[1]首页的左下角就有注释： 在文献[2]第2页提到了SP与CoSaMP的具体不同： 从上面可以知道，SP与CoSaMP主要区别在于“Ineach iteration, in the SP algorithm, only K new candidates are added, while theCoSAMP algorithm adds 2K vectors.”，即SP每次选择K个原子，而CoSaMP则选择2K个原子；这样带来的好处是“This makes the SP algorithm computationally moreefficient,”。 以下是文献[2]中的给出的SP算法流程： 这个算法流程的初始化(Initialization)其实就是类似于CoSaMP的第1次迭代，注意第(1)步中选择了K个原子：“K indices correspo nding to the largest magnitude entries”，在CoSaMP里这里要选择2K个最大的原子，后面的其它流程都一样。这里第(5)步增加了一个停止迭代的条件：当残差经过迭代后却变大了的时候就停止迭代。 不只是SP作者认识到了自己的算法与CoSaMP的高度相似性，CoSaMP的作者也同样关注到了SP算法，在文献[3]中就提到： 文献[3]是CoSaMP原始提出文献的第2个版本，文献[3]的早期版本[4]是没有提及SP算法的。 鉴于SP与CoSaMP如此相似，这里不就再单独给出SP的步骤了，参考《压缩感知重构算法之压缩采样匹配追踪(CoSaMP)》，只需将第(2)步中的2K改为K即可。 实验报告 课程算法设计与分析实验实验名称贪心算法设计与应用第 1 页一、实验目的 理解贪心算法的基本原理，掌握贪心算法设计的基本方法及其应用； 二、实验内容 (一)Huffman编码和译码问题： 1．问题描述 给定n个字符在文件中的出现频率，利用Huffman树进行Huffman编码和译码。设计一个程序实现： 1.输入含n(n<=10)个字符的字符集S以及S中各个字符在文件中的出现频 率，建立相应的Huffman树，求出S中各个字符的Huffman编码。 2.输入一个由S中的字符组成的序列L，求L的Huffman 编码。 3. 输入一个二进制位串B，对B进行Huffman译码，输出对应的字符序列； 若不能译码，则输出无解信息。 提示：对应10 个字符的Huffman树的节点个数<211。 2．测试数据 Input n=5 字符集合S={a, b, c, d, e}, 对应的频率分别为 a: 20 b: 7 c: 10 d: 4 e: 18 字符序列L=ebcca 二进制位串B=01100111010010 Output S中各个字符的Huffman编码：（设Huffman树中左孩子的权<=右孩子的权）a: 11 b: 010 c: 00 d: 011 e: 10 L的Huffman 编码：10010000011 B对应的字符序列： dcaeeb 若输入的B=01111101001，则无解 (二) 加油问题（Problem Set 1702）： 1.问题描述 一个旅行家想驾驶汽车从城市A到城市B（设出发时油箱是空的）。给定两个 城市之间的距离dis、汽车油箱的容量c、每升汽油能行驶的距离d、沿途油站数n、油站i离出发点的距离d[i]以及该站每升汽油的价格p[i],i=1,2,…,n。设d[1]=0 2019年1月第26卷第2期 自适应统计迭代重建与基于模型迭代重建算法 在超低剂量儿童胸部CT中的比较 赵凯宇宣伟玲陆洪江 尽管单次CT扫描有效剂量（1～12mSv）的长期风险很小且不确定，但CT仍是诊断性放射线暴露增加的最大因素，与成人相比，儿童对辐射更加敏感[1]。因此，如何在不影响诊断质量的前提下，最大限度减少被检者接受的辐射剂量很有必要。由于胸部CT扫描在儿童CT检查中占重较大，本文将比较超低剂量胸部CT中自适应统计迭代重建（ASIR）与基于模型的迭代重建（MBIR）的表现并评估辐射剂量减少程度的意义。 1 对象与方法 1.1 对象2016年11月至2017年6月杭州市儿童医院接受超低剂量胸部CT扫描的患者63例，平均年龄（13±3.7）岁，男35例，女28例，其中肺部转移随访28例（44.4%），肺部感染随访17例（27.0%），骨性胸廓评估16例（25.4%），先天性畸形评估2例（3.2%）。根据记录的所有患者的体重和身高计算体质量指数。 1.2 C T扫描协议采用64层螺旋C T扫描，参数：层厚5mm，视野32cm，螺距1.375，旋转时间0.5秒，管电压 作者单位：310014 杭州市儿童医院放射科（赵凯宇）；杭州市西溪医院放射科（宣伟玲）；解放军第117医院放射科（陆洪江） 通信作者：赵凯宇，Email:49340705@https://www.wendangku.net/doc/4b2227266.html, （80或100 kVp）和管电流（10mA或20mA）根据患者的体形大小使用。使用MBIR和ASIR重建技术将原始数据重建为轴位2.5mm层厚。尽管用两种技术重建了轴位和冠状图像，但只用轴位图像进行分析。 1.3客观图像分析由两名对本观察不知情的放射科医师在影像归档和通信系统（P AC S）工作站，按随机顺序对每次重建的图像用感兴趣区域（ROI）内的标准差进行图像噪声测量。将圆形或椭圆形ROI（直径约10mm）置于气管分叉处的降主动脉、椎旁肌、气管和肺实质。为了避免部分容积效应，R O I不能与相邻组织重叠。 1.4 主观图像分析影像学质量的主观分析包括病变可检测性由3名对本研究不知情的放射科医师完成。对经MB IR和ASIR重建的轴位图像，按照个人习惯对纵隔窗和肺窗的窗宽、窗位进行调整。根据计算机断层扫描质量标准指南评估图像质量，包括正常微小结构的可见性（肺外侧2cm的血管，次级支气管壁和裂隙）。如果有病变，根据肺部局灶性病变的可见性和类型（肺不张、实变、结节、毛玻璃样影）评估病变可检测性。当整体图像质量（包括病变可检测性）较好地满足诊断要求，并与预期标准剂量CT图像相当则评为优秀；如果整体图像质量满足诊断要求但低于标准剂量CT则评为可以接受；如果图像质量不能满足诊断要求，则评为不可接受。 【摘要】目的比较自适应统计迭代重建（ASIR）与基于模型的迭代重建（MBIR）两种算法在超低剂量儿童胸部CT扫描中的图像质量和辐射剂量。方法2016年11月至2017年6月杭州市儿童医院接受超低剂量胸部CT扫描的患者63例，分别用MBIR和ASIR算法重建。由两名放射科医师评估两种重建算法的主观和客观图像质量，并对患者超低剂量胸部CT扫描得到的辐射剂量与先前胸部CT扫描（标准剂量或低剂量扫描方案）的辐射剂量进行评估。结果MBIR算法的主观和客观图像质量均优于ASIR。MBIR显示为100%的诊断可接受性，但ASIR在平均0.33mSv （0.14～0.59mSv）超低剂量CT中显示为93%。在接受先前CT检查的患者中，超低剂量CT的特定剂量估计（SSDE）和剂量长度乘积（DLP）平均下降87%（35%～97%）和85%（41%～98%）。结论与ASIR相比，MBIR明显改善图像质量。此外，在诊断可接受的超低剂量胸部CT中，采用MBIR算法辐射剂量减少近90%。 【关键字】自适应统计迭代重建；基于模型的迭代重建；超低剂量；儿童胸部CT 45 贪心算法浅析 摘要：本文讲述了贪心算法的基本思路及实现过程，贪心算法的特点、存在的问题以及应用。并通过贪心算法的特点举例列出了几个经典问题，通过对问题的探讨和研究，对贪心算法有了更加深入的了解。 关键词：贪心算法；最优解；最优子结构问题；删数问题；活动安排问题 贪心算法的基本思路及实现过程 1贪心的基本思想 用局部解构造全局解，即从问题的某一个初始解逐步逼近给定的目标，以尽可能快地求得更好的解。当某个算法中的某一步不能再继续前进时，算法停止。贪心算法思想的本质就是分治，或者说：分治是贪心的基础。每次都形成局部最优解，换一种方法说，就是每次都处理出一个最好的方案。 利用贪心策略解题，需要解决两个问题： （1）该题是否适合于用贪心策略求解； （2）如何选择贪心标准，以得到问题的最优/较优解。 2贪心算法的实现过程 （1）应用同一规则F，将原问题变为一个相似的、但规模更小的子问题； （2）从问题的某一初始解出发： While（能朝给定目标前进一步） 求出可行解的一个解元素； （3）由所有解元素组合成问题的一个可行解。 贪心算法的特点 贪心算法的最大特点就是快，通常是线性二次式，不需要多少额外的内存。一般二次方级的存储要浪费额外的空间，而且那些空间经常得不出正解。但是，使用贪心算法时，这些空间可以帮助算法更容易实现且更快执行。如果有正确贪心性质存在，那么一定要采用。因为它容易编写，容易调试，速度极快，并且节约空间。几乎可以说，此时它是所有算法中最好的。但是应该注意，贪心算法有两大难点： （1）如何贪心 怎样用一个小规模的解构造更大规模的解呢?总体上，这与问题本身有关。但是大部分都是有规律的。正因为贪心有如此性质，它才能比其他算法快。 具有应当采用贪心算法的问题，当“贪心序列”中的每项互异且当问题没有重叠性时，看起来总能通过贪心算法取得（近似）最优解的。或者，总有一种直觉在引导我们对一些问题采用贪心算法。其中“找零钱”这个问题就是一个例子。题中给出的硬币面值事实上具有特殊性，如果面值发生变化，可能贪心算法就不能返回最优解了。但是，值得指出的是，当一个问题具有多个最优解时，贪心算法并不能求出所有最优解。另外，我们经过实践发现，单纯的贪心算法是顺序处理问题的；而且每个结果是可以在处理完一个数据后即时输出的。 （2）贪心的正确性 要证明贪心性质的正确性，才是贪心算法的真正挑战，因为并不是每次局部最优解都会与整体最优解之间有联系，往往靠贪心算法生成的解不是最优解。这样，贪心性质的证明就成了贪心算法正确的关键。对某些问题贪心性质也许是错的，即使它在大部分数据中都是可行的，但还必须考虑到所有可能出现的特殊情况，并证明该贪心性质在这些特殊情况中仍然正确。而这样容易陷入证明不正确贪心性质的泥塘中无法自拔，因为贪心算法的适用范围并不大，而且有一部分极难证明，若是没有把握，最好不要冒险，还有其他算法会比它要保险。 贪心算法存在的问题 （1）不能保证求得的最后解是最佳的。由于贪心策略总是采用从局部看来是最优的选择，因此并不从整体上加以考虑； （2）贪心算法只能用来求某些最大或最小解的问题； （3）贪心算法只能确定某些问题的可行性范围 贪心算法的应用 1哈夫曼编码 2 0-1背包问题 3磁盘文件的存储 4生产调度问题 5信息查询 在过去的三十多年里, 随着X射线球管、探测器技术、CT系统设计、图像重建算法以及计算机技术的不断发展, CT图像质量明显提高。尤其是在最近十多年里, 多层CT技术的迅猛发展使CT的诊断能力和扫描速度显著提高, 大大扩展了CT在临床上的应用范围。CT已经越来越多的替代常规X射线检查, 如各种血管成像(CTA)。这使得接受CT检查的人群数量逐年大幅增加。据2007年有关文献[1]报道, 1990年美国约有130万人次接受CT检查, 2000年为460万人次, 而当时预计2007年将高达687万人次。相对于普通X射线检查而言, CT 检查是辐射剂量非常高的检查(胸部普通X射线检查的有效剂量为0.02~0.2mSv, CT为5~7mSv)。统计显示[2]美国CT检查的数量只占整个放射学检查数量的11%~13%, 但CT检查的辐射剂量竟占整个放射学检查的2/3。随着CT检查数量的不断增加, 人们在感谢CT为人类健康做出巨大贡献的同时, 越来越多的人开始担忧CT辐射带来的潜在危害。 CT技术诞生以来, 人们已经发展了众多的图像重建算法, 但各种算法均存在着各自的优缺点。解析重建(Analytic Reconstruction, AR)和迭代重建(Iterative Reconstruction, IR)是CT 图像重建的两种基本方法。滤过反投影(Filtered Back Projection, FBP)是解析重建的主要算法, 代数重建算法(Algebraic Reconstruction Technique, ART)是迭代重建中常用的算法。虽然世界上第一台医用CT就采用ART, 但FBP很快就代替ART成为CT图像重建的“金标准[3]”, 这是由于ART计算速度慢、所需存储空间大, 在计算机技术水平不是很高的年代, 它的应用和发展受到了限制。 基于对CT辐射危害的考虑, 多年来众多CT科学家、制造商和临床操作人员为控制和降低CT辐射剂量做出了不懈的努力, 在硬件和软件上做出了诸多改进, 研究出了很多的方法[4], 如自动曝光控制技术(Automatic Exposure Control, AEC), 但该方法对于辐射剂量的降低程度依然有限, 这主要是由于FBP的内在特征决定的。FBP是基于解析重建方式, 图像重建具有闭合形式的解, 其过程是反求公式, 每组投影数据都要经过校准、滤波、反投影、加权, 当最后一组采集的投影数据处理完成, 整个重建过程结束并产生最终重建的图像。FBP 重建速度较快, 但它要求每次投影测量数据是精确定量的和完全的, X射线光子统计波动对它有很大影响, 它对噪声和伪影都很敏感。当辐射剂量降低或投影数据采集不足时, 重建出的图像质量就会很差, 因此使用FBP就不能大幅度降低辐射剂量。 统计迭代重建在发射断层成像(SPECT、PET)的成功应用表明, 即使在低信噪比(Signal Noise Ratio, SNR)的发射数据集利用FBP重建得到的图像质量极差时, 迭代重建仍然可以重建出高质量的图像。迭代重建的基本重建原理如下：对于某个重建视角, 首先在估计的物体图像上通过“前后投影”计算一个综合投影, 这是对沿着该视角的衰减的第一次估计, 但存在较大误差; 这种估计尽可能地模拟真实CT系统中X射线光子穿过物体并到达探测器的过程, 通过将X射线光子的初始位置设置在一个小区域而非单独的点来模拟有限的焦点大小；在X射线光子和物体相互作用的建模过程中, 通过计算光子在轻微不同方向和位置进入体素的路径长度来考虑重建像素的大小和尺寸(而不是一个假想的点)；采用相同的方式, 探测器单元的大小和形状通过探测器响应函数来建模。将综合投影与实际测量的投影相比较, 两者间的差异代表了当前估计需要校正的量, 图像校正的目的是使误差最小化。在校正过程中, 由有限光子统计导致的投影测量波动也被考虑了, 同时也评估每个独立测量中的光子统计并将这个信息用于图像校正过程。如果某个体素值与周围体素的值显著不同, 这种差异不能反映病人真实的解剖结构, 更可能是由于统计波动或图像噪声引起的, 即使是一个小血管也应该和血管树相连而非一个孤立的象素。当所有这些信息被考虑的时候, 当前的重建图像就被校正了, 这个图像再通过以上的综合和校正过程来获得一个更新的图像, 当重建图像和原算法导论-贪心算法
【精选】贪心算法的应用
利用贪婪算法实现多种实际问题
迭代重建技术
贪心算法详解分析
贪婪算法
贪心算法的应用
贪婪算法在资源分配问题中的应用----彭鹏
贪心算法的应用实例
贪心算法的实际应用
核医学图像重建快速迭代算法OSEM
贪婪算法中,SP算法的原理介绍及MATLAB仿真
贪心算法设计与应用
自适应统计迭代重建与基于模型迭代重建算法在超低剂量儿童胸部CT中的比较
贪心算法浅析
迭代算法