局部最佳與全域最佳（local vs global optimum）

想像你在濃霧中爬山，總是往上踏步以抵達最高點。你可能停在一座小丘上，任何單步都無法更高，而一座遠高的山卻隔著看不見的山谷矗立著。那座小丘是局部最佳——在它的近鄰中最高。那座高山是全域最佳——處處最高。它們未必是同一個地方。

全域最佳是整個搜尋空間中真正最好的解——最低成本、最多工作、最高價值，依目標而定。局部最佳是無法藉由微小的局部移動改善的解，即使存在一個截然不同且更好的解。貪婪演算法做出一連串局部最佳的選擇，因此就構造而言它追求的是局部最佳。這整個領域的核心主題正是：局部最佳何時迫使全域最佳？答案恰恰是當問題具有貪婪選擇性質與最佳子結構時（或更抽象地，具有擬陣結構）。成立時，局部最佳的路徑可證地抵達全域最佳；不成立時，貪婪可能把你困在小丘上。

這個區分也解釋了為何針對難解問題的區域搜尋與爬山啟發式不提供最佳性保證——它們可能停在離全域最佳很遠的局部最佳，這正是隨機重啟或模擬退火等技巧存在以逃離此陷阱的原因。誠實的結論：「我用微小改變無法改善它」只是關於局部最佳的陳述。要斷言它全域最佳，需要真正的證明，而非「卡住了」帶來的安心感。