胡康秀，王兵賢

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

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

胡康秀，王兵賢

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

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

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

1 巴格達竊賊問題模型

1.1問題的提出

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

1.2問題的分析

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

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

設(shè)隨機變量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個門的可能性總相等”這一假設(shè)雖然簡單，但并不科學(xué)。如果將該假設(shè)改為“竊賊每次選擇未選擇過的門的可能性總相等”，則問題的解決要更為復(fù)雜，但更具實際意義。

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

這樣，同樣令隨機變量X為竊賊到達地面需走的時間，Y為竊賊每次對3個門的選擇，則：

代入全期望公式：

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

2.2模型的推廣

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

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

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

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

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

2.3模型結(jié)果分析

當n=3,x1=3,x2=5,x3=7時，代入得：

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

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

而在改進的模型中，竊賊為獲得自由而奔走的平均時間為：

3 模型的應(yīng)用

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

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

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

10.13990/j.issn1001-3679.2014.06.024

TP301.6

A

1001-3679(2014)06-0854-03