文档介绍：第三部分算法设计方法
整理课件
2022/5/27
1
相关章节
Chapter13 贪婪算法
Chapter14 分而治之算法
Chapter15 动态规划
Chapter16 回溯
Chapter1个阶段，都作出一个看上去最优的决策（在一定的标准下）。决策一旦作出，就不再可更改。
作出贪婪决策的依据成为贪婪准则
2、贪婪算法思想
整理课件
2022/5/27
19
贪心算法的基本思路如下：1. 建立数学模型来描述问题2. 把求解的问题分成若干个子问题3. 对每一子问题求解，得到子问题的局部最优解
4. 把子问题的解局部最优解合成原来解问题的一个解
贪婪算法思想（续1）
整理课件
2022/5/27
20
实现该算法的过程：从问题的某一初始解出发；while 能朝给定总目标前进一步 do　　求出可行解的一个解元素；由所有解元素组合成问题的一个可行解；
贪婪算法思想（续2）
整理课件
2022/5/27
21
例13-4 找零钱问题
整理课件
2022/5/27
22
贪婪算法有一种直觉的倾向，
例如：在找零钱时，直觉告诉我们应使找出的硬币数目最少（至少是接近最少的数目）
整理课件
2022/5/27
23
例13-5 机器调度问题
使用7台机器
使用5台机器
整理课件
2022/5/27
24
一种获取最有分配的贪婪方法是逐步分配任务。每步分配一件任务，且按照任务的非递减顺序进行分配。
若已经至少有一件任务分配给某台机器，则称这台机器是旧的；若机器非旧则它就是新的。
在选择机器时，遵循的贪婪法则为：根据欲分配任务的开始时间，若此时有旧的机器可用，则将任务分配给旧机器。否则，任务分配给新机器
贪婪算法求解：机器调度
整理课件
2022/5/27
25
<机器调度> （续）
首先，按照任务时间区间递增排列（可以使用堆）
然后，按照贪婪准则“先旧后新”将任务分配给机器
整理课件
2022/5/27
26
例13-6 最短路径
贪婪算法
不一定能获取
最优解！
1-> 3-> 4-> 2-> 5：10
1->4->5：6
整理课件
2022/5/27
27
总结
贪婪算法并不总能保证得到最优解
启发式算法：算法并不保证得到最优解，但是通常所得结果与最优解相差无几或很接近。
例如：机器调度算法
启发式算法具有直觉倾向
近似算法：具有限定功能的启发式算法
整理课件
2022/5/27
28
3、应用1：货箱装船
整理课件
2022/5/27
29
假设n=8, c=400
[w1 , ... w8 ]=[100, 200, 50, 90, 150, 50, 20, 80]
利用贪婪算法时，所考察货箱的顺序为7, 3 , 6 , 8 , 4 , 1 , 5 , 2。
货箱7, 3 , 6 , 8 , 4 , 1的总重量为390个单位且已被装载，剩下的装载能力为10个单位，小于剩下的任何一个货箱。
在这种贪婪解决算法中得到[x1 , ..., x8 ]  = [ 1 , 0 , 1 , 1 , 0 , 1 , 1 , 1 ]且
可以证明：利用贪婪算法能产生最佳装载
整理课件
2022/5/27
30
货箱装载的C++算法实现
void IndirectSort(int w[], int t[], int n)
{
//假设w已经按照重量升序排列
for (int i=1; i <= n; i++) t[i] = i;
}
整理课件
2022/5/27
31
template<class T>
bool IndirectList<T>::Bubble(int n)
{
bool swapped = false; // no swaps so far
for (int i = 0; i < n - 1; i++)
if (*table[i] > *table[i+1]) {
Swap(table[i], table[i + 1]);
swapped = true; }
return swapped;
}
template<class T>
IndirectList<T>& IndirectList<T>::BubbleSort()
{
for (int i = length; i > 1 && Bubble(i); i--);
return *this;
}
整理课件
2022/5/27
32
3、应用2：0/1背包问题
整理