apio2018趣味算法应用讲课ii

1、清华大学 秦岳本讲旨在讲解OI算法在奇妙问题中的有趣简单的应用来帮助大家放松心情，愉悦身心，准备考试1、泊松图像编辑&高斯消元，线性代数2、游戏AI设计 &不可描述泊松图像融合改变天气无中生有改变天气改变表情去除高光融合纹理Fx(x,y)=Ax,y-Ax-1,yFy(x,y)=Ax,y-Ax,y-1(Fx,Fy)构成梯度向量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：将目标的梯度场”替换”背景图的梯度场，根据散度线性方程组解像素颜色值。一点小问题混合策略：选择模长较大的梯度值(保留两者细节)另一个问题，变量过多！(求解25W个变量的线性方程组，高斯消元O(n3)一点小思路，迭代求解：根据散度公式用周边的像素值确定新的值(三重for循环)6257

3、102571064(6)(6)4xAAxxdivAAxxdivx迭代0/1/10/100/1000/10000次：一阶定常迭代法：B是矩阵,f是常向量核心目标:构造一个B、f使得Ax=b的解与迭代公式吻合雅克比迭代法(Jacobi)高斯赛德尔迭代法(Gauss-Seidel)逐次超松弛迭代法(SOR)1kkxBxf按行进行雅克比迭代时，直接使用新一轮的x进行原地迭代一阶定常迭代理论公式：111()()kkxDLUxDLb在G-S迭代中使用w松弛因子进行加权平均：减缓/加速变化速度，加快收敛一阶定常迭代理论公式：11(1)kkkxxx11111() (1)()kkxDLDU xDLb考虑 的一般

4、形式设Ax=b的准确解为x*迭代近似解误差由于x*满足方程x*=Bx*+f，有故能否收敛取决于是否直观感受：只要B作用任何一个向量模长都变小则必定收敛1kkxBxf*kkexx11*()()()kkkkkexxBxfBxfB xxBe0lim0nnB e不可约矩阵：作为邻接矩阵对应的有向图强连通严格对角占优：每行对角线上的元素大于同行其他元素的和不严格对角占优：每行对角线上的元素大于等于同行其他元素的和几点结论：若矩阵A严格对角占优，或者是不可约的若对角占优矩阵，则Jacobi、G-S、0w=1的SOR算法必定收敛。扩展：泊松方程的FFT解法一些更有趣的东西patchmatch.mp4评估函数

5、f我方执子选择分数最高的方案敌方执子选择使我分数最低的方案0-33-3-3-21-36-30316011极大极大极小极小ab05-33 3-30 2 2-30-23 5 4 1-30 6 8 9-30 2极大节点的下界为极大节点的下界为 。极小节点的上界为极小节点的上界为 。剪枝的条件：剪枝的条件：后辈节点的后辈节点的 值值祖先节点的祖先节点的 值时，值时， 剪枝剪枝后辈节点的后辈节点的 值值祖先节点的祖先节点的 值时，值时， 剪枝剪枝简记为：简记为：极小极小极大，剪枝极大，剪枝极大极大极小，剪枝极小，剪枝486-315035-33-30 2 2-30-2309-300-303305411-3

6、1661abcdefghijkmn黑先手必胜？先手必胜！VCF/VCT状态压缩与置换表VC求解模块为什么为什么 - 剪枝方法在围棋上失效？剪枝方法在围棋上失效？ - 剪枝方法存在的问题剪枝方法存在的问题 依赖于局面评估的准确性依赖于局面评估的准确性局面评估问题局面评估问题 大量专家知识大量专家知识 知识的统一性问题知识的统一性问题 人工整理人工整理从当前局面的所有可落子点中随机选择一从当前局面的所有可落子点中随机选择一个点落子个点落子重复以上过程重复以上过程直到胜负可判断为止直到胜负可判断为止经多次模拟后，选择胜率最大的点落子经多次模拟后，选择胜率最大的点落子选择、扩展、模拟、反向转播1952

7、年年Robbins提出的一个统计决策模型提出的一个统计决策模型多臂老虎机多臂老虎机多臂老虎机拥有多臂老虎机拥有k个手臂，拉动每个手臂所获得个手臂，拉动每个手臂所获得的收益遵循一定的概率且互不相关，如何找到的收益遵循一定的概率且互不相关，如何找到一个策略，使得拉动手臂获得的收益最大化一个策略，使得拉动手臂获得的收益最大化用于解决蒙特卡洛规划中选择落子点的问用于解决蒙特卡洛规划中选择落子点的问题题Upper Confidence Bound Algorithmfunction UCB1 for each 手臂手臂j: 访问该手臂并记录收益访问该手臂并记录收益 end for while 尚未达到访

8、问次数限制尚未达到访问次数限制 do: 计算每个手臂的计算每个手臂的UCB1信心上界信心上界Ij 访问信心上界最大的手臂访问信心上界最大的手臂 end while其中其中： 是手臂是手臂j所获得回报的均值所获得回报的均值n是到当前这一时刻为止所访问的总次数是到当前这一时刻为止所访问的总次数 是手臂是手臂j到目前为止所访问的次数到目前为止所访问的次数上式考虑了上式考虑了“利用利用”和和“探索探索”间的平衡间的平衡)()ln(2nTnXIjjjjX)(nTj由于蒙特卡罗规划方法在没有知识的指导由于蒙特卡罗规划方法在没有知识的指导时树的扩展层数较少，不利于最优解的获时树的扩展层数较少，不利于最优解的

9、获取，取，将将UCB1算法应用于蒙特卡洛规划算法算法应用于蒙特卡洛规划算法中，用于选择可落子点中，用于选择可落子点可落子点不是随机可落子点不是随机选择，而是根据选择，而是根据UCB1选择选择信心上限值最大的节点信心上限值最大的节点实际计算实际计算UCB1时，加一个参数时，加一个参数c进行调节：进行调节：)()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状态状态(state)、动作动作(action)、奖赏奖赏(reward)智能体智能体(Agent)根据当前状态来采取动作，获得相应的奖赏之后，再去改进这些动作，使得下次再到相同状态