貪婪算法
- 貪婪算法分階段地工作。在每個階段，可以認為所做決定是最好的，而不考慮将來的後果。通常這意味着選擇的是某個局部最優。這種“目前能獲得的最優就拿”的政策是這類算法的名字來源。
- 當算法終止時候，我們希望的到累積的局部最優解就等于全局最優，如果是這樣的，那麼算法就是正确的；否則算法得到的是一個次優解（suboptimal solution）。如果不需要絕對的最佳答案，那麼有時候使用簡單的貪婪算法生成近似的答案能得到一個時間複雜度更優的解。
案例分析
- 舉幾個現實的貪婪算法的例子，明顯的是貨币找零問題。
- 使用RMB找零錢，我們重複的配發最大額貨币。于是為了找十七塊六毛，
- 我們拿出一張10元，一張5元，2張1元（2元貨币現在少見了），加一個5毛硬币，兩個一毛硬币。這麼做，我們能保證使用最少的鈔票和硬币，這個算法不是對每種貨币通用，但是RMB是有效的
- 交通問題
- 以下會詳細講解兩個案例，來說明貪婪算法的應用，第一個模拟排程問題，第二個模拟檔案壓縮算法，他是計算機科學最早的成果之一。
一個簡單的排程問題
- 假設我們計算機系統由任務j1，j2，j3 …jN，已知對應的運作時間分别是t1，t2，t3…tN，而處理器隻有一個，為了把作業平均完成的時間最小化，排程這些作業的最好方式是什麼？？？
- 假設我們讨論的都是非預占排程（nonpreemptive scheduling）：一旦開始一個任務就必須吧任務執行完。
- 我們用一下案例簡化，四個作業，已經運作時間，如下表格，一個可能的排程在圖一中表示：
| 任務 | 時間 |
|---|---|
| j1 | 15 |
| j2 | 8 |
| j3 | 3 |
| j4 | 10 |
- 上圖中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=1nk*tk
- 如上表達是可以看成，排程總時間和 ∑ k = 1 n \sum_{k=1}^n ∑k=1nk*tk 成反比，k表示第幾個位置執行，tk表示指定第k次執行的時間，當這個數值越大，那麼總的時間就越少，那麼我們将權重越大的往後放就能得到最小值。
多處理器情況
- 我們可以把問題擴充到多個處理器的情況，我們還是這些作業j1，j2，j3，j4，…jn。，時間t1，t2，t3…tN，另外有處理器P個。假設作業是有序的，最短的運作時間最先處理，加入P = 3.如下表格
| 任務 | 時間 |
|---|---|
| j1 | 3 |
| j2 | 5 |
| j3 | 6 |
| j4 | 10 |
| j5 | 11 |
| j6 | 14 |
| j7 | 15 |
| j8 | 18 |
| j9 | 20 |
- 如上圖他平均完成時間優化到了最小，作業1,4，7在處理器1 上運作，處理器二在2,5，8 上，處理器3 處理其餘作業，總完成時間是165，平均是165/9 = 18.33
- 解決多處理器情形的算法是按順序開始作業，處理器之間輪換配置設定罪業，不難證明沒有那個其他順序能做到更好。但是還有其他順序的最優解，如下圖：
資料結構與算法--貪婪算法 - 如上，還是最小的先執行，隻是我們将是哪個處理器處理的任務換了換而已
将最後完成時間最小化
- 還需要考慮一個非常類似情況，假設我們隻關注最後的作業的結束時間，在上面的兩個例子中，他們的完成時間分别是40 與38，第二種最後完成時間是更小的，我們能找出更小的最後完成時間
- 在上面二個方法中，整個序列完成時間更早是更可取的方法，我們有如下算法實作：
算法分析
- 首先擷取任務，并且從小到大排序
- 每次配置設定統計每個處理器處理需要的總時間
- 每次取出最小的一個任務，給定處理器清單中總時間最小的那個，也就先處理完的優先配置設定任務
- 依次處理任務，直到任務都處理完結
代碼實作
/**
* 貪心算法，處理器排程問題
*
* @author liaojiamin
* @Date:Created in 16:26 2021/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;
}
@Override
public 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，如下表格統計
資料結構與算法--貪婪算法
| 字元 | 編碼 | 頻率 | 比特數 |
|---|---|---|---|
| a | 000 | 10 | 30 |
| e | 001 | 15 | 45 |
| i | 010 | 12 | 36 |
| s | 011 | 3 | 9 |
| t | 100 | 4 | 12 |
| 空格 | 101 | 13 | 39 |
| nl | 110 | 1 | 3 |
- 如下表格中這個檔案我們用二叉樹辨別可以隻永174個比特位就能辨別，因為有58個字元，而每個字元3個比特位。
- 這種資料結構叫做trie樹（trie）如果字元 c_i 在深度 d_i 出出現 f_i 次那麼這種編碼的值就等于 ∑ i = 1 n \sum_{i=1}^n ∑i=1nd_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 2021/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;
}
@Override
public int compareTo(HufmanNode o) {
return this.weight - o.weight;
}
}
/**
* 哈夫曼算法 模拟 檔案壓縮問題
* @author liaojiamin
* @Date:Created in 11:46 2021/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