巴格達竊賊問題模型改進及應用研究

胡康秀，王兵賢

(東華理工大學理學院，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。……