巴格達(dá)竊賊問(wèn)題模型改進(jìn)及應(yīng)用研究

胡康秀，王兵賢

(東華理工大學(xué)理學(xué)院，330013，南昌)

巴格達(dá)竊賊問(wèn)題模型改進(jìn)及應(yīng)用研究

胡康秀，王兵賢

(東華理工大學(xué)理學(xué)院，330013，南昌)

在隨機(jī)過(guò)程的研究中，已知若干條件，通過(guò)條件數(shù)學(xué)期望求總體數(shù)學(xué)期望對(duì)于不確定性事件的一種科學(xué)估計(jì)具有很強(qiáng)的實(shí)際意義。通過(guò)對(duì)巴格達(dá)竊賊問(wèn)題建立數(shù)學(xué)模型，并運(yùn)用禁忌搜索思想進(jìn)行改進(jìn)，在此基礎(chǔ)上，對(duì)模型在計(jì)算機(jī)科學(xué)領(lǐng)域的應(yīng)用提出展望。

條件數(shù)學(xué)期望；巴格達(dá)竊賊問(wèn)題；數(shù)學(xué)模型

1 巴格達(dá)竊賊問(wèn)題模型

1.1問(wèn)題的提出

巴格達(dá)竊賊問(wèn)題：一竊賊被關(guān)在3個(gè)門的地牢中，其中第一個(gè)門通向自由，出這個(gè)門后3 h便回到地面；第2個(gè)門通向一個(gè)地道，在此地道中走5 h后將返回地牢；第3個(gè)門通向一個(gè)更長(zhǎng)的地道，沿這個(gè)地道走7 h后也返回地牢。問(wèn)竊賊為獲得自由而奔走的平均時(shí)間?[1-3]

1.2問(wèn)題的分析

首先將“巴格達(dá)竊賊問(wèn)題”一般化，設(shè)竊賊關(guān)在有n個(gè)門的地牢里，其中第1個(gè)門花xi小時(shí)便回到地面，第i個(gè)門花xi小時(shí)后又回到地牢(i=2,…,n)，如果竊賊每次選擇n個(gè)門的可能性一樣，求竊賊為獲得自由而奔走的平均時(shí)間?

1.3數(shù)學(xué)模型的建立與求解

設(shè)隨機(jī)變量X為竊賊到達(dá)地面需走的時(shí)間，Y為竊賊每次對(duì)n個(gè)門的選擇，由于竊賊每次選擇n個(gè)門的可能性一樣，所以隨機(jī)變量Y取到i(i=1,2,…,n)的概率均為1/n，由全期望公式：

(1)

因?yàn)?/p>

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

代入式(1)有：

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

在巴格達(dá)竊賊問(wèn)題中取n=3,x1=3,x2=5,x3=7，有

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

故在“竊賊每次選擇n個(gè)門的可能性一樣”的前提下，竊賊為獲得自由而奔走的平均時(shí)間為15 h。

2 模型的改進(jìn)與推廣

2.1模型的改進(jìn)

事實(shí)上，在實(shí)際生活中，假如竊賊在選擇第i個(gè)門并嘗試失敗后，在后面選擇的過(guò)程中是不會(huì)再選擇此門，所以“竊賊每次選擇n個(gè)門的可能性總相等”這一假設(shè)雖然簡(jiǎn)單，但并不科學(xué)。如果將該假設(shè)改為“竊賊每次選擇未選擇過(guò)的門的可能性總相等”，則問(wèn)題的解決要更為復(fù)雜，但更具實(shí)際意義。

現(xiàn)在回過(guò)頭再來(lái)思考“巴格達(dá)竊賊問(wèn)題”：如果竊賊每次選擇未選擇過(guò)的門的可能性總相等，問(wèn)竊賊為獲得自由而奔走的平均時(shí)間?

這樣，同樣令隨機(jī)變量X為竊賊到達(dá)地面需走的時(shí)間，Y為竊賊每次對(duì)3個(gè)門的選擇，則：

代入全期望公式：

從結(jié)果可以看出9<15，可見(jiàn)將條件“竊賊每次選擇n個(gè)門的可能性總相等”，改為“竊賊每次選擇未選擇過(guò)的門的可能性總相等”大大改善了結(jié)果。

2.2模型的推廣

從解決的過(guò)程中可以看出，如果門的個(gè)數(shù)比較多，問(wèn)題變得更為復(fù)雜，上述方法不能很好的將問(wèn)題的一般解找出。下面通過(guò)建立數(shù)學(xué)模型，尋求規(guī)律，找出問(wèn)題的一般解。

問(wèn)題的提出：設(shè)竊賊關(guān)在有n個(gè)門的地牢里，其中第1個(gè)門花x1小時(shí)便回到地面，第i個(gè)門花xi小時(shí)后又回到地牢(i=2,…,n)，如果竊賊每次選擇未選擇過(guò)的門的可能性總相等，求竊賊為獲得自由而奔走的平均時(shí)間?

問(wèn)題的求解：設(shè)X為竊賊獲得自由需走的時(shí)間，Y為竊賊獲得自由所嘗試過(guò)的門的個(gè)數(shù)，由于竊賊每次選擇未選擇過(guò)的門的可能性總相等，故：

條件數(shù)學(xué)期望：

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

2.3模型結(jié)果分析

當(dāng)n=3,x1=3,x2=5,x3=7時(shí)，代入得：

跟之前的結(jié)果一致。從推導(dǎo)的結(jié)果可以看出：在原模型中，竊賊為獲得自由而奔走的平均時(shí)間為：

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

而在改進(jìn)的模型中，竊賊為獲得自由而奔走的平均時(shí)間為：

3 模型的應(yīng)用

隨著計(jì)算機(jī)技術(shù)的飛速發(fā)展，智能計(jì)算方法的應(yīng)用領(lǐng)域也越來(lái)越廣泛。禁忌搜索(簡(jiǎn)稱TS)的思想最早由Fred Glover提出，它是對(duì)局部領(lǐng)域搜索的一種擴(kuò)展，是一種全局逐步尋優(yōu)算法，是對(duì)人類智力過(guò)程的一種模擬。本文在對(duì)“巴格達(dá)竊賊問(wèn)題”模型改進(jìn)的時(shí)候就運(yùn)用了禁忌思想，推導(dǎo)出來(lái)的結(jié)果簡(jiǎn)單明了，這對(duì)于估計(jì)禁忌搜索算法運(yùn)算時(shí)間有很強(qiáng)的參考價(jià)值。迄今為止，TS算法在組合優(yōu)化、生產(chǎn)調(diào)度、機(jī)器學(xué)習(xí)、電路設(shè)計(jì)和神經(jīng)網(wǎng)絡(luò)等領(lǐng)域取得了很大的成功，近年來(lái)又在函數(shù)全局優(yōu)化方面得到較多的研究，并大有發(fā)展的趨勢(shì)。

[1]李裕奇.隨機(jī)過(guò)程[M].北京:國(guó)防工業(yè)出版社,2008.

[2]孫榮恒.趣味隨機(jī)問(wèn)題[M].北京:科學(xué)出版社,2004.

[3]楊博．禁忌搜索算法在冷藏供應(yīng)鏈配送網(wǎng)絡(luò)中的應(yīng)用研究[D].上海:上海海事大學(xué)，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-)，女，江西新余人，碩士，副教授，主要從事代數(shù)方向。

東華理工大學(xué)校長(zhǎng)基金項(xiàng)目(DHXK0907)

10.13990/j.issn1001-3679.2014.06.024

TP301.6

A

1001-3679(2014)06-0854-03