上帝掷骰子吗.pptx

《上帝掷骰子吗.pptx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、上帝掷色子吗谢其哲Introduction上帝掷色子吗->随机和概率能力：1.很大概率上的正确解2.较优解3.期望时间复杂度很好的正确解效果好最好写的平衡树Treap期末时当你开始预习数据结构的平衡树是什么感受？AVL，红黑，AA……Whatthef*ckaretheseuglytrees?被吓倒了？来看看居家旅行杀人越货必备之平衡树：Treap最好写的平衡树Treap堆+排序二叉树权值：key,aux。Key：左子树≤根≤右子树（排序二叉树）Aux:根≤左子树，右子树（堆）最好写的平衡树Treap插入：根据key找到插入的位

2、置随机生成aux，旋转调整最好写的平衡树TreapInsert(I,k)If(i==0)新建点，aux[i]=rand()If(kaux[i])left(i)最好写的平衡树TreapDelete差不多，只有单旋期望高度：O(logn)平均复杂度：O(logn)素数判定Miller-Rabin算法O()->O(logn)费马小定理：(p为素数,a

3、为合数时，x取值有很多，如素数判定Miller-Rabin算法令，d为奇数若或，则称p通过以a为底的素性测试（为素数）。原理：若p为素数，则考虑数列.最后一位是1，每一位是前一位的平方%p，设数列最后一个1的前一个是x，若x≠-1则p为合数。例子：a=2，p=13，p-1=12=数列：8,64%13=12,144%13=1素数判定Miller-Rabin算法素数一定会通过测试合数有1/4的概率通过测试取6次不同的底a，误判率不到千分之二取内无误判。判断A*B=C?Problem:给定A，B，C(n*n的矩阵)，判断是否A*B=

4、C随机生成D(1*n的矩阵)，判断是否D*A*B=D*C平面最近点对O(logn)两点距离≥X值的差解1:(对随机数据效果很好)把输入的点按x从小到大排序Fori=1tonforj=i+1tonif(x[j]–x[i]

5、三个点为顶点的三角形，使其周长最小。传统算法：O(nlogn)，难写，常数大O(n^3)随机向量投影，O(n^3)+break比O(nlogn)快费马点问题给定n个点，求一个点到这n个点的距离和最小。费马点爬山算法:(求局部最优解)随机设置一个初始点b，设置初始步长TWhileT>T_minFlag=falseFori=1tok生成长度为T的随机向量vIfb+v优于bb=b+v,flag=trueIf(flag==false)T=T*0.8模拟退火原理：热力学退火过程，给固体设置一个充分高的温度，温度高时，原子容易脱离原位置做

6、自由运动。再让其慢慢冷却。冷却时原子会趋向内能最小的地方，但也有一定概率去内能较大的地方，直到温度足够低。流程：初始温度T，初始解S，每次迭代次数L，降温系数pWhileT>T_minFlag=falseFork=1toL随机长度为T的增量D，S’=S+D计算df=f(S’)-f(S)df>0时(变优了)接受解S’,flag=truedf<0时(变差了)以接受解S’If(flag==false)T=T*p最小正方形覆盖(poj3301)枚举正方形一条边的角度，计算最小需要的边长。初始温度T=pi/2,角度S=0，每次迭代次数L

7、=20,降温系数p=0.5WhileT>1e-8Flag=falseFork=1toLt=T*(-1到1中的一个随机数)df=f(S)-f(S+t)（f(S)为一条边角度为S时最小正方形边长）df>0时接受解S’,flag=truedf<0时以接受解S’（）If(flag==false)T=T*p遗传算法原理：达尔文进化论和遗传学机理有n个个体（DNA序列），按照适应度（权值）从高到低排序。繁殖：选出两个个体，以高概率选择适应度高的，低概率选择适应度低的，以一定概率P交配得出两个新个体代替原来的老个体，新个体的DNA是老个体D

8、NA的组合。突变：以一定概率随机改变序列的一到两位。重复适应度高的个体得到保存，适应度低的个体淘汰。拓展遗传算法与蒙娜丽莎TSP问题->模拟退火谢谢！