数据结构与算法--贪婪算法

贪婪算法

贪婪算法分阶段地工作。在每个阶段，可以认为所做决定是最好的，而不考虑将来的后果。通常这意味着选择的是某个局部最优。这种“当前能获得的最优就拿”的策略是这类算法的名字来源。当算法终止时候，我们希望的到累积的局部最优解就等于全局最优，如果是这样的，那么算法就是正确的；否则算法得到的是一个次优解（suboptimal solution）。如果不需要绝对的最佳答案，那么有时候使用简单的贪婪算法生成近似的答案能得到一个时间复杂度更优的解。

案例分析

举几个现实的贪婪算法的例子，明显的是货币找零问题。

使用RMB找零钱，我们重复的配发最大额货币。于是为了找十七块六毛，我们拿出一张10元，一张5元，2张1元（2元货币现在少见了），加一个5毛硬币，两个一毛硬币。这么做，我们能保证使用最少的钞票和硬币，这个算法不是对每种货币通用，但是RMB是有效的

交通问题

以下会详细讲解两个案例，来说明贪婪算法的应用，第一个模拟调度问题，第二个模拟文件压缩算法，他是计算机科学最早的成果之一。

一个简单的调度问题

假设我们计算机系统由任务j1，j2，j3 …jN，已知对应的运行时间分别是t1，t2，t3…tN，而处理器只有一个，为了把作业平均完成的时间最小化，调度这些作业的最好方式是什么？？？假设我们讨论的都是非预占调度（nonpreemptive scheduling）：一旦开始一个任务就必须吧任务执行完。我们用以下案例简化，四个作业，已经运行时间，如下表格，一个可能的调度在图一中表示：上图中j1 用时15个时间单位运行结束，j2用时23=（15+j2时间） 个时间单位，j3,用26，j4用36，所以平均完成时间是25。但是一个更好的调度完成时间是17.75 ，如下图中：

上图中给出的调度是按照最短的作业先完成来进行的。我们可以证明这种模式总会产生一个最优的调度，令调度表中的作业是j1，j2，j3，j4，…jn。第一个作业完成时间t_1，第二个作业t_1+t_2后完成，第三个作业依次类推，由此可以得到调度的总代价C有如下推论：

C = t_1 + (t_1+t_2) + (t_1+t_2+t_3) + ......+(t_1+t_2+t_3+......+t_n)C = nt_1 + (n-1)t-2 + (n-2)t_3 + (n-3)t_4 + ....+ 2t_(n-1) + t_(n-1)C = (n-1+1)t_1 + (n-2+1)t_2 + ... + (n-(n-1)+1)t_(n-1) + (n-n+1)t_n

如上累加： ∑ k = 1 n \sum_{k=1}^n ∑k=1n​(n-k+1)tk = ∑ k = 1 n \sum_{k=1}^n ∑k=1n​(n+1)tk - ∑ k = 1 n \sum_{k=1}^n ∑k=1n​k*tk如上表达是可以看成，调度总时间和 ∑ k = 1 n \sum_{k=1}^n ∑k=1n​k*tk 成反比，k表示第几个位置执行，tk表示指定第k次执行的时间，当这个数值越大，那么总的时间就越少，那么我们将权重越大的往后放就能得到最小值。

多处理器情况

我们可以把问题扩展到多个处理器的情况，我们还是这些作业j1，j2，j3，j4，…jn。，时间t1，t2，t3…tN，另外有处理器P个。假设作业是有序的，最短的运行时间最先处理，加入P = 3.如下表格如上图他平均完成时间优化到了最小，作业1,4，7在处理器1 上运行，处理器二在2,5，8 上，处理器3 处理其余作业，总完成时间是165，平均是165/9 = 18.33解决多处理器情形的算法是按顺序开始作业，处理器之间轮换分配罪业，不难证明没有那个其他顺序能做到更好。但是还有其他顺序的最优解，如下图：

如上，还是最小的先执行，只是我们将是哪个处理器处理的任务换了换而已

将最后完成时间最小化

还需要考虑一个非常类似情况，假设我们只关注最后的作业的结束时间，在上面的两个例子中，他们的完成时间分别是40 与38，第二种最后完成时间是更小的，我们能找出更小的最后完成时间在上面二个方法中，整个序列完成时间更早是更可取的方法，我们有如下算法实现：

算法分析

首先获取任务，并且从小到大排序每次分配统计每个处理器处理需要的总时间每次取出最小的一个任务，给定处理器列表中总时间最小的那个，也就先处理完的优先分配任务依次处理任务，直到任务都处理完结

代码实现

/*** 贪心算法，处理器调度问题** @author liaojiamin* @Date:Created in 16:26 /1/12*/public class ProcessorScheduling {class Task implements Comparable<Task> {private String taskName;private Integer taskTime;public String getTaskName() {return taskName;}public void setTaskName(String taskName) {this.taskName = taskName;}public Integer getTaskTime() {return taskTime;}public void setTaskTime(Integer taskTime) {this.taskTime = taskTime;}@Overridepublic int compareTo(Task o) {return this.taskTime - o.taskTime;}}/*** 获取需要处理的业务数据*/public Task[] getTask(Integer num) {Task[] tasks = new Task[num];Random random = new Random();for (int i = 0; i < num; i++) {Task task = new Task();task.setTaskName("t" + i);task.setTaskTime(random.nextInt(10));tasks[i] = task;}return tasks;}/*** 对数据进行从小到大排序*/public Task[] sortTask(Task[] tasks) {if (tasks == null) {return null;}quickSort(tasks, 0, tasks.length - 1);return tasks;}public Task[] quickSort(Task[] tasks, Integer left, Integer right) {if (left < right) {Integer temp = swap(tasks, left, right);quickSort(tasks, left, temp - 1);quickSort(tasks, temp + 1, right);}return tasks;}/*** 挖坑法快排*/public Integer swap(Task[] tasks, Integer left, Integer right) {if (left < right) {Task position = tasks[left];while (left < right) {while (left < right && tasks[right].compareTo(position) > 0) {right--;}if (left < right) {tasks[left] = tasks[right];left++;}while (left < right && tasks[left].compareTo(position) < 0) {left++;}if (left < right) {tasks[right] = tasks[left];right--;}}tasks[left] = position;}return left;}/*** 贪心算法* 给P个处理器分配任务*/public void finishTask(Integer p) {Task[] tasks = sortTask(getTask(8));for (int i = 0; i < tasks.length; i++) {System.out.println(tasks[i].getTaskName() + ":" + tasks[i].getTaskTime());}//存储每个列表总时长int[] countP = new int[p];//存储每个cpu的任务存储位置int[] posicition = new int[p];//存储p个cpu的任务列表Task[][] taskResult = new Task[p][tasks.length - 1];for (int i = 0; i < tasks.length; i++) {Integer min = getMinId(countP);countP[min] += tasks[i].getTaskTime();taskResult[min][posicition[min]] = tasks[i];posicition[min] += 1;}for (Task[] tasks1 : taskResult) {for (Task task : tasks1) {if (task != null) {System.out.print(task.getTaskName() + ":" + task.getTaskTime());System.out.print(" ");}}System.out.println();}}/*** 获取最小值id*/public int getMinId(int[] countP) {if (countP.length <= 0) {return 0;}int min = countP[0];int minNum = 0;for (int i = 0; i < countP.length; i++) {if (min > countP[i]) {min = countP[i];minNum = i;}}return minNum;}public static void main(String[] args) {ProcessorScheduling fi = new ProcessorScheduling();fi.finishTask(3);}}

哈夫曼编码

第二个案例我们来研究一下贪婪算法的文件压缩处理（file compression）

在现实中，文件是非常大的，许多大文件是某个程序的输出，而在使用评率最大和最小的字符之间存在很大差别，例如文件大多包含的空格和newline多，q，x这些字符少。如果我们在非高效性传输场景下我们更希望文件大小越小越好，其实却是是有这样的方案囊使文件街上25%甚至更多

我们一般的策略是让代码的长度从字符到字符是变化不等的，同时保证经常出现的字符其代码要短。

如果所有字符都相同频率出现那么无法优化

我们可以用二进制代码来标识字符，并且我们用二叉树来标识二进制

标准的ASCII字符集大约也就100个“可打印”字符组成。我们设一个文件，质保函字符a，e，i，s，t，加上一些空格和newline（换行）。进一步假设有10个a，15个e，12个i，3个s，4个t，13个空格以及一个newline如下图中标识

-如上二叉树所有数据只在叶子节点上，每个字符通过根节点开始用0 指定左边分支，用1 标识右边，如a节点 000 占用3个比特位置， e节点001占用3个比特位置，i节点010，如下表格统计

如下表格中这个文件我们用二叉树标识可以只永174个比特位就能标识，因为有58个字符，而每个字符3个比特位。这种数据结构叫做trie树（trie）如果字符 c_i 在深度 d_i 出出现 f_i 次那么这种编码的值就等于 ∑ i = 1 n \sum_{i=1}^n ∑i=1n​d_i*f_i更优的解法如下图： 如上二叉树的构成并不是最优解，而且我们注意到这个二叉树是一颗满树（full tree）:所有的节点要么是树叶，要么有两个儿子。一种最优的编码总是有这种性质，否则正如我们看到的，具有一个儿子的节点可以向上移动一层。如上，我们需要解决的基本问题在于找到总价值最小的满二叉树，其中所有字符都必须在叶子节点，我们需要解决的是如何构造这颗二叉树，1952年Huffman给出来一个算法。因此这种编码系统通常称为哈夫曼编码（Hufman code）

哈夫曼算法

加上字符个数为C。哈夫曼算法（Huffman’s algorithm）可以如下描述： 算法对应由树组成的一个森林。一棵树的权重等于它的树叶出现的评率，此处是字符在文件中出现的次数。任意选取两颗权重最小的树T1， T2，并任意以T1，T2 为子树组成一颗新树将上一步骤过程进行C-1次。 在算法开始存在C课单节点树—每棵树都代表一个字符。在算法结束得到一棵树，这棵树就是最优哈夫曼编码树

具体案例分析

如下图的初始森林，每棵树的权在根节点处以数字表示。

将两颗权最低的树合并到一起，得到以下森林，我们将根节点命名成T1，命名可以任意，此处只是为了以下的表述更加方便，我们可以看到我们令s是左儿子，这次令其为左儿子还是右儿子是任意的；

我们可以观察到哈夫曼算法描述中两个任意性：

新树的总权值是那些老树权的和，当然也就很容易计算由于建立新树只需得出一个新节点，建立左右链接并将权重记录，因此建立新树叶简单

经以上步骤，我们得到六棵树，接着在选取两颗权重最小的树，这两颗数是T1 和t，然后将他们合并成另一颗新树，树根节点是T2，权重是8，如下图：

在将T2 与a 节点合并建立T3，权重是10+8 = 18，如下图：

接着继续选取最小权重两个节点，这次是i 节点和空格节点，将这两棵树合并成根节点T4,：

继续合并根节点为e 和T3 的树，得到下图：

最后将两个剩下的树合并得到最优树，根节点是T6.

如上算法可以看出哈夫曼树的一些特性：

哈夫曼树必然是满的其次两个权重最小的节点A，B必然是最深的节点如果权重最小的节点A，B不是最深的节点，那么必然存在某个C是最深的节点，如果A的权重小于C，那么我们可以通过交换他们在树上的位置而改进总权值相同深度上任意两个节点处的字符可以交换而不影响最优性，这说明总可以找到一颗最优树，他含有两个进程不出现的符号作为兄弟

以上算方分析是贪婪算法的原因在于，每一节点我们都进行一次合并，而没有进行全局的考虑我们只是每个步骤选取最小权重的树

算法分析

按照上述C个元素按顺序保存在一个优先队列，那么我们在队列上进行一次buildHeap，2C-2次deleteMin，和C-2次insert，因此运行时间为O(ClogC)如果使用链表简单实现该队列，我们给出一个O(C^2)时间复杂度算法优先队列实现方法的选择取决于C的大小，在ASCII字符集典型情况下，C是足够小的，这使得二次的运行时间是可以接受的，这样的应用中实际上所有的运行时间都讲话费在读取输入文件和写入压缩文件所需的磁盘IO上。

算法实现

//哈夫曼树节点定义/*** @author liaojiamin* @Date:Created in 11:47 /1/13*/public class HufmanNode implements Comparable<HufmanNode>{//节点权重private Integer weight;//节点名称private String nodeName;private HufmanNode left;private HufmanNode right;public Integer getWeight() {return weight;}public void setWeight(Integer weight) {this.weight = weight;}public String getNodeName() {return nodeName;}public void setNodeName(String nodeName) {this.nodeName = nodeName;}public HufmanNode getLeft() {return left;}public void setLeft(HufmanNode left) {this.left = left;}public HufmanNode getRight() {return right;}public void setRight(HufmanNode right) {this.right = right;}@Overridepublic int compareTo(HufmanNode o) {return this.weight - o.weight;}}

/*** 哈夫曼算法 模拟 文件压缩问题* @author liaojiamin* @Date:Created in 11:46 /1/13*/public class HufmanCode {/*** 初始化文件字符信息* */public static String getRandomString(int length){String str="abcdefghabc";Random random=new Random();StringBuffer sb=new StringBuffer();for(int i=0;i<length;i++){int number=random.nextInt(10);sb.append(str.charAt(number));}System.out.println(sb);return sb.toString();}/*** 哈夫曼编码问题实现* */public static HufmanNode hufmanCode(){String hufmanBase = getRandomString(20);if(hufmanBase == null || hufmanBase.length() <= 0){return null;}Map<String, Integer> nameToWeight = new HashMap<>();for (int i = 0; i < hufmanBase.length(); i++) {String key = String.valueOf(hufmanBase.charAt(i));Integer value = nameToWeight.get(key);nameToWeight.put(key, value == null ? 1 : value + 1);}LinkedList<HufmanNode> linkedList = buildHufmanNode(nameToWeight);quickSort(linkedList, 0, linkedList.size() -1);if(linkedList.size() == 1){return linkedList.get(0);}while (!linkedList.isEmpty()){if(linkedList.size() == 1){return linkedList.removeFirst();}HufmanNode hufmanNode = buildNewNode(linkedList.removeFirst(), linkedList.removeFirst());insertLinkedList(linkedList, hufmanNode);}return linkedList.removeFirst();}/*** 按weight顺序插入哈夫曼节点* */public static void insertLinkedList(LinkedList<HufmanNode> linkedList, HufmanNode hufmanNode){if (linkedList.size() <= 0){linkedList.add(hufmanNode);return;}Integer temp = linkedList.size() - 1;for (int i = 0; i < linkedList.size(); i++) {if(linkedList.get(i).getWeight() > hufmanNode.getWeight()){temp = i;}}linkedList.add(temp, hufmanNode);}/*** 构造节点信息* */public static HufmanNode buildNewNode(HufmanNode left, HufmanNode right){HufmanNode hufmanNode = new HufmanNode();hufmanNode.setLeft(left);hufmanNode.setRight(right);hufmanNode.setNodeName("node" + System.currentTimeMillis());hufmanNode.setWeight(left.getWeight() + right.getWeight());return hufmanNode;}/*** 快排权重从小到大* */public static void quickSort(LinkedList<HufmanNode> linkedList, Integer left, Integer right){if(left < right){Integer temp = swap(linkedList, left, right);quickSort(linkedList, left, temp -1);quickSort(linkedList, temp + 1, right);}}/*** 挖坑法实现快排* */public static Integer swap(LinkedList<HufmanNode> linkedList, Integer left, Integer right){if(left < right){HufmanNode position = linkedList.get(left);while (left < right){while (left < right && linkedList.get(right).compareTo(position) > 0){right --;}if(left < right){linkedList.set(left, linkedList.get(right));left ++;}while (left < right && linkedList.get(left).compareTo(position) < 0){left ++;}if(left < right){linkedList.set(right, linkedList.get(left));right--;}}linkedList.set(left, position);}return left;}/*** 构造树节点* */public static LinkedList<HufmanNode> buildHufmanNode(Map<String, Integer> nameToWeight){LinkedList<HufmanNode> linkedList = new LinkedList<>();for (String nodeName : nameToWeight.keySet()) {HufmanNode hufmanNode = new HufmanNode();hufmanNode.setNodeName(nodeName);hufmanNode.setWeight(nameToWeight.get(nodeName));linkedList.addFirst(hufmanNode);}return linkedList;}public static void main(String[] args) {HufmanNode hufmanNode = hufmanCode();}}

上一篇：数据结构与算法–图论-深度优先搜索及其应用

下一篇：数据结构与算法–贪婪算法2