《基于离散模型的 双边搜索 博弈问题的研究.pdf》由会员分享，可在线阅读，更多相关《基于离散模型的 双边搜索 博弈问题的研究.pdf（4页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、S c i e n c e&T e c h n o l o g yR e v i e w 2 0 0 7V o l.2 5N o.2(S u mN o.2 2 4)0引言搜索论作为军事运筹学的一个分支,是根据二战中的搜潜、扫雷等军事行动经验,由K o o p m a n最先发展起来的理论 1-3。搜索论自提出以来,在人员搜救、信息查询、治安、反潜、反恐、战术对抗等领域 4 均有广泛的应用背景和指导意义。K o o p m a n搜索论的核心是以静止目标为研究对象的最优搜索力配置模型,S t o n e 5 发展了最优搜索论,利用动态规划方法完善了搜索力最优分配的理论,这个阶段的搜索理论中,由于
2、被搜索目标是无意识的,此类问题也称为单边搜索问题。当搜索双方都是具有智能的主体时,被搜索者不希望被搜索者发现,进而会根据搜索者的行为采取规避的策略。这类问题称为双边搜索问题 6,或搜索对抗问题。双边搜索问题首先用于描述反潜搜索过程,D a n s k i n 7 借助 速 度 圆 的 概 念 优 化 了 传 统 的 反 潜 策 略,G a l和A l p e r n 8 着重讨论了树形搜索域的双边搜索问题,Wa s h b u r n 9 提出以单元格为基础的多阶段搜索模型,H o h z a k i 1 0-1 1 则讨论了搜索者在固定移动路径上的巡逻搜索对抗问题。已有的研究多专注于对搜索双
3、方本身的各种约束条件的分析,而忽略了结合搜索域中的各处探测概率进行分析。在现实的搜索行动中,被搜索者会支付较大的花费移动到容易躲藏的地方(即探测概率较小的地方)基于离散模型的双边搜索博弈问题的研究陈 俊1,王令群2,郑应平11.同济大学控制科学与工程系,上海2 0 1 8 0 42.水产大学计算机科学与技术系,上海2 0 0 0 9 0摘要在双边搜索中,被搜索者不希望被搜索到,因此可以将搜索双方的行为看成二人零和博弈问题。在考虑搜索双方的搜索花费和搜索单元格的探测概率情况下描述了搜索过程,并基于离散搜索模型提出了一类双边搜索问题的算法,通过仿真算例,分析了搜索双方在均衡解下的搜索结果。关键词搜
4、索论;双边搜索;二人零和中图分类号 O 2 2 9,O 2 2 5文献标识码 A文章编号 1 0 0 0-7 8 5 7(2 0 0 7)0 2-0 0 6 4-0 4T w o-s i d e dS e a r c hG a me B a s e do nD i s c r e t e Mo d e lC H E NJ u n1,WA N GL i n g q u n2,Z H E N GY i n g p i n g11.D e p a r t m e n t o f C o n t r o l S c i e n c e a n dE n g i n e e r i n g,T o n
5、g j i U n i v e r s i t y,S h a n g h a i 2 0 1 8 0 4,C h i n a2.D e p a r t m e n t o f C o m p u t e r S c i e n c e a n dT e c h n o l o g y,F i s h e r i e s U n i v e r s i t y,S h a n g h a i 2 0 0 0 9 0,C h i n aA b s t r a c t:At w o-s i d e ds e a r c h,w h e r et h et a r g e t m a k e s e
6、 v e r ye f f o r t t oe v a d es e a r c h e r s d e t e c t i o n,c a nb er e g a r d e da s at w o-p e r s o nz e r o-s u mg a m e.T h eg a m ei sf o r m u l a t e dw i t hc o n s i d e r a t i o no fs e a r c hc o s t so nb o t hp l a y e r sa n dd e t e c t i o np r o b a b i l i t i e so f c e
7、 l l s.B a s e do na d i s c r e t e m o d e l,as o l u t i o nt ot h i s t w o-s i d e ds e a r c hg a m ei s p r o p o s e d.T h ee q u i l i b r i u mo f b o t hp l a y e r s i s a n a l y z e da f t e rt h e s i m u l a t i o n.K e yWo r d s:s e a r c ht h e o r y;t w o-s i d e ds e a r c h;t w
8、o-p e r s o nz e r o-s u mC L CN u mb e r s:O 2 2 9,O 2 2 5D o c u me n t C o d e:AA r t i c l eI D:1 0 0 0-7 8 5 7(2 0 0 7)0 2-0 0 6 4-0 4来稿日期:2 0 0 6-1 0-1 9作者简介:陈 俊,男,上海市曹安公路4 8 0 0号同济大学控制科学与工程系,硕士生,主要研究方向为搜索论、智能控制;E-m a i l:c h e n _ j u n _ 1 9 8 2 1 6 3.c o m郑应平(通讯作者),男,上海市曹安公路4 8 0 0号同济大学控制科学
9、与工程系,教授,主要从事复杂系统、智能控制等领域的研究工作;E-m a i l:y p z h e n g v i p.s i n a.c o mA r t i c l e s6 4科技导报2 0 0 7年第2 5卷第2期(总第2 2 4期)进行规避,这样就会对搜索双方的策略产生影响。本文在Wa s h b u r n的离散搜索模型基础上,提出了一种综合考虑搜索花费和探测概率的双边搜索模型,用以描述搜索双方混策略的变化情况。1双边搜索的模型根据被搜索者的特性,可将双边搜索模型按照两种方式划分:被搜索者是运动的还是固定的;被搜索者是否能观测到搜索者的历史搜索过程。被搜索者固定的双边搜索模型,主要
10、体现在G a l 1 2 的工作中。在G a l的树形搜索域里,被搜索者一开始选择一个节点进行躲藏,随后保持位置固定,支付函数为搜索成功的时间或经过的路程,搜索者期望极小化这个量,被搜索者期望极大化这个量。G a l和R u c k l e 1 3 随后证明这一模型最终可以划归为中国邮差问题进行处理。在这种情况下,被搜索者是否能观察到搜索者的历史搜索过程,对搜索结果没有影响。针对搜索双方都具有运动能力的情况,R u c k l e 1 4 首先研究了一类搜索双方相互不知道对方历史行为的搜索模型。但事实上在一些情况下,如典型的搜潜行动中,搜潜直升机投放的主动声纳仪发出的声纳信号可以在海中传播很远
11、,潜艇即使远离直升机的投放位置,也能探测到主动声纳仪的投放位置,进而感知到搜潜直升机的历史搜索路径。D a s k i n研究了此类被搜索者能够感知到搜索者的历史搜索路径的问题,并给出了相应对策 1 5。在将双边搜索模型应用于其他类型的搜索域,如楼层中分割的房间、一片根据地形特征进行划分的山区时,普遍采用了离散模型进行分析 1 6。在模型中离散是指:1)搜索区域是离散的,即将整个搜索区域划分成N个单元格,或抽象成具有若干节点的树;2)搜索的时间是离散的,即搜索双方的所有行为,如搜索者从某单元i移动到单元j、搜索者在单元j进行探测、被搜索者的移动等,都是一个最小时间!的倍数。下面将讨论的双边搜索
12、模型是离散的、搜索双方均是可运动的、被搜索者可以感知搜索者的历史搜索路径的一类新模型。与传统双边搜索模型相比,此模型将综合考虑搜索花费和探测概率的影响。1.1新模型描述在双边搜索中,被搜索者是对抗的。对于搜索者来说,希望花费尽可能少的代价,以尽可能大的概率发现搜索目标,而被搜索者则希望尽量防止被发现。显然,随着对抗的反复进行,不存在一个纯策略,否则搜索者将轻易地找到被搜索者,或被搜索者将轻易地回避搜索者。因此这是一个二人零和博弈问题。考虑双边搜索模型。某个搜索域划分成N个单元格,并以小写字母i,j,k,表示不同的单元格,(i,j,k=1,2,3,N)。搜索域内有一个搜索者和一个被搜索者,在某次
13、对抗搜索的回合中,搜索者和被搜索者分别各自选取一个单元格进行搜索和规避,如果在有限的回合内,搜索者发现了被搜索者,则判定搜索者胜,否则判定被搜索者胜。假设搜索者从单元格i,移动到单元格j所需要的搜索花费(可以是燃油、补给等物理变量)为f(i,j);当搜索者在单元格j而被搜索者在单元格k时,搜索者进行一次探测找到躲避者的概率称为探测概率Pj k,探测概率反映不同单元格进行探测的难易程度,且有Pj k=0j kPjj=k(1)搜索者的策略空间为S=s1,s2,sN,被搜索者的策略空间为E=e1,e2,eN。以F(j,n)表示第n个回合搜索者在单元格j进行探测后的支付函数,则F(i,n+1)为下回合
14、搜索者移动到单元格i进行探测后的支付函数。F(j,0)=0且F(i,n+1)F(j,n)。在第n+1次搜索回合结束后,从搜索者角度来讲,进行一次搜索活动的支付函数就有两种情况:1)搜索者和被搜索者不在一个单元格内,则搜索者的探测是不可能发现被搜索者的,此时搜索者需要支付的值为f(i,j)+F(j,n)。2)搜索者和被搜索者同时处于一个单元格i内,则搜索者进行探测时,以概率Pi发现被搜索者,此时搜索者需要支付值:f(i,j)+(1-Pj)F(j,n)。基于上述分析,可以得出某次对抗搜索中,搜索者需要支付的总支出:F(i,n+1)=j#sj f(i,j)+(1-k$ekPj k)F(j,n)(2)
15、由式(1),上式可以简化为F(i,n+1)=j$sj f(i,j)+(1-ejPj)F(j,n)(3)显然对于搜索者来说希望最小化搜索支出,而被搜索者希望极大化搜索支出。因此,搜索双方的对策函数为F(i,n+1)=m i nsm a xej$sj f(i,j)+(1-ejPj)F(j,n)(4)注意到方程右侧是e的线性函数,对于被搜索者来说,他的最优策略就是选择j$sj PjF(j,n)最小项,从而,可将式(4)简化为F(i,n+1)=m i nsj$sj f(i,j)+F(j,n)-m i njsjPjF(j,n)(5)研究论文6 5S c i e n c e&T e c h n o l o
16、 g yR e v i e w 2 0 0 7V o l.2 5N o.2(S u mN o.2 2 4)令,z=m i njejPjF(j,n),最终可以将双边搜索化为一个动态规划问题:m i n j!sj f(i,j)+F(j,n)-z(6)s.t.sjPjF(j,n)-z 0(7)j!sj=1(8)可以解得,该动态规划问题有两个均衡解:z=sjPjF(j,n)#j=1,2,N,或者z=0由式(8),可在仿真计算时,通过以下形式计算。z=j!1PjF(j,n)$%-1(9)因此,当对抗搜索双方均以最优策略进行搜索与躲避时,第n+1回合的均衡对策值为F(j,n+1)=m i nm i nj
17、f(i,j)+F(j,n),s*j f(i,j)+F(j,n)-&z(1 0)s*j=zPjF(j,n);e*j=1-F(i,n+1)-f(i,j)F(j,n)$%1Pj(1 1)再根据式(1 0)和式(1 1),以及搜索者的历史路径,就可以计算得到搜索双方在每个搜索回合的最优搜索-规避的混策略。1.2基于新模型的仿真运算由以上的理论推导可以知道,对于一个分割成N个单元格的搜索域,若知道每个单元格的搜索花费和探测概率,便可以对搜索双方的行为进行分析。不失一般性,假设某搜索区域可以划分为3个单元格,相对位置关系如图1。单元格2到其他两个单元格所需花费相等,f(1,2)=f(2,1)=f(2,3)
18、=f(3,2)=2。而单元格1,3之间相隔较远需要的花费为3,f(1,3)=f(3,1)=3。在原单元格内保持不动需要的花费为1,f(1,1)=f(2,2)=f(3,3)=1。首先分析等探测概率下的双边搜索情况,即设每个单元格的探测概率相同:P=P1P2P3=0.8 0.8 0.8,由此得到的1 0次搜索回合结果列于表1。从表1中的数据可以看出,在第5回合,搜索者以0.3 2 60,0.3 4 81,0.3 2 60的概率分别对3个单元格进行搜索,假设搜索者最后到达单元格1进行搜索,而被搜索者观测到搜索者处于单元格1,则根据式(4),躲避者应当分别以0.1 0 05,0.2 8 88,0.6
19、1 07的概率前往单元格1,2,3躲避。对于搜索者来说,在第6回合应当以更大的概率0.3 4 69搜索单元格2,因为此单元格到达其他单元格所需要的花费比较小。其次分析不等探测概率下的双边搜索情况,即同样花 费 矩 阵 不 变,探 测 矩 阵 变 为P=P1P2P3=0.80.90.1,其表明在单元格3进行搜索具有更大的难度;那么由此得到的1 0次搜索结果列于表2。可以发现,虽然单元格2到达其他单元格的平均时间较短,但在多次搜索回合之后,搜索者和被搜索者反而会以较大的概率选择探测概率较小的单元格3进行探测和躲藏。当然,给定每个单元格的搜索花费和探测概率后,以上算法可以简单推广到多单元格的情况。2
20、结论本文在综合考虑了搜索花费和探测概率对搜索双方混策略的影响后,建立一类改进的新型双边搜索模型。图1 3单元格的搜索区域F i g.1 S e a r c hd o ma i nw i t ht h r e ec e l l s表1等探测概率下的双边搜索结果T a b l e1 T w o-s i d e ds e a r c hr e s u l t so f e q u a ld e t e c t i o np r o b a b i l i t yF(1,n)s1F(2,n)s2F(3,n)s3n=1n=2n=3n=4n=5n=6n=7n=8n=9n=1 01.0 0 002.0 0
21、003.0 0 004.0 0 004.9 0 005.5 0 595.9 4 856.2 7 376.5 1 276.6 8 820.3 3 330.3 3 330.3 2 950.3 2 520.3 2 600.3 2 660.3 2 700.3 2 720.3 2 740.3 2 751.0 0 002.0 0 003.0 0 003.8 6 674.5 5 915.1 5 645.6 0 045.9 2 686.1 6 666.3 4 270.3 3 330.3 3 330.3 4 090.3 4 950.3 4 810.3 4 690.3 4 610.3 4 560.3 4 520.
22、3 4 501.0 0 002.0 0 003.0 0 004.0 0 004.9 0 005.5 0 595.9 4 856.2 7 376.5 1 276.6 8 820.3 3 330.3 3 330.3 2 950.3 2 520.3 2 600.3 2 660.3 2 700.3 2 720.3 2 740.3 2 75表2不等探测概率下的双边搜索结果T a b l e2 T w o-s i d e ds e a r c hr e s u l t so f u n e q u a ld e t e c t i o np r o b a b i l i t yF(1,n)s1F(2,n
23、)s2F(3,n)s3n=1n=2n=3n=4n=5n=6n=7n=8n=9n=1 01.0 0 002.0 0 003.0 0 004.0 0 005.0 0 006.0 0 007.0 0 008.0 0 008.9 3 639.5 2 910.1 6 980.1 6 980.1 6 980.1 6 860.1 6 550.1 6 160.1 5 710.1 5 360.1 5 440.1 5 531.0 0 002.0 0 003.0 0 004.0 0 005.0 0 006.0 0 006.9 0 527.6 1 038.2 5 068.8 3 620.1 5 090.1 5 090
24、.1 5 090.1 4 990.1 4 710.1 4 560.1 4 680.1 4 790.1 4 800.1 4 821.0 0 002.0 0 003.0 0 004.0 0 004.9 4 725.7 7 676.5 3 027.2 2 467.8 5 858.4 3 910.6 7 920.6 7 920.6 7 920.6 8 160.6 8 750.6 9 280.6 9 600.6 9 860.6 9 750.6 9 65(1 1)再根据式(1 0)和式(1 1),以及搜索者的历史路径,就可以计算得到搜索双方在每个搜索回合的最优搜索-规避的混策略。1.2基于新模型的仿真运算
25、由以上的理论推导可以知道,对于一个分割成N个单元格的搜索域,若知道每个单元格的搜索花费和探测概率,便可以对搜索双方的行为进行分析。不失一般性,假设某搜索区域可以划分为3个单元格,相对位置关系如图1。单元格2到其他两个单元格所需花费相等,f(1,2)=f(2,1)=f(2,3)=f(3,2)=2。而单元格1,3之间相隔较远需要的花费为3,f(1,3)=f(3,1)=3。在原单元格内保持不动需要的花费为1,f(1,1)=f(2,2)=f(3,3)=1。首先分析等探测概率下的双边搜索情况,即设每个单元格的探测概率相同:P=P1P2P3=0.8 0.8 0.8,由此得到的1 0次搜索回合结果列于表1。
26、从表1中的数据可以看出,在第5回合,搜索者以0.3 2 60,0.3 4 81,0.3 2 60的概率分别对3个单元格进行搜索,假设搜索者最后到达单元格1进行搜索,而被搜索者观测到搜索者处于单元格1,则根据式(4),躲避者应当分别以0.1 0 05,0.2 8 88,0.6 1 07的概率前往单元格1,2,3躲避。对于搜索者来说,在第6回合应当以更大的概率0.3 4 69搜索单元格2,因为此单元格到达其他单元格所需要的花费比较小。其次分析不等探测概率下的双边搜索情况,即同样花 费 矩 阵 不 变,探 测 矩 阵 变 为P=P1P2P3=0.80.90.1,其表明在单元格3进行搜索具有更大的难度
27、;那么由此得到的1 0次搜索结果列于表2。可以发现,虽然单元格2到达其他单元格的平均时间较短,但在多次搜索回合之后,搜索者和被搜索者反而会以较大的概率选择探测概率较小的单元格3进行探测和躲藏。当然,给定每个单元格的搜索花费和探测概率后,以上算法可以简单推广到多单元格的情况。2结论本文在综合考虑了搜索花费和探测概率对搜索双方混策略的影响后,建立一类改进的新型双边搜索模型。表1等探测概率下的双边搜索结果T a b l e1 T w o-s i d e ds e a r c hr e s u l t so f e q u a ld e t e c t i o np r o b a b i l i t
28、 y(1 1)再根据式(1 0)和式(1 1),以及搜索者的历史路径,就可以计算得到搜索双方在每个搜索回合的最优搜索-规避的混策略。1.2基于新模型的仿真运算由以上的理论推导可以知道,对于一个分割成N个单元格的搜索域,若知道每个单元格的搜索花费和探测概率,便可以对搜索双方的行为进行分析。不失一般性,假设某搜索区域可以划分为3个单元格,相对位置关系如图1。单元格2到其他两个单元格所需花费相等,f(1,2)=f(2,1)=f(2,3)=f(3,2)=2。而单元格1,3之间相隔较远需要的花费为3,f(1,3)=f(3,1)=3。在原单元格内保持不动需要的花费为1,f(1,1)=f(2,2)=f(3,
29、3)=1。首先分析等探测概率下的双边搜索情况,即设每个单元格的探测概率相同:P=P1P2P3=0.8 0.8 0.8,由此得到的1 0次搜索回合结果列于表1。从表1中的数据可以看出,在第5回合,搜索者以0.3 2 60,0.3 4 81,0.3 2 60的概率分别对3个单元格进行搜索,假设搜索者最后到达单元格1进行搜索,而被搜索者观测到搜索者处于单元格1,则根据式(4),躲避者应当分别以0.1 0 05,0.2 8 88,0.6 1 07的概率前往单元格1,2,3躲避。对于搜索者来说,在第6回合应当以更大的概率0.3 4 69搜索单元格2,因为此单元格到达其他单元格所需要的花费比较小。其次分析
30、不等探测概率下的双边搜索情况,即同样花 费 矩 阵 不 变,探 测 矩 阵 变 为P=P1P2P3=0.80.90.1,其表明在单元格3进行搜索具有更大的难度;那么由此得到的1 0次搜索结果列于表2。可以发现,虽然单元格2到达其他单元格的平均时间较短,但在多次搜索回合之后,搜索者和被搜索者反而会以较大的概率选择探测概率较小的单元格3进行探测和躲藏。当然,给定每个单元格的搜索花费和探测概率后,以上算法可以简单推广到多单元格的情况。2结论本文在综合考虑了搜索花费和探测概率对搜索双方混策略的影响后,建立一类改进的新型双边搜索模型。表2不等探测概率下的双边搜索结果T a b l e2 T w o-s
31、i d e ds e a r c hr e s u l t so f u n e q u a ld e t e c t i o np r o b a b i l i t yA r t i c l e s6 6科技导报2 0 0 7年第2 5卷第2期(总第2 2 4期)对该算法的仿真数据研究可知,当搜索域各处的探测概率相差不大时,如果搜索域里某些地区,到达其他地区所需的花费较少,即交通较方便时,该地区应当重点加强搜索。而如果某些地区的探索概率比较小(如可以隐蔽的地方较多等),则这些地区就是搜索和躲避相对频繁的地区。仿真算例的结果进一步显示,在双边搜索问题中,搜索者和被搜索者的理想搜索、规避地点是
32、那些交通方便,且探测难度较大的地方。综上,仿真计算结果展示该新模型在一定程度上可以定量描述抓捕、搜索入侵者等一类的问题,具有一些现实意义。本文对于双边搜索行为的研究还是初步的,考虑到的环境和影响因素都较为简单。例如,如果被搜索者起初并未意识到搜索者的存在;或被搜索者不知道搜索者的目的,因而可能采取或对抗或合作的态度等,都会对双方的搜索策略造成影响。此外,在现实中,被搜索者经过一段路径会留下痕迹,使得自己被发现的概率增大;而搜索区域也不是简单的拓扑结构。上述这些情况,都对搜索模型的建立和分析提出了挑战,有待将来进一步细致的研究。参考文献(R e f e r e n c e s)1 K O O P
33、 MA NBO.T h et h e o r yo f s e a r c h:1.k i n e ma t i cb a s e s J .O p e r a t i o nR e s e a r c h,1 9 5 6,4(3):3 2 4-3 4 6.2 K O O P MA NBO.T h et h e o r yo f s e a r c h:2.t a r g e t d e t e c t i o n J .O p e r a t i o nR e s e a r c h,1 9 5 6,4(5):5 0 3-5 3 1.3 K O O P MA NBO.T h eT h e o
34、 r yo f s e a r c h:3.t h eo p t i mu md i s t r i b u t i o no f s e a r c h i n ge f f o r t s J .O p e r a t i o nR e s e a r c h,1 9 5 7,5(5):6 1 3-6 2 6.4 张宝康.搜索论的某些进展和应用 J ,运筹学杂志,1 9 9 0,9(1):3 1-3 8.Z H A N G B a o k a n g.S o mei mp r o v e me n ta n d a p p l i c a t i o n so ns e a r c ht
35、h e o r y J .C h i n e s eJ o u r n a l o f O p e r a t i o nR e-s e a r c h,1 9 9 0,9(1):3 1-3 8.5 S T O N E LD.T h e o r yo fo p t i ma ls e a r c h M.N e wY o r k:A c a d e mi cP r e s s,1 9 7 5.6 S A K A G U C H I S.T w o-s i d e ds e a r c hg a me s J .J o u r n a l o ft h eO p e r a t i o n sR
36、 e s e a r c h S o c i e t yo fJ a p a n,1 9 7 3(1 6):2 0 7-2 2 5.7 D A N S K I NJM.AH e l i c o p t e r v s.S u b ma r i n es e a r c hg a me J .O p e r a t i o nR e s e a r c h,1 9 6 8,1 6(3):5 0 9-5 1 7.8 A L P E R NS,G A LS.R e n d e z v o u ss e a r c ho nt h el i n ew i t hd i s t i n g u i s
37、h a b l ep l a y e r s J .S I A M J o u r n a l o f C o n t r o l a n dO p t i mi z a t i o n,1 9 9 5,3 3(4):1 2 7 0-1 2 7 6.9 WA S H B U R NAR.S e a r c h-e v a s i o ng a mei naf i x e dr e g i o n J .O p e r a t i o nR e s e a r c h,1 9 8 0,2 8(6):1 2 9 0-1 2 9 8.1 0 H O H Z A K I R.S e a r c ha
38、l l o c a t i o ng a me J .E u r o p e a nJ o u r-n a l o f O p e r a t i o n a l R e s e a r c h,2 0 0 6,1 7 2(1):1 0 1-1 1 9.1 1 H O H Z A K IR.I I D A K A.S e a r c hg a mew h e nas e a r c hp a t hi sg i v e n J .E u r o p e a nJ o u r n a l o f O p e r a t i o n a l R e-s e a r c h,2 0 0 0,1 2
39、4(1):1 1 4-1 2 4.1 2 G A LS.S e a r c hg a me s M.N e wY o r k:A c a d e mi cP r e s s,1 9 8 0.1 3 A L P E R NS,G A LS.S e a r c h i n gf o r a na g e n t w h oma yo rma yn o t w a n t t ob ef o u n d J .O p e r a t i o nR e s e a r c h,2 0 0 2,5 0(2):3 1 1-3 2 3.1 4 R U C K L E W.G e o me t r i cg
40、a me sa n d t h e i ra p p l i c a t i o n s M.B o s t o n:P i t ma n,1 9 8 3.1 5 T H O MA SLC,WA S H B U R NAR.D y n a mi cs e a r c hg a me s J .O p e r a t i o nR e s e a r c h,1 9 9 1,3 9(3):4 1 5-4 2 2.1 6 A B I-Z E I D I,J O H N RF.S A R P l a n:Ad e c i s i o ns u p p o r ts y s t e m f o r C
41、 a n a d i a ns e a r c ha n dr e s c u eo p e r a t i o n s J .E u r o p e a nJ o u r n a l o f O p e r a t i o n a l R e s e a r c h,2 0 0 5,1 6 2(3):6 3 0-6 5 3.(责任编辑赵 佳)取2枚均匀的骰子,每枚骰子的6个面都分别刻着1 6的点数。同时抛掷这2枚骰子,考虑这样一个问题:需要将2枚骰子掷多少次才能使得到2个6点的可能性不小于5 0%?这也是一个在玩骰子的赌徒中长期流传的问题。早期许多数学家曾研究并解答过这一问题。如以卡尔丹公式
42、闻名的1 6世纪意大利数学家卡尔丹(1 5 0 1-1 5 7 6)做过这样的分析:因为每3 6次中有1次机会掷出两个6点,所以平均起来,每掷3 6次这样的结果会出现一次。因此,在半数这么多次即1 8次投掷中,出现2个6点的机会能达到5 0%。1 7世纪,一位名叫梅累的贵族给出的答案是:2 4次。然而,他发现当以一比一打赌“每掷2 4次总会有一次2个骰子都是6点”时,自己仍是输多赢少。为什么会这样?1 6 5 2年前后,梅累就此问题向当时法国著名数学家帕斯卡(1 6 2 3-1 6 6 2)请教。帕斯卡经过思考,给出了正确的回答。你也来解答一下这个问题吧(可以使用计算器)。上期“3枚骰子的点数
43、”答案问题的关键在于:每种情况出现的机会并不一定相等。为了出现3个骰子点数完全相同,只有一种途径,比如要出现“3,3,3”,只能3个骰子都掷出3点。但当3个骰子点数有2个相同时,有3种不同的途径掷出,比如要出现 3,3,4,3个骰子掷的结果可以如下:3,3,4;3,4,3;4,3,3。而当3个骰子点数均不相同时,则有6种不同的途径掷出。这样,我们就可以算出3个骰子点数之和为9的六种情况(即1,2,6;1,3,5;1,4,4;2,2,5;2,3,4;3,3,3)出现的总的可能数为:6+6+3+3+6+1=2 5,因此9可有2 5种不同的途径掷出。同样,我们可以算出3个骰子点数之和为1 0的6种情况(即1,3,6;1,4,5;2,2,6;2,3,5;2,4,4;3,3,4)出现的总的可能数为:6+6+3+6+3+3=2 7,因此1 0可有2 7种不同途径掷出。有趣的是,伽利略在解答这一问题时,把3个骰子掷出来后可能有的2 1 6种结果全列了出来!在这种穷举的基础上,伽利略得出了与我们上面分析相同的结论。(供稿韩雪涛责任编辑黄永明)科技智力游戏 好玩的数学双6点之惑研究论文6 7