基于籠圖-快速搜索的移動(dòng)機(jī)器人目標(biāo)搜索

孫曉莉，鐘發(fā)榮

(浙江師范大學(xué) 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，浙江 金華 321000)

0 引 言

在生物界存在一類常見問(wèn)題，群狼搜索一只羊。若搜索區(qū)域存在道路縱橫交錯(cuò)的山洞，為了搜索到羊，群狼該如何利用最少的狼按照某種路線盡早捉到羊呢?移動(dòng)機(jī)器人目標(biāo)搜索與此類動(dòng)物捕食問(wèn)題類似，主要是研究一群作為搜索者的機(jī)器人應(yīng)當(dāng)如何合作、采取怎樣的搜索策略去搜索目標(biāo)。移動(dòng)機(jī)器人目標(biāo)搜索是實(shí)現(xiàn)救援、防御等任務(wù)的重要環(huán)節(jié)，是多機(jī)器人研究的重要內(nèi)容之一[1-4]。所謂搜索問(wèn)題，即搜索者試圖搜索到目標(biāo)。在某特定區(qū)域的移動(dòng)機(jī)器人目標(biāo)搜索實(shí)質(zhì)是圖搜索問(wèn)題(graph searching)的實(shí)際應(yīng)用案例。圖搜索，即一群搜索者在某類圖上利用最少的搜索者去搜索目標(biāo)。因此，考慮將給定區(qū)域的移動(dòng)機(jī)器人目標(biāo)搜索問(wèn)題的搜索區(qū)域抽象為類似結(jié)構(gòu)的圖，然后選用合適的圖搜索模型，將其轉(zhuǎn)化為圖搜索問(wèn)題進(jìn)行研究。

針對(duì)不同的搜索問(wèn)題，圖搜索問(wèn)題提供了多種模型，如邊搜索、點(diǎn)搜索、混合搜索、快速搜索等[5-9]。考慮到移動(dòng)機(jī)器人目標(biāo)搜索問(wèn)題中機(jī)器人造價(jià)花費(fèi)高及機(jī)器人需避免出現(xiàn)來(lái)回往返移動(dòng)等需求，文中利用快速搜索模型進(jìn)行研究。Dyer等人[10]介紹了快速搜索模型并提出一種用于計(jì)算樹的快速搜索數(shù)的線性時(shí)間算法。Stanley和Yang[11]給出一個(gè)用于計(jì)算Halin圖的快速搜索數(shù)的線性時(shí)間算法，并提出一種二次時(shí)間算法來(lái)計(jì)算三次圖的快速搜索數(shù)。Yang[12]證明了求解圖的快速搜索數(shù)是NP完全問(wèn)題，他還證明了判斷圖G的快速搜索數(shù)是否等于G中奇數(shù)頂點(diǎn)數(shù)的一半是NP完全問(wèn)題；Dereniowski等人[13]描述了一種在快速搜索模型中用兩個(gè)或三個(gè)搜索者就足夠搜索到入侵者的圖，并證明了圖的快速搜索問(wèn)題是NP難問(wèn)題。Xue等人[14]提出完全k部圖、完全分割圖的快速搜索數(shù)的下界和上界，并確定了完全二部圖的快速搜索數(shù)。Xue[15]還給出了笛卡爾積圖的快速搜索數(shù)。

目前，在快速搜索模型的研究中僅研究了樹、Halin圖、完全k部圖、完全分割圖等的快速搜索數(shù)，還有大量不同結(jié)構(gòu)圖的快速搜索問(wèn)題沒(méi)有研究。然而，移動(dòng)機(jī)器人目標(biāo)搜索等實(shí)際問(wèn)題中的搜索區(qū)域結(jié)構(gòu)往往各不相同，當(dāng)遇到除上述已有成果外的搜索區(qū)域時(shí)，已經(jīng)提出的圖的快速搜索數(shù)及其快速搜索算法不能滿足其他區(qū)域的移動(dòng)機(jī)器人目標(biāo)搜索。因此，針對(duì)上述問(wèn)題，考慮到實(shí)際生活中存在機(jī)器人在類似籠圖結(jié)構(gòu)的區(qū)域進(jìn)行目標(biāo)搜索，根據(jù)籠圖的特定性質(zhì)，確定籠圖的快速搜索數(shù)下界，然后根據(jù)下界及搜索策略給出快速搜索數(shù)，提出一種基于籠圖的快速搜索算法。該算法對(duì)求解與籠圖類似區(qū)域的移動(dòng)機(jī)器人目標(biāo)搜索問(wèn)題具有重要意義。

1 基本概念

為了論述方便，引入以下基本概念及符號(hào)[16-18]。

1.1 圖論概念

假設(shè)G=(VG,EG)是簡(jiǎn)單無(wú)向圖，其中VG和EG分別表示圖G的頂點(diǎn)集和邊集。用uv表示連接頂點(diǎn)u和v的邊。如果uvEG，則稱u和v鄰接。若E'是EG的子集，V'是VG的子集，則稱H=(V',E')是G的子圖。如果頂點(diǎn)集S?V，那么G[S]表示圖G中由S導(dǎo)出的子圖。對(duì)于VG的子集X，稱NG(X)={u∈VG|?v∈X,uv∈EG}為X的鄰接頂點(diǎn)集。若X只有一個(gè)元素u，則用NG(u)表示u的鄰接頂點(diǎn)集。頂點(diǎn)u的鄰接頂點(diǎn)集大小，即u的鄰接頂點(diǎn)數(shù)，稱為u的度或價(jià)，用符號(hào)d(u)或r表示，顯然有d(u)=|NG(u)|=|{v∈VG|uv∈EG}|。

圖G的一條通道(walk)是指一個(gè)有限的非空序列W=v0e1v1e2v2…ekvk，其中vi∈VG(0≤i≤k)，ej=vj-1vj∈EG(1≤j≤k)。若通道W中的邊互不相同，則稱之為跡(trail)。若跡W的長(zhǎng)度為正且起點(diǎn)和終點(diǎn)相同，則稱之為閉跡(trail)。若通道W中的頂點(diǎn)互不相同，則稱之為路徑(path)。使用p=v1v2…vk表示起點(diǎn)為v1和終點(diǎn)為vk的路徑。路徑中邊的數(shù)目稱為路徑長(zhǎng)度。若一條閉跡的起點(diǎn)和內(nèi)部頂點(diǎn)互不相同，則稱之為簡(jiǎn)單回路，也稱為圈(cycle)，記為C。圈中的邊數(shù)稱為圈的長(zhǎng)度，長(zhǎng)度為k的圈稱為k-圈，記為Ck。圖中最短圈的長(zhǎng)度也稱為圍長(zhǎng)(girth)，記為g。不在圈上但連接圈中兩個(gè)頂點(diǎn)的邊稱為該圈的弦(chord)(如圖1所示)。經(jīng)過(guò)G的每條邊一次并且僅一次的路徑稱為歐拉通路。如果歐拉通路是回路(起點(diǎn)和終點(diǎn)是同一個(gè)頂點(diǎn))，則稱此回路為歐拉回路(Euler circuit)。

圖1 弦與非弦示意

1.2 快速搜索

快速搜索是一個(gè)在連通無(wú)向圖上進(jìn)行的搜索問(wèn)題，該模型由對(duì)立的搜索者和入侵者雙方組成。搜索初，圖G上沒(méi)有搜索者，但圖G包含一個(gè)隱藏在頂點(diǎn)或邊上的入侵者，故搜索開始時(shí)，假設(shè)整個(gè)圖都是污染的。在搜索過(guò)程中，搜索者和入侵者分別在圖上移動(dòng)，其中搜索者只能從一個(gè)頂點(diǎn)滑動(dòng)到與其相鄰接的頂點(diǎn)，且搜索者看不見入侵者，只能根據(jù)每一次的移動(dòng)路徑等信息，推測(cè)入侵者的位置信息；入侵者可以在任意時(shí)刻以任意快的速度沿著一條沒(méi)有搜索者的路徑滑動(dòng)，去躲避搜索者的搜索[10-12]。在該模型中，搜索者可以采取兩種動(dòng)作：占據(jù)在某一頂點(diǎn)(放置)、從某一頂點(diǎn)滑動(dòng)到相鄰頂點(diǎn)(滑動(dòng))。放置動(dòng)作須發(fā)生在滑動(dòng)動(dòng)作前。

如果一條邊uv可能包含入侵者，則稱之為污染的，否則稱之為干凈的。可以采取以下兩種動(dòng)作搜索一條邊uv，使之成為干凈的邊：

若頂點(diǎn)u包含大于等于兩個(gè)搜索者，滑動(dòng)其中一個(gè)搜索者從u沿邊uv到v；

若頂點(diǎn)u包含一個(gè)搜索者，并且uv是唯一一條與u關(guān)聯(lián)的污染的邊，則滑動(dòng)u上的搜索者沿邊uv到v。

如果確定某個(gè)頂點(diǎn)沒(méi)有關(guān)聯(lián)污染的邊，則稱該頂點(diǎn)為干凈的，否則稱它為污染的。在快速搜索模型中，圖中的每條邊只允許遍歷一次。如果某個(gè)頂點(diǎn)只包含一個(gè)搜索者，并且與該頂點(diǎn)關(guān)聯(lián)的污染的邊的數(shù)量大于該頂點(diǎn)上的搜索者的數(shù)量，則該頂點(diǎn)上的搜索者不能滑動(dòng)離開該頂點(diǎn)，否則干凈的頂點(diǎn)和邊會(huì)重新被污染。

當(dāng)所有的邊和頂點(diǎn)都被搜索過(guò)，即搜索者搜索到入侵者，搜索結(jié)束。圖的搜索策略即搜索者所移動(dòng)的路線的集合。圖G的快速搜索數(shù)，即在圖上搜捕到入侵者所需要的最小的搜索者數(shù)，用fs(G)表示。如果一個(gè)策略使用fs(G)個(gè)搜索者搜捕到入侵者，則稱此策略是搜索圖G的最優(yōu)搜索策略。

用VC表示干凈的頂點(diǎn)的集合，VZ表示污染的頂點(diǎn)的集合，EC表示干凈的邊的集合，EZ表示污染的邊的集合。snum(v)表示頂點(diǎn)v上的搜索者數(shù)量，csnum(v)表示可以在頂點(diǎn)v上滑動(dòng)到其他頂點(diǎn)的搜索者數(shù)量,EZ(v)表示與頂點(diǎn)v關(guān)聯(lián)的污染的邊的集合。

2 籠圖的快速搜索

對(duì)r=2的籠圖G2,g，由于G2,g是g-圈，只需要在圖中的某一頂點(diǎn)放置兩個(gè)搜索者，移動(dòng)其中一個(gè)沿圈Cg搜索即可搜索到目標(biāo)，易得fs(G2,g)=2。

對(duì)g=2的籠圖Gr,2，由于Gr,2只有兩個(gè)頂點(diǎn)且由r個(gè)邊連接，易得fs(Gr,2)=3。

在本節(jié)中，首先研究籠圖的性質(zhì)，利用頂點(diǎn)度和邊的關(guān)系給出籠圖G3,g(3≤g≤12)、G4,g(3≤g≤8)的快速搜索數(shù)的下界；其次，根據(jù)快速搜索數(shù)的下界給出籠圖G3,g(3≤g≤12)、G4,g(3≤g≤8)、Gr,4的快速搜索數(shù)。

2.1 快速搜索數(shù)的下界

定理1：對(duì)r=3,3≤g≤12籠圖G3,g，有

定理2：對(duì)r=4,3≤g≤8的籠圖G4,g，有：

類似定理1的證明可證，不再贅述。

2.2 籠圖的快速搜索數(shù)

下面給出r=3，3≤g≤12、r=4，3≤g≤8以及g=4的籠圖的快速搜索數(shù)。

引理1：對(duì)r=3,g=3的籠圖，有fs(G3,3)=4。

證明：根據(jù)定理1得，fs(G3,3)≥4。下面采用一個(gè)4個(gè)搜索者的策略進(jìn)行搜索(G3,3見圖2)。

首先在頂點(diǎn)v1放置搜索者γ1、γ2、γ3，在頂點(diǎn)v4放置搜索者γ4，然后進(jìn)行以下移動(dòng)動(dòng)作：

(1)移動(dòng)γ1從頂點(diǎn)v1沿邊v1v4到頂點(diǎn)v4，移動(dòng)γ2從頂點(diǎn)v1沿邊v1v3到頂點(diǎn)v3，移動(dòng)γ3從頂點(diǎn)v1沿邊v1v2到頂點(diǎn)v2。

(2)移動(dòng)γ4從頂點(diǎn)v4沿路徑v4v3v2v4到頂點(diǎn)v4。

此時(shí)，G被搜索干凈，因此對(duì)于(3,3)-籠圖，有fs(G3,3)=4，引理1成立。

圖2 (3,3)籠

引理2：對(duì)r=3，g=4的籠圖，有fs(G3,4)=5。

引理3：對(duì)r=3，g=5的籠圖，有fs(G3,5)=7。

引理4：對(duì)r=3，g=6的籠圖，有fs(G3,6)=9。

引理5：對(duì)r=3，g=7的籠圖，有fs(G3,7)=14。

引理6：對(duì)r=3，g=8的籠圖，有fs(G3,8)=17。

引理7：對(duì)r=3，g=9的籠圖，有fs(G3,9)=31。

引理8：對(duì)r=3，g=10的籠圖，有fs(G3,10)=37。

引理9：對(duì)r=3，g=11的籠圖，有fs(G3,11)=58。

引理10：對(duì)r=3，g=12的籠圖，有fs(G3,12)=65。

證明類似，不再逐一證明。

下面給出當(dāng)r=3，3≤g≤12時(shí)，籠圖的快速搜索數(shù)的定理。

根據(jù)定理1以及引理1到引理10可證，不再贅述。

引理11：對(duì)r=4,g=3的籠圖，有fs(G4,3)=5。

證明：根據(jù)定理2得，fs(G4,3)≥5。下面采用一個(gè)5個(gè)搜索者的策略進(jìn)行搜索(G4,3見圖3)。首先在頂點(diǎn)v1放置搜索者γ1、γ2、γ3。γ4在頂點(diǎn)v5放置搜索者γ5，然后進(jìn)行以下移動(dòng)動(dòng)作：

(1)移動(dòng)γ1從頂點(diǎn)v1沿邊v1v5到頂點(diǎn)v5，移動(dòng)γ2從頂點(diǎn)v1沿邊v1v4到頂點(diǎn)v4，移動(dòng)γ3從頂點(diǎn)v1沿邊v1v3到頂點(diǎn)v3，移動(dòng)γ4從頂點(diǎn)v1沿邊v1v2到頂點(diǎn)v2。

(2)移動(dòng)γ5從頂點(diǎn)v5沿路徑v5v4v3v2v5到頂點(diǎn)v5；

(3)移動(dòng)γ1從頂點(diǎn)v5沿邊v5v3到頂點(diǎn)v3。

(4)移動(dòng)γ4從頂點(diǎn)v2沿邊v2v4到頂點(diǎn)v4。

此時(shí)，圖被搜索干凈，因此對(duì)于(4,3)-籠圖，引理成立。

圖3 (4,3)籠

引理12：對(duì)r=4,g=4的籠圖，有fs(G4,4)=7。

引理13：對(duì)r=4,g=5的籠圖，有fs(G4,5)=12。

引理14：對(duì)r=4,g=6的籠圖，有fs(G4,6)=15。

引理15：對(duì)r=4,g=7的籠圖，有fs(G4,7)=31。

引理16：對(duì)r=4,g=8的籠圖，有fs(G4,8)=37。

上述引理證明類似，不再逐一列出。

下面給出當(dāng)r=4，3≤g≤8時(shí)，籠圖的快速搜索數(shù)的定理。

定理4：對(duì)任意r=4,3≤g≤8的籠圖，有：

根據(jù)定理2以及引理11到引理16可證，不再贅述。

定理5：對(duì)于r≥3，g=4的籠圖，有fs(Gr,4)=2r-1。

證明：對(duì)r≥3，g=4的籠圖，給出以下快速搜索策略。

(1)在頂點(diǎn)v1放置r個(gè)搜索者γ1,γ2,…,γr，在頂點(diǎn)v|VG|放置r-2個(gè)搜索者γr+1,γr+2,…,γ2r-2，在頂點(diǎn)v2r-1放置搜索者γ2r-1。

(2)對(duì)i從1到r，滑動(dòng)γi從頂點(diǎn)v1到頂點(diǎn)vj，其中vj∈NH(vi)，1≤j≤|VGr,4|。

(3)滑動(dòng)頂點(diǎn)v|VG|上所有的搜索者從v|VG|分別到其每一個(gè)鄰接點(diǎn)vj，其中vj∈NH(v|VG|)。

(4)當(dāng)r為奇數(shù)時(shí)，滑動(dòng)搜索者γ2r-1從頂點(diǎn)v2r-1沿歐拉回路搜索H；當(dāng)r為偶數(shù)時(shí)，滑動(dòng)搜索者γ2r-1從頂點(diǎn)v2r-1沿H中的非弦邊到頂點(diǎn)v2r-1，然后滑動(dòng)搜索者γ2r-1從頂點(diǎn)v2r-1沿其一條弦到其鄰接點(diǎn)搜索直到該搜索者不能再滑動(dòng)。

(5)若此時(shí)H仍有污染的邊：

若H中存在vp滿足|EZ(vp)|=1，則滑動(dòng)vp上的搜索者搜索與其關(guān)聯(lián)的污染的邊。若仍存在污染的邊，則繼續(xù)滑動(dòng)其他能滑動(dòng)的搜索者搜索H。

2.3 籠圖的快速搜索算法

下面給出搜索籠圖的快速搜索算法，輸入為籠圖Gr,g，輸出為放置搜索者的頂點(diǎn)集V和移動(dòng)路徑序列S。算法大致思路為：(1)在圖中某一頂點(diǎn)v放置搜索者，并分別移動(dòng)該頂點(diǎn)上的搜索者到其各個(gè)鄰接點(diǎn)；(2)此時(shí)若有滿足1≤|EZ(u)|≤snum(u)的頂點(diǎn)u，則滑動(dòng)u上的搜索者沿污染的邊搜索；(3)否則，從頂點(diǎn)v的一個(gè)非弦鄰接點(diǎn)vi依次沿圈C|VGr,g|開始(當(dāng)r=3,g=5時(shí)，從頂點(diǎn)v的任意一個(gè)鄰接點(diǎn)開始)，若|EZ(vi)|≥1且csnum(vi)<1，則在vi上放置搜索者，使其滿足|EZ(vi)|≤snum(vi)，然后滑動(dòng)vi上搜索者搜索vi的鄰接點(diǎn)；(4)令vi的一個(gè)非弦鄰接點(diǎn)為新的vi(當(dāng)r=3,g=5時(shí)，令vi的任意一個(gè)鄰接點(diǎn)為新的vi),重復(fù)步驟2～步驟4，直到每個(gè)頂點(diǎn)都沒(méi)有污染的邊，即圖完全干凈。下面給出具體搜索算法，算法SC為搜索籠圖G3,g(3≤g≤12)、G4,g(3≤g≤8)的搜索算法。

算法SC：

1.在vj放置搜索者，分別移動(dòng)vj上的搜索者到其各個(gè)鄰接點(diǎn)

2.ifr=3,g=5 then

3.選擇vj的一個(gè)鄰接點(diǎn)vp，令i←p

4.else

5.選擇vj的一個(gè)鄰接點(diǎn)vncj，令i←ncj

6.end if

7.whileEZ≠? do

8.while除了vi有滿足1≤|EZ(u)|≤snum(u)的頂點(diǎn)udo

9.滑動(dòng)u上的搜索者沿污染的邊搜索

10.end while

11.while除了vi所有的臟點(diǎn)滿足csnum(vi)<1 and|EZ(vi)|≥1 do

12.ifvi滿足snum(vi)≤1 and|EZ(vi)|≥1 then

13.在vi上放置|EZ(vi)|-1個(gè)搜索者,分別移動(dòng)vi的搜索者到其鄰接點(diǎn)

14.end if

15.ifvi滿足snum(vi)≥2 and|EZ(vi)|≥1 then

16.分別移動(dòng)vi的搜索者到其鄰接點(diǎn)

17.end if

18.ifr=3,g=5 then

19.令vi的一個(gè)鄰接點(diǎn)為新的vi

20.else

21.令vi的一個(gè)非弦鄰接點(diǎn)為新的vi

22.end if

23.end while

24.end while

3 實(shí)例分析

為保證籠圖的快速搜索算法的準(zhǔn)確性，本節(jié)將對(duì)2.3節(jié)中的算法SC進(jìn)行實(shí)驗(yàn)驗(yàn)證。實(shí)驗(yàn)的測(cè)試?yán)龍D為(3,5)籠、(3,6)籠、(4,4)籠。具體數(shù)據(jù)見表1。其中|VG|為頂點(diǎn)數(shù)，|EG|為邊數(shù)，fs(G)為快速搜索數(shù)。

表1 實(shí)驗(yàn)測(cè)試?yán)龍D數(shù)據(jù)

3.1 算法SC在籠圖G3,5上的實(shí)驗(yàn)

根據(jù)引理3可知，搜索籠圖G3,5需要7個(gè)搜索者。實(shí)驗(yàn)過(guò)程如下：在第0輪，在頂點(diǎn)v1放置三個(gè)搜索者，第1輪，移動(dòng)頂點(diǎn)v1的搜索者去搜索；第2輪，在頂點(diǎn)v5放置一個(gè)搜索者，移動(dòng)頂點(diǎn)v5上的搜索者去搜索；第3輪，在頂點(diǎn)v4放置一個(gè)搜索者，移動(dòng)v4上的搜索者去搜索；第4輪，在頂點(diǎn)v3放置一個(gè)搜索者，移動(dòng)v3上的搜索者去搜索；第5輪，移動(dòng)v2上的搜索者去搜索；第6輪，在頂點(diǎn)v7放置一個(gè)搜索者，移動(dòng)v7的搜索者去搜索。下面由表2給出搜索過(guò)程中搜索者的位置、臟邊集合、臟點(diǎn)集合的變化。其中i為移動(dòng)的輪次，Vi為搜索者每輪所在位置集合，EZ為臟邊集合(搜索者的移動(dòng)路徑)，VZ為臟點(diǎn)集合，且EZ、VZ隨輪次i變化。

表2 搜索過(guò)程中G3,5臟點(diǎn)集與臟邊集隨搜索輪次的變化

圖4所示為搜索過(guò)程中，臟點(diǎn)和臟邊的變化過(guò)程及實(shí)驗(yàn)結(jié)果。其中三角形頂點(diǎn)表示已經(jīng)搜索過(guò)的頂點(diǎn)，虛線表示已經(jīng)搜索過(guò)的邊，圓形頂點(diǎn)表示未搜索的頂點(diǎn)，實(shí)線邊表示未搜索的邊。

圖4 (3,5)籠的部分搜索過(guò)程示意

通過(guò)表2和圖4可以看出，實(shí)驗(yàn)經(jīng)6輪搜索后，臟點(diǎn)集合和臟邊集合為空集，圖4(c)為最后結(jié)果，可以看出G3,5中的所有頂點(diǎn)皆為三角形、所有邊皆為虛線，即G3,5中的臟點(diǎn)和臟邊全部被搜索完。

3.2 算法SC在籠圖G3,6上的實(shí)驗(yàn)

根據(jù)引理4可知，搜索籠圖G3,6需要9個(gè)搜索者。實(shí)驗(yàn)過(guò)程如下：在第0輪，在頂點(diǎn)v1放置三個(gè)搜索者；第1輪，移動(dòng)頂點(diǎn)v1的搜索者去搜索；第2輪，在頂點(diǎn)v14放置一個(gè)搜索者，移動(dòng)頂點(diǎn)v14上的搜索者去搜索；第3輪，在頂點(diǎn)v13放置一個(gè)搜索者，移動(dòng)v13上的搜索者去搜索；第4輪，在頂點(diǎn)v12放置一個(gè)搜索者，移動(dòng)v12上的搜索者去搜索；第5輪，在頂點(diǎn)v11放置一個(gè)搜索者，移動(dòng)v11上的搜索者去搜索；第6輪，移動(dòng)v10的搜索者去搜索；第7輪，在頂點(diǎn)v9放置一個(gè)搜索者，移動(dòng)v9的搜索者去搜索；第8輪，移動(dòng)v8的搜索者去搜索；第9輪，在頂點(diǎn)v7放置一個(gè)搜索者，移動(dòng)v7的搜索者去搜索。下面由表3給出搜索過(guò)程中搜索者的位置、臟邊集合、臟點(diǎn)集合的變化。其中i為移動(dòng)的輪次，Vi為搜索者所在位置集合，EZ為臟邊集合(搜索者的移動(dòng)路徑)，VZ為臟點(diǎn)集合，且EZ、VZ隨輪次i變化。

表3 搜索過(guò)程中G3,6的臟點(diǎn)集與臟邊集隨搜索輪次的變化

圖5所示為搜索過(guò)程中，臟點(diǎn)和臟邊的變化過(guò)程及實(shí)驗(yàn)結(jié)果圖。其中圖中三角形頂點(diǎn)表示已經(jīng)搜索過(guò)的頂點(diǎn)、虛線表示已經(jīng)搜索過(guò)的邊，圓形頂點(diǎn)表示未搜索的頂點(diǎn)、實(shí)線邊表示未搜索的邊。

(a)i=0 (b)i=1 (c)i=9

通過(guò)表3和圖5可以看出，該實(shí)驗(yàn)經(jīng)9輪搜索后，臟點(diǎn)集合和臟邊集合為空集，其中圖5(c)為最后結(jié)果圖，從圖5可以看出G3,6中所有頂點(diǎn)皆為三角形、所有邊皆為虛線，即G3,6中的臟點(diǎn)和臟邊全部被搜索完。

3.3 算法SC在籠圖G4,4上的實(shí)驗(yàn)

根據(jù)引理12可知，搜索籠圖G4,4需要7個(gè)搜索者。實(shí)驗(yàn)過(guò)程如下：在第0輪，在頂點(diǎn)v1放置三個(gè)搜索者；第1輪，移動(dòng)頂點(diǎn)v1的搜索者去搜索；第2輪，在頂點(diǎn)v8放置2個(gè)搜索者，移動(dòng)頂點(diǎn)v8上的搜索者去搜索；第3輪，在頂點(diǎn)v7放置一個(gè)搜索者，移動(dòng)v7上的搜索者去搜索；第4輪，移動(dòng)v6上的搜索者去搜索；第5輪，移動(dòng)v5上的搜索者去搜索。下面由表4給出搜索過(guò)程中搜索者的位置、臟邊集合、臟點(diǎn)集合的變化。其中i為移動(dòng)的輪次，Vi為搜索者所在位置集合，EZ為臟邊集合(搜索者的移動(dòng)路徑)，VZ為臟點(diǎn)集合，且EZ、VZ隨輪次i變化。

表4 搜索過(guò)程中G4,4的臟點(diǎn)集與臟邊集隨搜索輪次的變化

圖6所示為搜索過(guò)程中，臟點(diǎn)和臟邊的變化過(guò)程及實(shí)驗(yàn)結(jié)果圖。其中三角形頂點(diǎn)表示已經(jīng)搜索過(guò)的頂點(diǎn)，虛線表示已經(jīng)搜索過(guò)的邊，圓形頂點(diǎn)表示未搜索的頂點(diǎn)，實(shí)線邊表示未搜索的邊。

(a)i=0 (b)i=1 (c)i=5

通過(guò)表4和圖6可以看出，該實(shí)驗(yàn)經(jīng)5輪搜索后，臟點(diǎn)集合和臟邊集合皆為空集，其中圖6(c)為最后結(jié)果，可見籠圖G4,4中所有頂點(diǎn)皆為三角形、所有邊皆為虛線，即圖中所有頂點(diǎn)和邊都被搜索過(guò)，完成對(duì)籠圖G4,4的搜索。

3.4 總結(jié)與分析

在上述三個(gè)例圖實(shí)驗(yàn)中，根據(jù)2.2節(jié)給出的搜索數(shù)引理，利用算法SC根據(jù)頂點(diǎn)關(guān)聯(lián)的污染的邊數(shù)放置搜索者(機(jī)器人)的個(gè)數(shù)，又在每條邊搜索的過(guò)程中遵循只搜索一次的規(guī)則完成在整個(gè)區(qū)域?qū)δ繕?biāo)的搜索。從表2、表3、表4可以看出臟邊一直在減少，且被搜索過(guò)的臟邊不會(huì)再次成為臟邊，即搜索者對(duì)每條邊只搜索了一次，減少了搜索次數(shù)；從圖4(c)、圖5(c)、圖6(c)可見，圖中所有頂點(diǎn)皆為三角形、所有邊皆為虛線，即都已被搜索者搜索過(guò)，有效地完成了對(duì)籠圖G3,5、G3,6、G4,4的搜索。因此，實(shí)驗(yàn)表明算法SC在經(jīng)有限輪次后使籠圖中的臟點(diǎn)和臟邊集合皆為空集，有效地完成了對(duì)整個(gè)籠圖區(qū)域的搜索。

4 結(jié)束語(yǔ)

針對(duì)籠圖區(qū)域的移動(dòng)機(jī)器人目標(biāo)搜索問(wèn)題，對(duì)籠圖快速搜索建模，通過(guò)對(duì)籠圖性質(zhì)的探索得到籠圖的快速搜索數(shù)的下界及籠圖的快速搜索數(shù)。提出一種基于籠圖的快速搜索算法，用于解決籠圖形狀區(qū)域的移動(dòng)機(jī)器人目標(biāo)搜索問(wèn)題。在快速搜索模型下對(duì)籠圖的頂點(diǎn)和邊進(jìn)行搜索，經(jīng)在三個(gè)籠圖實(shí)例上的模擬驗(yàn)證，該算法可以有效地使機(jī)器人在不知道目標(biāo)具體位置的情況下，逐步搜索到目標(biāo)。該研究為基于籠圖的移動(dòng)機(jī)器人目標(biāo)搜索問(wèn)題的求解提供了一種新思路和可行的搜索策略,但仍需進(jìn)一步在大規(guī)模問(wèn)題上研究。