apio2018趣味算法應(yīng)用講課ii

1、清華大學(xué) 秦岳本講旨在講解OI算法在奇妙問題中的有趣簡單的應(yīng)用來幫助大家放松心情，愉悅身心，準(zhǔn)備考試1、泊松圖像編輯&高斯消元，線性代數(shù)2、游戲AI設(shè)計 &不可描述泊松圖像融合改變天氣無中生有改變天氣改變表情去除高光融合紋理Fx(x,y)=Ax,y-Ax-1,yFy(x,y)=Ax,y-Ax,y-1(Fx,Fy)構(gòu)成梯度向量Div(x,y)=Fx(x+1,y)-Fx(x,y) + Fy(x,y+1)-Fy(x,y) =Ax-1,y+Ax+1,y +Ax,y-1+Ax,y+1-4*Ax,yDiv定義了每個像素點的散度值已知像素6/7/10/11的div但不知具體顏色值？V(2)+

2、V(5)+V(7)+V(10)-4*V(6)=div(6)V(3)+V(6)+V(8)+V(11)-4*V(7)=div(7)V(6)+V(9)+V(11)+V(14)-4*V(10)=div(10)V(7)+V(10)+V(12)+V(15)-4*V(11)=div(11)N個變量的線性方程組！方程組形式：思路1：將目標(biāo)的梯度場”替換”背景圖的梯度場，根據(jù)散度線性方程組解像素顏色值。一點小問題混合策略：選擇模長較大的梯度值(保留兩者細節(jié))另一個問題，變量過多！(求解25W個變量的線性方程組，高斯消元O(n3)一點小思路，迭代求解：根據(jù)散度公式用周邊的像素值確定新的值(三重for循環(huán))6257

3、102571064(6)(6)4xAAxxdivAAxxdivx迭代0/1/10/100/1000/10000次：一階定常迭代法：B是矩陣,f是常向量核心目標(biāo):構(gòu)造一個B、f使得Ax=b的解與迭代公式吻合雅克比迭代法(Jacobi)高斯賽德爾迭代法(Gauss-Seidel)逐次超松弛迭代法(SOR)1kkxBxf按行進行雅克比迭代時，直接使用新一輪的x進行原地迭代一階定常迭代理論公式：111()()kkxDLUxDLb在G-S迭代中使用w松弛因子進行加權(quán)平均：減緩/加速變化速度，加快收斂一階定常迭代理論公式：11(1)kkkxxx11111() (1)()kkxDLDU xDLb考慮 的一般

4、形式設(shè)Ax=b的準(zhǔn)確解為x*迭代近似解誤差由于x*滿足方程x*=Bx*+f，有故能否收斂取決于是否直觀感受：只要B作用任何一個向量模長都變小則必定收斂1kkxBxf*kkexx11*()()()kkkkkexxBxfBxfB xxBe0lim0nnB e不可約矩陣：作為鄰接矩陣對應(yīng)的有向圖強連通嚴格對角占優(yōu)：每行對角線上的元素大于同行其他元素的和不嚴格對角占優(yōu)：每行對角線上的元素大于等于同行其他元素的和幾點結(jié)論：若矩陣A嚴格對角占優(yōu)，或者是不可約的若對角占優(yōu)矩陣，則Jacobi、G-S、0w=1的SOR算法必定收斂。擴展：泊松方程的FFT解法一些更有趣的東西patchmatch.mp4評估函數(shù)

5、f我方執(zhí)子選擇分數(shù)最高的方案敵方執(zhí)子選擇使我分數(shù)最低的方案0-33-3-3-21-36-30316011極大極大極小極小ab05-33 3-30 2 2-30-23 5 4 1-30 6 8 9-30 2極大節(jié)點的下界為極大節(jié)點的下界為 。極小節(jié)點的上界為極小節(jié)點的上界為 。剪枝的條件：剪枝的條件：后輩節(jié)點的后輩節(jié)點的 值值祖先節(jié)點的祖先節(jié)點的 值時，值時， 剪枝剪枝后輩節(jié)點的后輩節(jié)點的 值值祖先節(jié)點的祖先節(jié)點的 值時，值時， 剪枝剪枝簡記為：簡記為：極小極小極大，剪枝極大，剪枝極大極大極小，剪枝極小，剪枝486-315035-33-30 2 2-30-2309-300-303305411-3

6、1661abcdefghijkmn黑先手必勝？先手必勝！VCF/VCT狀態(tài)壓縮與置換表VC求解模塊為什么為什么 - 剪枝方法在圍棋上失效？剪枝方法在圍棋上失效？ - 剪枝方法存在的問題剪枝方法存在的問題 依賴于局面評估的準(zhǔn)確性依賴于局面評估的準(zhǔn)確性局面評估問題局面評估問題 大量專家知識大量專家知識 知識的統(tǒng)一性問題知識的統(tǒng)一性問題 人工整理人工整理從當(dāng)前局面的所有可落子點中隨機選擇一從當(dāng)前局面的所有可落子點中隨機選擇一個點落子個點落子重復(fù)以上過程重復(fù)以上過程直到勝負可判斷為止直到勝負可判斷為止經(jīng)多次模擬后，選擇勝率最大的點落子經(jīng)多次模擬后，選擇勝率最大的點落子選擇、擴展、模擬、反向轉(zhuǎn)播1952

7、年年Robbins提出的一個統(tǒng)計決策模型提出的一個統(tǒng)計決策模型多臂老虎機多臂老虎機多臂老虎機擁有多臂老虎機擁有k個手臂，拉動每個手臂所獲得個手臂，拉動每個手臂所獲得的收益遵循一定的概率且互不相關(guān)，如何找到的收益遵循一定的概率且互不相關(guān)，如何找到一個策略，使得拉動手臂獲得的收益最大化一個策略，使得拉動手臂獲得的收益最大化用于解決蒙特卡洛規(guī)劃中選擇落子點的問用于解決蒙特卡洛規(guī)劃中選擇落子點的問題題Upper Confidence Bound Algorithmfunction UCB1 for each 手臂手臂j: 訪問該手臂并記錄收益訪問該手臂并記錄收益 end for while 尚未達到訪

8、問次數(shù)限制尚未達到訪問次數(shù)限制 do: 計算每個手臂的計算每個手臂的UCB1信心上界信心上界Ij 訪問信心上界最大的手臂訪問信心上界最大的手臂 end while其中其中： 是手臂是手臂j所獲得回報的均值所獲得回報的均值n是到當(dāng)前這一時刻為止所訪問的總次數(shù)是到當(dāng)前這一時刻為止所訪問的總次數(shù) 是手臂是手臂j到目前為止所訪問的次數(shù)到目前為止所訪問的次數(shù)上式考慮了上式考慮了“利用利用”和和“探索探索”間的平衡間的平衡)()ln(2nTnXIjjjjX)(nTj由于蒙特卡羅規(guī)劃方法在沒有知識的指導(dǎo)由于蒙特卡羅規(guī)劃方法在沒有知識的指導(dǎo)時樹的擴展層數(shù)較少，不利于最優(yōu)解的獲時樹的擴展層數(shù)較少，不利于最優(yōu)解的

9、獲取，取，將將UCB1算法應(yīng)用于蒙特卡洛規(guī)劃算法算法應(yīng)用于蒙特卡洛規(guī)劃算法中，用于選擇可落子點中，用于選擇可落子點可落子點不是隨機可落子點不是隨機選擇，而是根據(jù)選擇，而是根據(jù)UCB1選擇選擇信心上限值最大的節(jié)點信心上限值最大的節(jié)點實際計算實際計算UCB1時，加一個參數(shù)時，加一個參數(shù)c進行調(diào)節(jié)：進行調(diào)節(jié)：)()ln(2nTncXIjjj模擬模擬 勝勝(1, 1)(1, -1)模擬模擬 負負(1, -1)(2, 0)模擬模擬 負負(1, -1)(2, 2)(3, -1)模擬模擬 負負(1, -1)(3, 3)(4, -2)到時！到時！Googles DeepMind AI Just Taught Itself To Walk.mp4SIGGRAPH 2018- DeepMimic paper (main video).mp4狀態(tài)狀態(tài)(state)、動作動作(action)、獎賞獎賞(reward)智能體智能體(Agent)根據(jù)當(dāng)前狀態(tài)來采取動作，獲得相應(yīng)的獎賞之后，再去改進這些動作，使得下次再到相同狀態(tài)