❶ 常見演算法有哪些
模擬
擬陣
暴力
貪心
二分法
整體二
三分法
一般動規與遞推
斯坦納樹
動態樹分治
2-SAT
並查集
差分約束
最短路
最小割
費用流
最大流
有上下界網路流
虛樹
矩陣樹定理
最小生成樹
點分治
樹鏈剖分
prufer編碼
哈夫曼樹
拉格朗日乘數法
BSGS
博弈論
矩陣乘法
高斯消元
容斥原理
抽屜原理
模線性方程組
莫比烏斯反演
快速傅里葉變換
擴展歐幾里得演算法(
裴蜀定理
dfs序
深度搜索
迭代深搜
廣度搜索
雙向廣搜
啟發式搜索
dancing link
迴文自動機
KMP
字典樹
後綴數組
AC自動機
後綴自動機
manacher
凸包
掃描線
三角剖分
旋轉卡殼
半平面交
cdq分治
莫隊演算法
爬山演算法
分數規劃
模擬退火
朱劉演算法
隨機增量法
倍增演算法
❷ MCTS方法在強化學習和組合優化中的調研
MCTS是一種古老的解決對抗搜索的方法。與Min-max 搜索不同，其可以做單智能體的任務。
1928年，John von Neumann的minimax定理提出了關於對手樹搜索的方法，這成為了計算機科學和人工智慧決策制定的基石。
其思路為，如果樹的層數較淺，我們可以窮舉計算每個節點的輸贏概率，可以使用minmax演算法，從葉子節點開始看，本方回合選擇max，對方回合選擇min，從而在博弈論中達到納什均衡點。
流程如上圖所示。當然，我們可以使用alpha-beta對這個搜索樹剪枝。
但如果每一層的搜索空間都很大，這種方法就極其低效了，以圍棋為例，圍棋每一步的所有可能選擇都作為樹的節點，第零層只有1個根節點，第1層就有361種下子可能和節點，第2層有360種下子可能和節點，這是一顆非常大的樹。如果我們只有有限次評價次數，minimax方法就是不可行的（往往只能跑2-3層，太淺了）
1940年代，Monte Carlo方法形成，這個方法由於在摩納哥的蒙特卡洛賭場被發明而得名。其思想類似於18世紀的譜豐投針。
這種方法可以用到樹搜索上。以圍棋為例，圍棋的每一步所有可能選擇都作為樹的節點，第零層只有1個根節點，第1層就有361種下子可能和節點，第2層有360種下子可能和節點，但是如果我們不斷地嘗試隨機選擇往下模擬5步，拿有限的嘗試次數給當前層的每個動作算個期望，我們就可以選擇相對最優的動作。
值得注意的是，這種方法可以應用到單人游戲上，所以在model-free強化學習中，也有這樣的蒙特卡洛方法。
蒙特卡羅強化學習(Monte Carlo reinforcement learning)：指在不清楚 MDP 狀態轉移概率的情況下，直接從經歷完整的狀態序列 (episode) 來估計狀態的真實價值，並認為某狀態的價值等於在多個狀態序列中以該狀態算得到的所有return 的平均，記為期望值。
2006年，Kocsis和Szepesvári將此觀點形式化進UCT演算法。UCT=MCTS+UCB。UCB是在多臂老虎機問題中的不確定性估計方法。這種方法的思路是蒙特卡洛方法的動作選擇之間具有不確定性，基於選擇次數可以估計一個確定性值，以輔助價值評估。
UCT演算法為，在原有的基礎上，拓展作為確定性上界。t是選擇這個動作的次數，T是當前狀態的選擇動作總次數。最後根據這個公式來選擇給定狀態的動作。這個確定性上界的推導是Chernoff-Hoeffding Bound定理得出的。
其實確定性上界有很多，由於推導過程認為選擇次數會足夠多。這個上界滿足的是。後續很多工作只是把這一項當作了啟發式，給第二項加了個系數。
這樣，MCTS的過程就進化為了以下四個步驟。
再重新回到根節點，重復上述過程。
我們可以發現，這里的Simulation過程如果搜不到結束狀態，對當前狀態估值就是一個很重要的學問。我們將利用過往經驗訓練的神經網路對其估價就是一個可信的優秀方法。
Alphago Lee：接下來我會講一下這個基本的方法之後於深度學習的結合，分別是在圍棋和組合優化。MCTS的組合優化應用大概也是Alphago的功勞。
這是第一篇Alphago文章。
總的來說，這篇工作一共使用了3種技術：監督學習，強化學習和MCTS（UCT）。
下圖展示了兩個訓練階段。
這里的監督學習輸入是狀態的表示，我不會下圍棋，所以不清楚這里的capture是什麼。總體來說就是一個48 * 360 * 360的張量。
訓練了兩個類似的網路，只是大小不同。loss是CE loss。這些數據都是來自於一個數據集KGS，大小為100,000。
相比於上來就強化學習，這樣相當於訓練baseline，會更加穩定。
這個學完的效果是不好的。文章拿這個網路不加蒙特卡洛搜索對比了其他方法，只能贏11%-12%的對局。
強化學習的目的有兩個。一是繼續學習：數據集過小了，和minst差不多大（60,000），勝率太低了。二是獲得估值：監督學習就好比圖片分類，在輸入棋盤後只會學習輸出最優答案，而不是每個位置的勝率。
繼續學習
獲得估值
在提升策略網路性能的同時，RL另外訓練了一個價值網路來估計棋盤的勝率 loss是MSE。輸出由動作概率變為一個標量值，用來表示狀態s的勝率。注意到勝率其實就是上文中的reward對動作序列的期望。
這之後的MCTS是一個獨立的步驟，文章先評價了每個方法的效果。
正如上文提到，MCTS分為四個步驟，最終會得到一個訓練好的MCTS。這個過程網路都是fixed的。
Alphago的MCTS流程如下。
上文提到這個最大確定上界u可以很靈活，對照前文表示方法，這里的[公式]。
值得強調的是，最終Alphago在運行時選擇動作的依據不是Q，而是u。
這是最終的結果。看得出超過了所有人類高手和已有方法。
這頁很有意思。
可以看出設備很足……
Alphazero
一年後，原班人馬提出了升級版，motivation是原有的監督學習數據會導致容易陷入局部最優而且不優雅。
兩者最大的不同是，本文僅僅使用self-play強化學習，從隨機play開始，不用任何監督學習。
作者的意思是，rollout只是網路不行的一個替代解決方案。這里的U有一個微調，改回了原始版本[公式]。
注意，這里不是一個神經網路，而是一組，Alphazero維護的神經網路為[公式]，兩者分別是根據獎勵和選擇次數（u）策略梯度更新和根據獎勵MSE更新，最終加權估計這個Q。也就是說，在Alphazero中，不需要一套額外的計數器去記錄Q和u了。在訓練時，這兩個函數被記錄去訓練兩個網路，在訓練完成後，整個決策就會完全根據網路輸出，[公式]代替argmax Q+U選擇動作。
這篇文章的潛能更高當然train得更慢。
組合優化：
後續有很多文章致力於用MCTS做TSP，基本思想也是建模成四個流程模仿Alphago。
眾所周知，強化學習組合優化一般是兩種思路，一個是一位一位得輸出解，這個過程是端到端的，稱為Learn to construct。
Learn to Construct methods
對於end-to-end的L2C思路，2016年就有一位學者發表了論文Application of monte-carlo tree search to traveling salesman problem，但這篇文章怎麼也搜不到了。
後來2020年有這樣一篇文章。
這篇文章里，蒙特卡洛樹搜索被建模為每層選解。以TSP20為例，第一層就是20個選擇，第二層是19個...
依然是四個階段。
選擇動作如下式子。
在提前訓練這個網路的時候也是reward擬合剩下的半部分，用的是值函數逼近 訓練方法（L2 loss + 正則化，但是沒有搞target network）。
他這里介紹的reward有一處錯誤，[公式]應該是[公式]，下邊是訓練方法。
這里的隨機選擇我不理解，我的理解是這樣學習網路的價值就不大了。文章結果比不過不加MCTS。這個directly use也有點不規范……
這篇文章還有升級版，採用了類似的獎勵設置，投稿ICLR2021獲得了455的分數，叫做：
這篇文章就是按照Alphazero的思路搞出來兩個網路，擬合v和[公式]，然後險勝S2V-DQN的原始方法。
這兩篇文章和所有在這個角度的文章最大的貢獻應當是證明了，基於構造（L2C）的組合優化蒙特卡洛方法不可行。我的理解是，這個方法是根據對弈產生的，其獎勵的和自然可以代表勝率。兩者都把這個最關鍵的獎勵設置為人為構造的新東西。構造排名得分是個不錯的想法，但是這樣轉化根據結果看不是一個好的轉化方法，導致這套理論就無法發揮作用。
Openreview的意見認為，這種方法發展到大規模會比較好。傳統的端到端學習基本只能擬合值函數或者policy之一，Alphazero框架需要同時擬合兩者，這需要一定的創新。
Learn to Improve methods
這個方向是比較成功的，有一篇AAAI21的文章。這個方向上的第一篇文章是：
但是被ICLR拒了。這個方法完全是AAAI文章的一部分（也是同一個課題組搞得）。本文使用的提升運算元為k-opt。這篇文章不是learning-based的，而是一種啟發式，每次重新跑一遍MCTS，所以被拒了。
這個MCTS的結構就比較特別了，後邊會提到。同樣是四個階段。
k-opt的動作選擇可以用一個序列表示[公式]代表。對應刪除邊[公式]，連接[公式]在選擇時我們認為一個TSP序列是有向環路，所以我們只需要選擇k個不同的a即可。在每次選擇一個b後，對於一個n個結點的圖下一個點是這樣決定的，還是用T代表當前層總訪問次數[公式]這里就看出來了，這其實是一個運算元迭代樹，這里的MCTS也不是為了快速求解而是輔助啟發式的。
result：
最後這篇文章是AAAI21，我曾經做過一個論文復盤 論文復盤：Generalize a Small Pre-trained Model to Arbitrarily Large TSP Instances-AAAI2021大規模tsp監督學習方法。他就是在這個操作前監督學習train了小網路並且拼接得到熱圖來生成初始解。
但是讀了前一篇文章我對這個結果就有點不解了...
總結一下：MCTS是一個解決游戲問題很好的方法，取自MAB，但是對於優化問題有一定的限制。MCTS的核心是rollout和simulation時用到的UCB評價，前者來自於賭場經驗，後者來自於MAB的理論。這兩個單獨的構建分別在RL方法里被發展成了兩個分支，這說明了這兩個點對於強化學習的重要性。例如DDPG也是一個價值網路和一個策略網路，這兩個部件可以對應到之前講到的基線估計方法TD3、SAC和curiosity好奇心。