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

胡康秀，王兵賢

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

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

胡康秀，王兵賢

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

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

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

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

1.1問題的提出

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

1.2問題的分析

首先將“巴格達(dá)竊賊問題”一般化，設(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為竊賊每次對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á)竊賊問題中取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è)門并嘗試失敗后，在后面選擇的過程中是不會再選擇此門，所以“竊賊每次選擇n個(gè)門的可能性總相等”這一假設(shè)雖然簡單，但并不科學(xué)。如果將該假設(shè)改為“竊賊每次選擇未選擇過的門的可能性總相等”，則問題的解決要更為復(fù)雜，但更具實(shí)際意義。

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

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

代入全期望公式：

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

2.2模型的推廣

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

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

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

條件數(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)域也越來越廣泛。禁忌搜索(簡稱TS)的思想最早由Fred Glover提出，它是對局部領(lǐng)域搜索的一種擴(kuò)展，是一種全局逐步尋優(yōu)算法，是對人類智力過程的一種模擬。本文在對“巴格達(dá)竊賊問題”模型改進(jìn)的時(shí)候就運(yùn)用了禁忌思想，推導(dǎo)出來的結(jié)果簡單明了，這對于估計(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)域取得了很大的成功，近年來又在函數(shù)全局優(yōu)化方面得到較多的研究，并大有發(fā)展的趨勢。

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

[2]孫榮恒.趣味隨機(jī)問題[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é)校長基金項(xiàng)目(DHXK0907)

10.13990/j.issn1001-3679.2014.06.024

TP301.6

A

1001-3679(2014)06-0854-03