高考申論題
108年
[工業行政] 計算機概論
第 題
📖 題組：
二、下圖是 Huffman encoding 的一個例子： (圖略：給出字元頻率 A:17, B:12, C:12, D:27, E:32，並圖示步驟 a 到 e 建構霍夫曼樹，最後產生編碼表)
二、下圖是 Huffman encoding 的一個例子： (圖略：給出字元頻率 A:17, B:12, C:12, D:27, E:32，並圖示步驟 a 到 e 建構霍夫曼樹，最後產生編碼表)
Huffman encoding 是一種 greedy algorithm，請問如何判別它是 greedy algorithm？（5 分）
📝 此題為申論題
思路引導 VIP
看到此題，應先回想『貪婪演算法（Greedy Algorithm）』的核心特徵：每步採取當前局部最佳選擇且不回溯。接著，將 Huffman Tree 建構過程中『每次必定挑選兩個頻率最小的節點合併』的具體操作與該定義結合，即可精準作答。
🤖
AI 詳解
AI 專屬家教
【破題】 Huffman encoding 之所以為貪婪演算法（Greedy Algorithm），是因為它在建構霍夫曼樹（Huffman Tree）時，每一步驟均採取「當前狀態下的局部最佳選擇」，且決策不可撤回。 【論述】
▼ 還有更多解析內容