王佳慧,鐘發(fā)榮

(浙江師范大學數(shù)學與計算機科學學院，浙江 金華 321004)

1 引言

圖搜索[1,2]是數(shù)學、計算機等領(lǐng)域熱門的話題，它為現(xiàn)實生活中的很多問題提供了數(shù)學模型。在圖搜索中有2類玩家：搜索者和入侵者。根據(jù)玩家占據(jù)的圖中位置、移動速度和可見性等因素可將圖搜索分為邊搜索、點搜索、混合搜索和快速搜索等[3,4]。警察與強盜博弈就是圖搜索的一種，研究的主要問題是確定能成功捕獲強盜的最少警察數(shù)。該問題最早于1978年由Quilliot[5]提出，后被Nowakowski和Winkler單獨研究[6]。上述研究只分析了1個警察就可完成搜索的情況；之后又有學者對有多個警察的情況展開了研究[7 - 9]。Bonato等[10]總結(jié)了傳統(tǒng)博弈模型下有關(guān)最少警察數(shù)的大量結(jié)論。最新的研究結(jié)果可查看文獻[11,12]。

零可視警察與強盜博弈是傳統(tǒng)博弈模型的一種變形，與傳統(tǒng)博弈模型唯一的區(qū)別是強盜不可見。通?？紤]在一個連通圖G中的零可視警察與強盜博弈，有2類玩家：1個強盜，多個警察。零可視警察與強盜博弈按照輪次進行。首輪，警察先選定初始頂點位置，之后強盜選擇初始頂點位置。每一輪按照先警察后強盜的順序交替行動，玩家每次只可以移動到鄰接頂點或者停留在原頂點。整個博弈過程中，強盜在任一時刻都知道警察的位置，而警察不知道強盜位置。若在有限輪數(shù)內(nèi)，警察與強盜在同一頂點，強盜被捕獲。我們把在零可視警察與強盜博弈中能成功捕獲強盜的最少警察數(shù)稱為最優(yōu)搜索數(shù)，用c0(G)表示，且在最優(yōu)搜索數(shù)下的策略稱為最優(yōu)搜索策略。零可視警察與強盜博弈模型進一步增加了警察的搜索難度，最早由To?ic[13]在1985年提出，并且給出了路徑、圈、完全圖和完全二部圖的最優(yōu)搜索數(shù)的特征；Tang[14]提出了求解樹的最少警察的二次時間算法；韓小東[15]研究了疊書圖的最優(yōu)搜索數(shù)。

在零可視警察與強盜博弈中，關(guān)鍵問題是確定最優(yōu)搜索數(shù)的上下界。上述研究并未給出較好的方法，直至Dereniowskl等[16]用路寬來確定單調(diào)性下最優(yōu)搜索數(shù)的上下界，接著有學者計算出不同圖的路寬[17,18]，三維網(wǎng)格圖的路寬由Otachi等[19]計算得出。但是，在一般情況下的最優(yōu)搜索數(shù)仍然無法確定。之后Xue等[20,21]提出用劃分的方法來確定最優(yōu)搜索數(shù)的下界，并且成功求出平面網(wǎng)格圖等簡單圖的最優(yōu)搜索數(shù)，但該方法在一些較為復雜的圖中并未得到驗證。因此，本文將在零可視下對三維網(wǎng)格圖中的警察與強盜搜索模型展開研究，引入劃分思想確定三維網(wǎng)格圖最優(yōu)搜索數(shù)的下界，利用單調(diào)性原則確定三維網(wǎng)格圖最優(yōu)搜索數(shù)的上界，最后提出一種三維網(wǎng)格圖在最優(yōu)搜索數(shù)范圍內(nèi)可行的搜索算法。

2 基本概念

本文用Pn表示具有n個頂點的路徑，用G1□G2表示圖G1和圖G2的笛卡爾積圖，滿足V(G1□G2)={(u,v)|u∈G1,v∈G2}，且2個頂點(u,v),(u′,v′)∈V(G1□G2)鄰接當且僅當u=u′且v和v′在G2中鄰接，或者v=v′且u和u′在G1中鄰接。因此，二維網(wǎng)格圖可以看成是路徑Pn1與Pn2的笛卡爾積圖，即Pn1□Pn2，用Gn1,n2表示；三維網(wǎng)格圖則可以看成是路徑Pn1、Pn2和Pn3的笛卡爾積圖，即Pn1□Pn2□Pn3，用Gn1,n2,n3(n1,n2,n3≥2)表示。如圖1所示。因為笛卡爾積運算是可交換的，因此本文的證明只需考慮2≤n1≤n2≤n3即可。

Figure 1 Two-dimensional grid G3,4 and three-dimensional grid G3,4,3圖1 二維網(wǎng)格圖G3,4和三維網(wǎng)格圖G3,4,3

Figure 2 Two-dimensional grid G4,5 with |V1|=10,|?V1|=4圖2 |V1|=10，|?V1|=4的二維網(wǎng)格圖G4,5

單調(diào)性是圖搜索中的一個重要概念，若用Si表示警察第i輪移動后臟頂點的集合，且在一個成功捕獲強盜的搜索策略中若滿足Si+1?Si(i≥0)，則該搜索策略是單調(diào)的。本文把滿足單調(diào)性的零可視警察與強盜博弈中能成功捕獲強盜的最少警察數(shù)記作mc0(G)。若一個警察在相鄰輪數(shù)間沿著邊(u,v)在頂點u和頂點v之間來回移動，則稱該警察在邊(u,v)上振蕩。

3 劃分與邊界

3.1 二維網(wǎng)格圖

證明運用反證法。假設|?V1|

□

3.2 三維網(wǎng)格圖

Figure 3 Three-dimensional grid Gn1,n2,n3(2≤n1≤n2≤n3)圖3 三維網(wǎng)格圖Gn1,n2,n3(2≤n1≤n2≤n3)

證明以Z方向為例，有max{rl|1≤l≤n3}=m成立?？梢苑窒铝?種情況來討論：

Figure 4 Three-dimensional grid G3,3,4 with m=6,|?V1|=6,|V1|=10圖4 m=6,|?V1|=6,|V1|=10的三維網(wǎng)格圖G3,3,4

□

Figure 5 Three-dimensional grid G3,3,3 with m=6,|?V1|=6圖5 m=6,|?V1|=6三維網(wǎng)格圖G3,3,3

□

證明與定理2類似。如圖4所示。

□

證明與定理2類似。如圖4所示。

□

4 最優(yōu)搜索數(shù)

4.1 三維網(wǎng)格圖最優(yōu)搜索數(shù)下界

同理，在X和Y方向可以根據(jù)推論1和推論2按照如上方式證明。

□

證明利用反證法。

□

4.2 三維網(wǎng)格圖最優(yōu)搜索數(shù)上界

定理5[12]假設G是一個連通圖，則c0(G)≤mc0(G)。

引理4G2,2,3是一個三維網(wǎng)格圖，則mc0(G2,2,3)≤3。

證明在三維網(wǎng)格圖G2,2,3中，存在一種警察數(shù)為3且滿足單調(diào)性的搜索策略如下所示(頂點坐標見圖6)：

第1輪：警察λi的初始位置分別為：

λ1:v1,1,λ2:v1,2,λ3:v1,4,S1={v1,3,v2,1,v2,2,v2,3,v2,4,v3,1,v3,2,v3,3,v3,4}

第2輪：

λ1:v1,1→v2,1,λ2:v1,2→v2,2,λ3:v1,4→v1,3,S2={v2,3,v2,4,v3,1,v3,2,v3,3,v3,4}

第3輪：

λ1:v2,1,λ2:v2,2→v2,3,λ3:v1,3→v1,4,S3={v2,4,v3,1,v3,2,v3,3,v3,4}

第4輪：

λ1:v2,1,λ2:v2,3→v2,2,λ3:v1,4→v2,4,S4={v3,1,v3,2,v3,3,v3,4}

第5輪：

λ1:v2,1→v3,1,λ2:v2,2→v3,2,λ3:v2,4→v2,3,S5={v3,3,v3,4}

第6輪：

λ1:v3,1→v3,4,λ2:v3,2→v3,3,λ1:v2,3→v2,4,S6=?。

上述搜索策略中只需3個警察就可以將圖中所有頂點清理干凈，且滿足單調(diào)性Si+1?Si(i≥0)，因此mc0(G2,2,3)≤3。

□

Figure 6 Three-dimensional grid G2,2,3圖6 三維網(wǎng)格圖G2,2,3

①若t<2i-1：警察λi將在邊(vj,2i,vj,2i-1)上振蕩;

②若t=2i-1：警察λi將從vj,2i移動到vj+1,2i;

③若t>2i-1：警察λi將在邊(vj+1,2i,vj+1,2i+1)上振蕩。

(3)令j←j+1，重復(2)和(3)操作，直至j=n3，停止。

□

Figure 7 Three-dimensional grid Gn1,n2,n3,n1n2is odd圖7 n1n2是奇數(shù)的三維網(wǎng)格圖Gn1,n2,n3

5 搜索算法

證明由定理4和定理6可得。

□

根據(jù)上述結(jié)果，三維網(wǎng)格圖最優(yōu)搜索數(shù)范圍內(nèi)的成功搜索算法如算法1所示(頂點的標號方式參照圖7)。

算法1Search algorithm onGn1,n2,n3

輸入：n1,n2,n3,wheren1≤n2≤n3;vl,t,where 1≤l≤n3,1≤t≤n1n2。

輸出：c0(Gn1,n2,n3),M[vl,t]。

1.InitialM[vl,t]=0;

2.Ifn1n2is oddthen

4.Forj=1 ton3-1

5.Fort=1 ton1n2

7.If(t<2i-1)then

8.P[vj,2i-1]=0;P[vj,2i-2]=1

orP[vj,2i-1]=1;P[vj,2i-2]=0;

9.Elseif(t=2i-1)then

10.P[vj+1,2i-1]=1;P[vj,2i-1]=0;

M[vj,2i-1]=1;

11.Else

12.P[vj+1,2i-1]=0;P[vj+1,2i]=1;

orP[vj+1,2i-1]=1;P[vj+1,2i]=0;

M[vj,2i]=1;

13.Endif

14.Endif

15.Endfor

16.Endfor

17.Endfor

18.P[vn,t]=1,where 1≤t≤n1n2;

20.Else/*n1n2is even*/

22.Forj=1 ton3-1

23.P[vj+1,1]=1;P[vj,1]=0;M[vj,1]=1;

24.Fort=1 ton1n2

26.If(t<2i-1)then

27.P[vj,2i]=0;P[vj,2i-1]=1;

orP[vj,2i]=1;P[vj,2i-1]=0;

28.Elseif(t=2i-1)then

29.P[vj,2i]=0;P[vj+1,2i]=1;M[vj,2i]=1;

30.Else

31.P[vj+1,2i]=0;P[vj+1,2i+1]=1;

orP[vj+1,2i]=1;P[vj+1,2i+1]=0;

M[vj,2i+1]=1;

32.Endif

33.Endif

34.Endfor

35.Endfor

36.Endfor

37.P[vn,t]=1,where 1≤t≤n1n2;

39.Endif

6 結(jié)束語

本文通過將零可視警察與強盜博弈抽象成頂點清理模型，利用劃分的方法和單調(diào)性的原則對三維網(wǎng)格圖的最優(yōu)搜索數(shù)展開研究，最終得到三維網(wǎng)格圖最優(yōu)搜索數(shù)的上下界，并給出了在三維網(wǎng)格圖中一種可行的搜索算法。