巴格达窃贼问题模型改进及应用研究

胡康秀，王兵贤

(东华理工大学理学院，330013，南昌)

巴格达窃贼问题模型改进及应用研究

胡康秀，王兵贤

(东华理工大学理学院，330013，南昌)

在随机过程的研究中，已知若干条件，通过条件数学期望求总体数学期望对于不确定性事件的一种科学估计具有很强的实际意义。通过对巴格达窃贼问题建立数学模型，并运用禁忌搜索思想进行改进，在此基础上，对模型在计算机科学领域的应用提出展望。

条件数学期望；巴格达窃贼问题；数学模型

1 巴格达窃贼问题模型

1.1问题的提出

巴格达窃贼问题：一窃贼被关在3个门的地牢中，其中第一个门通向自由，出这个门后3 h便回到地面；第2个门通向一个地道，在此地道中走5 h后将返回地牢；第3个门通向一个更长的地道，沿这个地道走7 h后也返回地牢。问窃贼为获得自由而奔走的平均时间?[1-3]

1.2问题的分析

首先将“巴格达窃贼问题”一般化，设窃贼关在有n个门的地牢里，其中第1个门花xi小时便回到地面，第i个门花xi小时后又回到地牢(i=2,…,n)，如果窃贼每次选择n个门的可能性一样，求窃贼为获得自由而奔走的平均时间?

1.3数学模型的建立与求解

设随机变量X为窃贼到达地面需走的时间，Y为窃贼每次对n个门的选择，由于窃贼每次选择n个门的可能性一样，所以随机变量Y取到i(i=1,2,…,n)的概率均为1/n，由全期望公式：

(1)

因为

E(X|Y=1)=x1,E(X|Y=i)=xi+E(X),(i=2,…,n),

代入式(1)有：

从而得E(X)=x1+x2+…+xn。

在巴格达窃贼问题中取n=3,x1=3,x2=5,x3=7，有

E(X)=3+5+7=15。

故在“窃贼每次选择n个门的可能性一样”的前提下，窃贼为获得自由而奔走的平均时间为15 h。

2 模型的改进与推广

2.1模型的改进

事实上，在实际生活中，假如窃贼在选择第i个门并尝试失败后，在后面选择的过程中是不会再选择此门，所以“窃贼每次选择n个门的可能性总相等”这一假设虽然简单，但并不科学。如果将该假设改为“窃贼每次选择未选择过的门的可能性总相等”，则问题的解决要更为复杂，但更具实际意义。

现在回过头再来思考“巴格达窃贼问题”：如果窃贼每次选择未选择过的门的可能性总相等，问窃贼为获得自由而奔走的平均时间?

这样，同样令随机变量X为窃贼到达地面需走的时间，Y为窃贼每次对3个门的选择，则：

代入全期望公式：

从结果可以看出9<15，可见将条件“窃贼每次选择n个门的可能性总相等”，改为“窃贼每次选择未选择过的门的可能性总相等”大大改善了结果。

2.2模型的推广

从解决的过程中可以看出，如果门的个数比较多，问题变得更为复杂，上述方法不能很好的将问题的一般解找出。下面通过建立数学模型，寻求规律，找出问题的一般解。

问题的提出：设窃贼关在有n个门的地牢里，其中第1个门花x1小时便回到地面，第i个门花xi小时后又回到地牢(i=2,…,n)，如果窃贼每次选择未选择过的门的可能性总相等，求窃贼为获得自由而奔走的平均时间?

问题的求解：设X为窃贼获得自由需走的时间，Y为窃贼获得自由所尝试过的门的个数，由于窃贼每次选择未选择过的门的可能性总相等，故：

条件数学期望：

记sum=x1+x2+…+xn，由全期望公式得：

2.3模型结果分析

当n=3,x1=3,x2=5,x3=7时，代入得：

跟之前的结果一致。从推导的结果可以看出：在原模型中，窃贼为获得自由而奔走的平均时间为：

E(X)=x1+x2+…+xn=sum，

而在改进的模型中，窃贼为获得自由而奔走的平均时间为：

3 模型的应用

随着计算机技术的飞速发展，智能计算方法的应用领域也越来越广泛。禁忌搜索(简称TS)的思想最早由Fred Glover提出，它是对局部领域搜索的一种扩展，是一种全局逐步寻优算法，是对人类智力过程的一种模拟。本文在对“巴格达窃贼问题”模型改进的时候就运用了禁忌思想，推导出来的结果简单明了，这对于估计禁忌搜索算法运算时间有很强的参考价值。迄今为止，TS算法在组合优化、生产调度、机器学习、电路设计和神经网络等领域取得了很大的成功，近年来又在函数全局优化方面得到较多的研究，并大有发展的趋势。

[1]李裕奇.随机过程[M].北京:国防工业出版社,2008.

[2]孙荣恒.趣味随机问题[M].北京:科学出版社,2004.

[3]杨博．禁忌搜索算法在冷藏供应链配送网络中的应用研究[D].上海:上海海事大学，2005.

TheResearchontheModelofBagdadThiefProblem′sImprovementandApplication

HU Kangxiu,WANG Bingxian

(College of Science,East China Institute of Technology,330013,Nanchang,PRC)

In the study of stochastic processes,general mathematical expectation is obtained by means of conditional mathematical expectation when a number of conditions are known,which it is practically significant to scientifically estimate the uncertain events.The Bagdad Thief Problem is investigated in this paper.Its model is built and improved by means of Tabu search theory,and prospected in the field of computer science.

conditional mathematical expectation;Bagdad thief problem;mathematical model

2014-09-11;

2014-10-14

胡康秀(1978-)，女，江西新余人，硕士，副教授，主要从事代数方向。

东华理工大学校长基金项目(DHXK0907)

10.13990/j.issn1001-3679.2014.06.024

TP301.6

A

1001-3679(2014)06-0854-03