文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > Simulated Annealing for Graph Bisection
侵权投诉

Simulated Annealing for Graph Bisection

Simulated Annealing for Graph Bisection

Blu er: Metropolis: 0

P1 b

P2 b

P3 b

P1

P2

\excess"\shortfall" (reserved) (redistributed)

1

Figure 1: Sample space for Blu er and Metropolis process run at temperature T for t= state with probability at most exp(? (

Claim 5.2 For any temperature 0< T

p ( 2T 3= n log2 n) steps encounters a -atypical 2 T 2= log 2 n)).

poly(n) and any tolerance, the Metropolis

Proof Acting in parallel with the Metropolis process, we introduce a second random b b b

process, the blu er, which should shadow it closely without knowledge of the graph G. The blu er is de ned as follows. Given the current state^, the next state^ 0 is chosen as i with probability Pi= P (^; i). This will be implemented by partitioning 0; 1) into intervals of length Pi, and selecting^ 0= i when the random\coin toss" falls into the i'th interval. This\blu er's mapping" taking^ to^ 0 is applied to^ ( ) to yield^ (p+ 1). We modify the blu er's procedure according to a correction tape: a set of O(t n=T ) times j and associated moves m( j ). For any time j,^ ( j ) will be the state obtained from^ ( j? 1) by applying move m( j ), rather than the state obtained by applying the blu er's mapping. Note that an initial state^ (0), a random sequence ( ( ))t=1, and a correction tape, completely determine the blu er's sequence (^( ))t=1. Base a trajectory of the Metropolis process on the same sample space of 's as used for the blu er, as follows. For any=^, take as a starting point the same partitioning of 0; 1) into intervals of length Pi . Now| given the graph G| imagine overlaying each of these intervals with an interval of length Pi= PG (; i), matching up the left ends. (Refer to Figure 1.) When Pi< Pi, the Pi -long interval is\labeled" i, and the\excess" interval of length Pi? Pi is reserved. When Pi> Pi, the label i is applied to the interval Pi, giving a\shortfall" of Pi? Pi . Because the total of the excesses is equal to the total of the shortfalls, we end by arbitrarily distributing the labels that fell short into the reserved excess spaces. By construction, each i labels a collection of intervals of total length Pi, so 0= i is chosen with the correct Metropolis probability PG (; i). Furthermore, if^ ( )= ( ), the blu er's uncorrected successor for^ ( ) and the 1 Metropolis's (+1) are equal with probability 1? 2 kP?P k, over random (+1) 2 0; 1): they are unequal only if (+ 1) falls into one of the\excess" regions, and the total size 1 of these is 2 kP? P k. We now claim that for graph G satis es P? P k= pn=T ) for all bisections any from any which is not^rough (whichwith high kprobability ), initial state (0)= (0), O( b b b b b b b b b

Simulated Annealing for Graph Bisection

上一页第11页

你可能喜欢

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email