貪心算法概述

貪心算法（又稱貪婪算法），基本原理是，遵循某種既定原則，不斷地選取當前條件下最優的選擇來構造每一個子步驟，直到獲得問題最終的求解。即在求解時，總是作出當前看來最好的選擇。也就是說，不從整體最優上加以考慮，僅是求解局部最優解，以期望能找到全局最優解。

貪心算法與動態規劃類似，都是將原來的較大規模的問題拆分為規模較小的問題，依據大問題與小問題之間的遞推關系，通過解決較小規模的問題，最終獲得原始問題的求解。但是動態規劃要通盤考慮各個階段各子問題的求解情況，從全局的角度進行衡量，最終找到解決原始問題的最佳解決方案。貪心算法與動態規劃的不同之處在于，貪心算法利用問題的貪心性質，簡化了分解原始問題的過程，每次只關注在當前狀態下可以獲得的局部最優解，通過拼接各階段的局部最優解獲得最終問題的解。因為貪心選擇可以依賴于以往所做的選擇，但絕不依賴于未來所做的選擇，也不依賴于子問題的解。故而貪心算法往往求解時與動態規劃相反，采用自頂向下的方式，迭代作出貪心選擇，不斷化簡問題規模。

利用貪心算法解題，需要解決兩個問題：

• 是否適合用貪心法求解，即所求解問題是否具有貪心選擇性質。所謂貪心選擇性質是指應用同一規則，將原問題變為一個相似的但規模更小的子問題，而后的每一步都是當前看似最佳的選擇。這種選擇依賴于已做出的選擇，但不依賴于未做出的選擇。從全局來看，運用貪心策略解決的問題在程序的運行過程中無回溯過程。貪心選擇性質的證明一般采用數學歸納法，證明每一步做出的貪心選擇確實能導致問題的整體（全局）最優解，也有基于算法的輸出，或使用一種“擬陣”結構等形式的證明。
• 是否具有局部最優解，從而通過選擇一個貪心標準，可以得到問題的最優解。貪心算法和動態規劃都依賴于問題具有最優子結構性質，但并不是具有最優子結構性質的問題就可以用貪心算法求解。貪心算法不是總能對動態規劃求解最優化問題進行優化的。

貪心算法解題思路

1. 建立對問題精確描述的數學模型，包括定義最優解的模型；
2. 將問題分成一系列的子問題，同時定義子問題的最優解結構；
3. 應用貪心算法原則可以確定每個子問題的局部最優解，并根據最優解模型，用子問題的局部最優解堆疊出全局最優解。

代碼示例

• 硬幣找零問題是給定找零金額，計算如何搭配使得使用的硬幣數量最少

• 哈夫曼編碼

現在有一個包含 5 個字符的字符表 {A,B,C,D,E}，各字符出現的頻率A:0.35, B:0.1, C:0.2, D:0.2, E:0.15；

構造一種有效率的編碼類型，使用該編碼表達以上字符表內容時可以產生平均長度最短的位串。在對由 n 個字符組成的文本進行編碼過程中，有兩種編碼方式，即定長編碼和變長編碼。對于定長編碼而言，會為每個字符賦予一個長度固定為 m(m≥log2n) 的位串，我們常用的標準 ASCII 碼就是采用定長編碼策略對字符集進行編碼的。長度各異的編碼，其中出現頻率較高的字符，采用長度較短的編碼表示，出現頻率較低的字符，采用長度較長的編碼表示。

為了對某字母表構造一套二進制的前綴碼，可以借助二叉樹。將樹中所有的左向邊都標記為0，所有的右向邊都標記為 1。通過記錄從根節點到字符所在的葉子節點的簡單路徑上的所有 0-1 標記來獲得表示該字符的編碼。

# 參考文檔: https://www.92python.com/view/354.html# 樹節點定義class Node:    def __init__(self, pro):        self.left = None        self.right = None        self.parent = None        self.pro = pro    def is_left(self):  # 判斷左子樹        return self.parent.left == self# create nodes創建葉子節點def create_nodes(pros):    return [Node(pro) for pro in pros]# create Huffman-Tree創建Huffman樹def create_huffman_tree(nodes):    '''從下向上創建二叉樹'''    queue = nodes[:]    while len(queue) > 1:        queue.sort(key=lambda item: item.pro)        node_left = queue.pop(0)        node_right = queue.pop(0)        node_parent = Node(node_left.pro + node_right.pro)  # 二節點值合并        node_parent.left = node_left  # 父親認兒子，        node_parent.right = node_right        node_left.parent = node_parent  # 兒子認父親        node_right.parent = node_parent        queue.append(node_parent)    queue[0].parent = None    return queue[0]# Huffman編碼def huffman_encoding(nodes, root):    '''根據當前節點為左右子樹進行判斷賦值'''    codes = [''] * len(nodes)    for i in range(len(nodes)):        node_temp = nodes[i]        while node_temp != root:            if node_temp.is_left():                codes[i] = '0' + codes[i]            else:                codes[i] = '1' + codes[i]            node_temp = node_temp.parent  # 當前節點替換為父子節點    return codesif __name__ == '__main__':    letters_pros = [('B', 10), ('E', 15), ('C', 20), ('D', 20), ('A', 35)]    nodes = create_nodes([item[1] for item in letters_pros])  # 生成樹節點    root = create_huffman_tree(nodes)    codes = huffman_encoding(nodes, root)    for item in zip(letters_pros, codes):        print('Label:%s pro:%-2d Huffman Code:%s' % (item[0][0], item[0][1], item[1]))

哈夫曼樹：

總結

• 貪心算法需要具備貪心選擇性質和最優子結構性質
• 動態規劃和貪心算法的計算順序是相反的，動態規劃由下而上，貪心從頂而下；