:::warning 這篇文涉及到的觀念比較複雜，建議沒有經驗的讀者可以使用維基百科輔助理解這篇文的內容。 :::

:::warning 筆者對於 P 與 NP 問題的詳細定義可能存在些許誤解或理解不夠全面，因此如果文中出現錯誤麻煩告知，會儘快修正。 :::

起因

上了大學之後因為對自己的專業技能抱有期待能夠發揮在一些地方， 因此我很主動在詢問學校的資源， 教授剛好藉機向我介紹實驗室這個地方， 於是在我好奇心的驅使下在大一還是個新生時就進入了學校實驗室， 後來從教授口中得知實驗室有在做最佳化演算法的實驗， 目的是改善現有的演算法， 並且從演算法的角度出發去找到更高效率的演算法， 實驗室已經有實現出 Python 版本， 而我負責改寫為 C++ 並且提升效能。 也算是幫忙寫 code 順便賺點零用錢。

P=NP 問題與時間複雜度

關於最佳化演算法的出現首先要提起 P=NP 問題， 這是著名的千禧年難題之一， 在介紹這個問題前， 我先簡單解釋什麼是「時間複雜度」， 時間複雜度用於表示一個演算法需要花多少時間解決問題， 通常人們習慣用大O表示法來表達時間複雜度， 並以 n 作為問題大小， 例如遍歷一個陣列的時間複雜度為 O(n)， 表示使用問題大小的時間(操作次數)可以解決此問題。

P 與 NP

P 代表的是多項式時間， 也就是在次方項為常數的時間複雜度， 因為次方向如果為 n 的話會導致花費的時間隨著問題大小成指數成長， 也就是 NP， 因此問題只要變大很快就會變得無法計算， 因此需要隨著問題大小讓時間線性成長的演算法來解決 NP 問題。

啟發式與最佳化演算法

啟發式演算法是藉由學習或模仿自然界已有的可行方案例如蟻群、狼群尋找食物的方式之類的行為來設計一套演算法， 也有藉由退火啟發的演算法， 都是想要藉由演化或其他自然界的力量來處理問題。

最佳化演算法是專為一系列的 NP 問題而誕生。

區域最佳解與全域最佳解

一個大的 NP 問題中在我們使用最佳化演算法時會遇到一個重要的問題， 要如何調配區域搜尋和全域搜尋的比例， 若區域搜尋過多會停留在區域最佳解， 過少則會導致解往更好方向的收斂速度過慢， 從而浪費時間。

許多最佳化演算法會遇到止步於區域最佳解的問題， 因為沒有遍歷所有可能的方法就沒有辦法保證找到的是最佳解， 因此演算法可能誤以為自己已經找到了全域最佳解或是持續尋找區域更優解， 因此掌握何時該做區域搜尋何時該做全域搜尋是最佳化演算法的重要課題。

使用的演算法

量子啟發的最佳化演算法， 以量子角度思考演算法的設計， 用於解決一系列 NP 問題。

論文中主要的演算法， 改進了原先 QTS 旋轉量子位元角度的速度， 提升最佳解收斂速度和品質。

實作過程

因為實驗室中使用的 Python 執行速度過慢， 因此我重新寫了一份 C++ 的版本，開發過程中我才逐漸了解這兩個算法的核心思想， 藉由模擬量子的特性來給予每個物品拿或不拿的機率， 並且從上一代解的好壞調整下一代要拿取該物品的機率。

最後也加入了一些功能，例如多執行緒並行用來節省執行時間， 加上 C++ 原先執行就比 Python 快上許多， 以實驗室的電腦效能粗估最後剩下至少 150 倍的時間。

我的體悟

我覺得了解這個千禧年難題的過程中帶給我很多的啟發， 例如全域搜尋和區域搜尋的概念， 就像是經驗法則與創意的對立， 又或是能證明 P=NP 或 P!=NP 就能獲得一百萬美金等等。 這些事情都讓我對這個世界的理解變得比以前更廣， 在看待事情時也多了一些不同的角度， 也開始思考為何現有的解決方案是可行的， 並且對比自己曾經的想法， 不停思考的過程讓我成長很多。