啟發式最佳化演算法帶給我的成長
:::warning 這篇文涉及到的觀念比較複雜，建議沒有經驗的讀者可以使用維基百科輔助理解這篇文的內容。 ::: :::warning 筆者對於 P 與 NP 問題的詳細定義可能存在些許誤解或理解不夠全面，因此如果文中出現錯誤麻煩告知，會儘快修正。 ::: 起因 上了大學之後因為對自己的專業技能抱有期待能夠發揮在一些地方， 因此我很主動在詢問學校的資源， 教授剛好藉機向我介紹實驗室這個地方， 於是在我好奇心的驅使下在大一還是個新生時就進入了學校實驗室， 後來從教授口中得知實驗室有在做最佳化演算法的實驗， 目的是改善現有的演算法， 並且從演算法的角度出發去找到更高效率的演算法， 實驗室已經有實現出 Python 版本， 而我負責改寫為 C++ 並且提升效能。 也算是幫忙寫 code 順便賺點零用錢。 P=NP 問題與時間複雜度 關於最佳化演算法的出現首先要提起 P=NP 問題， 這是著名的千禧年難題之一， 在介紹這個問題前， 我先簡單解釋什麼是「時間複雜度」， 時間複雜度用於表示一個演算法需要花多少時間解決問題， 通常人們習慣用大O表示法來表達時間複雜度， 並以 n 作為問題大小， 例如遍歷一個陣列的時間複雜度為 O(n)， 表示使用問題大小的時間(操作次數)可以解決此問題。 P 與 NP P 代表的是多項式時間， 也就是在次方項為常數的時間複雜度， 因為次方向如果為 n 的話會導致花費的時間隨著問題大小成指數成長， 也就是 NP， 因此問題只要變大很快就會變得無法計算， 因此需要隨著問題大小讓時間線性成長的演算法來解決 NP 問題。 啟發式與最佳化演算法 啟發式演算法是藉由學習或模仿自然界已有的可行方案例如蟻群、狼群尋找食物的方式之類的行為來設計一套演算法， 也有藉由退火啟發的演算法， 都是想要藉由演化或其他自然界的力量來處理問題。 最佳化演算法是專為一系列的 NP 問題而誕生。 區域最佳解與全域最佳解 一個大的 NP 問題中在我們使用最佳化演算法時會遇到一個重要的問題， 要如何調配區域搜尋和全域搜尋的比例， 若區域搜尋過多會停留在區域最佳解， 過少則會導致解往更好方向的收斂速度過慢， 從而浪費時間。 ...