贪心算法：活动选择问题与霍夫曼编码

引言

贪心算法是一种在每一步选择中都采取当前最优解的方法。贪心算法通常用于解决一些优化问题，它的主要优势在于其简单性和高效性。本文将详细介绍两个经典的贪心算法问题：活动选择问题和霍夫曼编码。

活动选择问题

定义

活动选择问题是一个经典的贪心算法问题，目的是在给定的一组活动中选择尽可能多的活动，使得这些活动互不重叠。

问题描述

假设有一组活动 (A = {a_1, a_2, \ldots, a_n})，每个活动 (a_i) 都有一个开始时间 (s_i) 和一个结束时间 (f_i)。活动选择问题要求选择尽可能多的活动，使得这些活动互不重叠，即对于任意两个选择的活动 (a_i) 和 (a_j)，有 (f_i \leq s_j) 或 (f_j \leq s_i)。

贪心选择策略

贪心选择策略是每次选择结束时间最早且不与已选择活动重叠的活动。

示例

假设有以下活动：

活动     开始时间  结束时间
a1       1        4
a2       3        5
a3       0        6
a4       5        7
a5       3        9
a6       5        9
a7       6        10
a8       8        11
a9       8        12
a10      2        14
a11      12       16

贪心算法实现

下面是用Java实现活动选择问题的代码示例：

import java.util.*;public class ActivitySelection {// 活动类，包含开始时间和结束时间static class Activity {int start;int finish;Activity(int start, int finish) {this.start = start;this.finish = finish;}}// 活动选择算法public static void selectActivities(List<Activity> activities) {// 按结束时间升序排序activities.sort(Comparator.comparingInt(a -> a.finish));System.out.println("选中的活动:");// 第一个活动总是被选中Activity lastSelected = activities.get(0);System.out.println("活动 (" + lastSelected.start + ", " + lastSelected.finish + ")");// 选择其他活动for (int i = 1; i < activities.size(); i++) {Activity currentActivity = activities.get(i);if (currentActivity.start >= lastSelected.finish) {System.out.println("活动 (" + currentActivity.start + ", " + currentActivity.finish + ")");lastSelected = currentActivity;}}}public static void main(String[] args) {List<Activity> activities = Arrays.asList(new Activity(1, 4),new Activity(3, 5),new Activity(0, 6),new Activity(5, 7),new Activity(3, 9),new Activity(5, 9),new Activity(6, 10),new Activity(8, 11),new Activity(8, 12),new Activity(2, 14),new Activity(12, 16));selectActivities(activities);}
}

活动选择问题的详细图解

以下是活动选择问题的执行过程图解：

霍夫曼编码

定义

霍夫曼编码（Huffman Coding）是一种用于数据压缩的贪心算法。通过构建最优前缀码，使得出现频率较高的字符使用较短的编码，而出现频率较低的字符使用较长的编码，从而达到压缩数据的目的。

问题描述

给定一个字符集及其对应的权重（出现频率），通过霍夫曼编码生成最优前缀码，使得编码后的总长度最短。

贪心选择策略

贪心选择策略是每次选择权重最小的两个节点，合并它们，并将新节点的权重设为两个节点权重之和。

示例

假设有以下字符及其对应的权重：

霍夫曼编码算法实现

下面是用Java实现霍夫曼编码的代码示例：

import java.util.PriorityQueue;public class HuffmanCoding {// 节点类，包含字符、权重、左子节点和右子节点static class Node implements Comparable<Node> {char character;int frequency;Node left;Node right;Node(char character, int frequency) {this.character = character;this.frequency = frequency;}Node(int frequency, Node left, Node right) {this.frequency = frequency;this.left = left;this.right = right;}@Overridepublic int compareTo(Node o) {return this.frequency - o.frequency;}}// 构建霍夫曼树public static Node buildHuffmanTree(char[] characters, int[] frequencies) {PriorityQueue<Node> priorityQueue = new PriorityQueue<>();for (int i = 0; i < characters.length; i++) {priorityQueue.add(new Node(characters[i], frequencies[i]));}while (priorityQueue.size() > 1) {Node left = priorityQueue.poll();Node right = priorityQueue.poll();Node newNode = new Node(left.frequency + right.frequency, left, right);priorityQueue.add(newNode);}return priorityQueue.poll();}// 打印霍夫曼编码public static void printHuffmanCodes(Node root, String code) {if (root == null) {return;}if (root.character != '\0') {System.out.println(root.character + ": " + code);}printHuffmanCodes(root.left, code + "0");printHuffmanCodes(root.right, code + "1");}public static void main(String[] args) {char[] characters = {'A', 'B', 'C', 'D', 'E', 'F'};int[] frequencies = {5, 9, 12, 13, 16, 45};Node root = buildHuffmanTree(characters, frequencies);printHuffmanCodes(root, "");}
}