模拟退火与最小steiner树课件

1、模拟退火与最小steiner生成树 王茂芝目录图的着色问题及其应用:交通信号灯问题模拟退火算法及其注意点最小steiner生成树问题及其求解1 交通信号灯问题问题描述与背景介绍13种不同线路目标不冲突时间尽可能少abcde问题分析与转化四色问题转化：类似于地图着色问题，交通信号灯问题也可以归结为图的顶点着色问题。把路口的所有线路表示为无向图的顶点，两个顶点之间有一边连接当且仅当对应的两条路线在路口相交，而把各个路线划分为尽可能少的互不相交的k组，恰恰等价于求相应的无向图的最小色数k。得到13个顶点20条边的图，而且ba、dc、ed孤立（拐小弯）。问题求解（算法设计讨论）把交通信号灯问题归结为更

2、一般的无向图顶点着色问题。穷举法：令色数k从2开始，用k种颜色分别对13个顶点着色，共有k13种情形，对每一种情形进行检查，直到找到一种着色方案使得20条边的两顶点全为异色。若k=5,则最坏情况需要进行20（ 213 313 413 + 513 ）次比较算法设计讨论剪枝法假设顶点ab着色为c1,则点ab的所有邻点ea、da、bc、bd都不必着色c1第一点，例如ab，可以只有一种颜色，由颜色的对称性，ab取其它（k-1）种颜色的情形可不必再检查。使用此剪枝法一项可把计算量缩小到原来的1/k启发式算法贪心法（greedy）是一种有效的设计快速算法的策略，不过，它不一定总能得到最优解。2 模拟退火算

3、法物理背景算法描述注意事项应用实例物理背景在物理学中,对固体物质进行退火处理时,通常先将它加温溶化,使其中的粒子可自由运动,然后随着物质温度的下降,粒子也形成了低能态的晶格.若在凝结点附近的温度下降速度足够慢,则固体物质一定会形成最低能量的基态.对于组合优化问题来说,它也又类似的过程,也就是说物体中固体物质的退火过程与组合优化问题具有相似性.组合优化问题也是在解空间寻求花费函数最小(或最大)的解.模拟退火算法描述在神经网络系统中,设系统所有可能状态为V=v1,v2,vN,与系统相对应有一能量E,它是系统状态的函数,即E(V).设控制参数为温度T,我们的目标是找到某一个系统状态v*,使E(v*)

4、=min(vi,viV).模拟退火思想是:让T从一个足够高的值慢慢下降,对每个T,用Metropolis抽样法在计算机上模拟该系统在此T下的热平衡状态,即对当前状态vi经过随机扰动产生一个新状态vj,计算系统的能量增加E=E(vj)-E(vi),并以概率 e(-E/kT)接受vj作为当前状态.续初始化.任给一初始状态v0,vi=v0,计算E(v0),将参数T置一初始温度值.产生一随机扰动v,按下式计算E: E=E(vi+v)-E(vi).若E0,则转(5),否则在(0,1)区间上产生一个均匀分布的随机数若e(-E/kT) ,则转(2)用vi+v来取代原来的vi,并令E=E+ E在该T下,检验系

5、统是否稳定,若不稳定则转(2)以某一方式取TT退火过程是否结束,否则转(2)初始化:v0,E(v0),T=T0扰动v, E=E(vi+v)-E(vi)E0迭代Vi=Vi+v, E=E + E (0,1) e(-E/kT) T是否稳定降温 退火结束算法结束 YNYYYNNN注意事项在上述过程中,模拟退火过程是否达到能量E的最小值,取决于T0是否足够高和T下降得是否充分慢,以及对每个T时系统是否稳定.T0初始选取均匀地随机抽样v,取E(v)的方差为T0在所有可能状态中,选取两个状态vi和vj,使差| vE|=|E(vi)-E(vj)|最大,T0为该值的某一倍数由经验给出3.2 最小生成树的算法Kr

6、uskal算法:边考虑Prim算法:点考虑应用实例最小生成树概念:设G=(V,E)是无向连通带权图,即一个网络.E中每条边(v,w)的权为cvw.如果G的子图G是一棵包含G的所有定点的树,则称G为G的生成树.生成树上各边权的总和称为该生成树的耗费.在G的所有生成树中,耗费最小的生成树称为G的最小生成树.网络的最小生成树在实际中有广泛的应用.例如, 通信线路设计.最小生成树的性质用贪心算法设计策略可以设计出构造最小生成树的有效算法.最小生成树性质:设G=(V,E)是连通带权图, U是V的真子集.如果(u,v) E,且u U,v V-U,且在所有这样的边中,(u,v)的权cuv最小,那么一定存在G

7、的一棵最小生成树,它以(u,v)为其中一条边.这个性质有时也称为MST性质.(这一性质可以用反证法得到证明)最小生成树的Prim算法设G=(V,E)是连通带权图,V=1,2,n.构造G的最小生成树的Prim算法的基本思想是:首先置S=1,然后,只要S是V的真子集,就进行如下的贪心选择:选取满足条件iS, j V-S,且cij最小的边,将顶点j添加到S中.这个过程一直持续进行到S=V时为止.在这个过程中选取到的所有边恰好构成G的一棵最小生成树.Prim算法思想描述 void Prim(int n,float c) T=O; S=1; while(S!=V) (i,j)=iS且jV-S的最小权边;

8、 T=T(i,j); S=S j; /end of whileKruskal算法给定无向连通带权图G=(V,E),V=1,2,n. Kruskal算法构造G的最小生成树的基本思想是:首先将G的n个顶点看成n个孤立的连通分支.将所有的边按权从小到大排序.然后从第一条边开始,依边权递增的顺序查看每一条边,并按下述方法连接两个不同的连通分支:当查看到第k条边(v,w)时,如果端点v和w分别是当前两个不同的连通分支T1和T2中的顶点时,就用边(v,w)将T1和T2连接成一个连通分支,然后继续查看第k+1条边;如果端点v和w在当前的同一个连通分支中,就直接再查看第k+1条边.这个过程一直进行到只剩下一个

9、连通分支时为止.此时,这个连通分支就是G的一棵最小生成树.3.3 最小steiner生成树见PDF文档(教程)问题:某地区有3个村子v1,v2,v3,村子之间有道路相连,地区希望工程办公室计划在该地区建一所学校v*,使得学校v*到3个村子的道路总长为最小.问学校应建在哪里?数学描述在欧氏平面给定三个点v1,v2,v3,在平面上求一个点v*,使得点v*到v1,v2,v3三点的总距离为最小.由于这一问题是法国数学家fermat大约在1640年最早考虑的,因此点v*称为fermat点.与fermat同一时代的意大利数学家torricelli和cavalieri各自独立地解决了这一问题.Fermat点

10、和Steiner点因此,fermat问题是euclid平面上给定三点求最小steiner生成树问题,而fermat点即是steiner点.之所以将fermat点称为是steiner点,其原因是19世纪中期,瑞士数学家J.Steiner把三点fermat问题推广到Euclid平面上n个给定的点,即欧氏平面上给定n个点v1,v2,vn,在平面上求一点v*,使得点v*到点v1,v2,vn的总距离为最小.Euclid平面n点steiner问题欧氏平面上n点steiner问题：设v1,v2,vn是欧氏平面上n个给定的点.在平面上在点v1,v2,vn外取s个点v1*,v2*,vs*.记V0v1,v2,vn

11、, Vs=v1*,v2*,vs*, V=V0UVs.以V为顶点集合的n+s阶完全图记做GVs. 对于图GVs中的任意边e,以边e的两个端点间的距离为边e的权,则GVs是一个赋权图.赋权图GVs中最小生成树记做Tvs,对于给定的非负整数s,赋权图GVs的最小生成树Tvs的权w(Tvs)依赖于s点集Vs选取,对于s点集Vs,最小生成树TVs中权最小的记做Ts.当s=0时,T0即是以V0为顶点集合的n阶赋权完全图的最小生成树.对于所有非负整数s,最小生成树Ts中权最小的记做T*,它称为n个给定的点v1,v2,vn的最小steiner生成树.T*中不属于V0的点称为steiner点.问题对于欧氏平面给

12、定的n个点,最小steiner树是否存在.最小steiner生成树T*上有多少个steiner点,这些steiner点的几何位置有什么特点.(s=n-2)怎样确定最小steiner生成树T*,是否有一种确定最小steiner生成树的有效算法.(Melzak)如果那样的有效算法不存在,能否给出一种近似解.对于给定的n个点,最小steiner生成树T*和以n个点为顶点的n解赋权完全图的最小生成树T0的权之比w(T*)/w(T0)称为steiner比,问题是其下确界是多少.3.4 一般n点steiner问题把欧氏距离改为赋范空间中的范数3.5 通讯网络极小生成树两个通讯站间通讯线路的费用与线路的长度

13、成正比。通过引入若干个“虚设站”并构造一个新的Steiner树就可以降低由一组站生成的最小生成树所需的费用。用这种方法可降低费用多达1-sqrt(3)/2=13.4% 。而且为构造一个有n个站的网络的费用最低的Steiner树绝不需要多于(n-2)个虚设站。对于局部网络而言，有必要用直折线距离或“棋盘”距离来代替欧氏直线距离。假定希望你设计一个有9个站的局部网络的最低造价生成树。这9个站的直角坐标是:续限定你只能用直线，而且所有的虚设站必须位于格点上(即其坐标是整数)。每条直线段的造价是其长度值。 求该网络的一个极小费用树。 假定每个站的费用为d3/2*w，其中d通讯站度，若w=1.2，求极小费用树。 试推广本问题。穷举法31个可能的点位,虚设点可能