三維網格圖的零可視警察與強盜博弈算法*

王佳慧,鐘發榮

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

1 引言

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

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

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

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中鄰接。因此，二維網格圖可以看成是路徑Pn1與Pn2的笛卡爾積圖，即Pn1□Pn2，用Gn1,n2表示；三維網格圖則可以看成是路徑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 二維網格圖G3,4和三維網格圖G3,4,3

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

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

3 劃分與邊界

3.1 二維網格圖

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

□

3.2 三維網格圖

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

證明以Z方向為例，有max{rl|1≤l≤n3}=m成立。可以分下列2種情況來討論：

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

□

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

□

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

□

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

□

4 最優搜索數

4.1 三維網格圖最優搜索數下界

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

□

證明利用反證法。

□

4.2 三維網格圖最優搜索數上界

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

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

證明在三維網格圖G2,2,3中，存在一種警察數為3且滿足單調性的搜索策略如下所示(頂點坐標見圖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個警察就可以將圖中所有頂點清理干凈，且滿足單調性Si+1?Si(i≥0)，因此mc0(G2,2,3)≤3。

□

Figure 6 Three-dimensional grid G2,2,3圖6 三維網格圖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是奇數的三維網格圖Gn1,n2,n3

5 搜索算法

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

□

根據上述結果，三維網格圖最優搜索數范圍內的成功搜索算法如算法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 結束語

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