2010年12月10日星期五

序贯蒙特卡洛(二)



积和式近似

前面两个例子都没有展开,这次写具体些。
白老师曾说,计算数学其实分两块,一块研究“计数”,就是“数数儿”,另一块研究算数,就是解方程。积和式属于前者的范畴。

积和式定义
http://en.wikipedia.org/wiki/Permanent

A是一个n阶0-1方阵,积和式perm(A)=#{A(p)=1, p是(1,...,n)的一个排列},其中A(p)=A[1][p[1]]*...*A[n][p[n]]
物理意义:p是一条长度为n的哈密尔顿路径,A是约束矩阵,A[i][j]=1表示允许路径的第i步走到j。A(p)=1表示哈密尔顿路径p满足约束A。
perm(A)就是满足约束A的哈密尔顿路径的个数。
(上个版本说和哈密尔顿路径问题等价是错误的)

下面考虑计算perm(A)的蒙特卡洛方法。

M1:大海捞针
生成N个(1,...,n)的排列p_1,...,p_N
perm(A)的估计=n!*(A(p_1)+...+A(p_N))/N

M2:走一步说一步
一步步构造哈密尔顿路径,每次等概率地走到还没走过的且能走的地方,直到无路可走。
尝试m次:
w[0]=1
走第k步时,如果没路了,则w=0,尝试失败
否则w[k]=w[k-1]*没走过且可走的地方的个数
最后w[n]作为这次尝试的权重w
perm(A)的估计:m次权重w的平均值

M3:倾向于先走不容易走到的地方
思路是如果一个地方少有机会能走,则应该先走。
一步步构造哈密尔顿路径,每次走到还没走过的且能走的地方k的概率,反比于k的剩余的可走到的机会数,直到无路可走。如果一个地方必须这次去,则概率1地走向哪里。
尝试m次:
w[0]=1
走第k步时,如果没路了,则w=0,尝试失败
否则w[k]=w[k-1]*第k步选择所选落脚点的概率的倒数
最后w[n]作为这次尝试的权重w
perm(A)的估计:m次权重w的平均值

实验
A=
[[ 0.  1.  1.  1.  1.  1.  1.]
 [ 1.  1.  0.  0.  1.  1.  1.]
 [ 1.  1.  1.  1.  1.  1.  1.]
 [ 1.  1.  1.  1.  0.  1.  1.]
 [ 1.  0.  1.  1.  1.  0.  0.]
 [ 1.  1.  1.  1.  1.  1.  1.]
 [ 1.  1.  0.  1.  1.  1.  1.]]
真值perm(A)=1434
三种方法估计的均值(样本数20)
[ 1415.          1448.91071429  1434.89212938]
下图是M1,M2,M3的Boxplot
可以明显看出方差的减小


没有评论: