基于哈密頓通路解決的地面搜索模型

1、基于哈密頓通路解決的地面搜索模型作者：董愛(ài)卿（女）計(jì)算機(jī)應(yīng)用技術(shù)08-4鐘 瑞 計(jì)算機(jī)應(yīng)用技術(shù)08-3崔 濤 計(jì)算機(jī)應(yīng)用技術(shù)08-3 摘要本文針對(duì)地面搜索問(wèn)題關(guān)于隊(duì)員安排和路線選擇問(wèn)題，建立了優(yōu)化模型。在確保地面搜索不遺漏以及路線盡量不重復(fù)情況下，使得搜索的時(shí)間盡量少。具體結(jié)果如下：?jiǎn)栴}一的求解中，我們模擬了三種方案。方案1，為了在搜索到人員后能盡快聯(lián)系到組長(zhǎng)，我們認(rèn)為20個(gè)人應(yīng)該并排走，按照s的路線搜索完，雖然避免了地面搜索不遺漏的情況，但卻走了重復(fù)的路線（具體路線見(jiàn)圖1），并且最終求出，搜索任務(wù)完成后需要50.01小時(shí)。方案2，為了確保不走重復(fù)路線，我們又想到了哈密頓通路解法（具體路線見(jiàn)圖

2、2），這樣就解決了路線重復(fù)問(wèn)題，但在拐角處會(huì)浪費(fèi)很多時(shí)間，這種方案完成搜索任務(wù)需要50.28小時(shí)。方案3, 每一種方案都避免不了過(guò)兩種拐角所浪費(fèi)的時(shí)間和隊(duì)伍分散與集合所需要的時(shí)間，第一種拐角是90度彎的拐角，第二種拐角是0度或180度的拐角，第一種拐角處需要10.8分鐘整理隊(duì)型，第二種拐角處需要11.1分鐘平移整個(gè)隊(duì)伍；而隊(duì)伍分散與集合所需時(shí)間為10.6分鐘。因此，在方案2的問(wèn)題上我們進(jìn)行了優(yōu)化，即盡可能大的削減拐角數(shù)量，我們有方案2上的18個(gè)拐角削減到15個(gè)拐角，這樣，搜索任務(wù)完成需要49.80小時(shí)。由以上可知，我們無(wú)法在48小時(shí)內(nèi)完成搜索任務(wù)，我們需要增加人手。首先需要解決一個(gè)小應(yīng)用題：2

3、0個(gè)人完成一任務(wù)耗時(shí)49.8小時(shí)，那么，在48小時(shí)內(nèi)完成同樣的任務(wù)至少需要多少人？答案是49.8*20/48=20.75即至少要21人。同理可證，我們需要增加1位搜索人員。問(wèn)題二的求解中，根據(jù)問(wèn)題一的優(yōu)化方案，我們繼續(xù)用哈密頓通路的方法解決。為了便于路線的安排，我們確定了三個(gè)小組的人數(shù)，即20,20,10人。暫且按順序分別叫做小組1，小組2，小組3。為了使任務(wù)平均分配，我們認(rèn)為小組1應(yīng)搜索此塊矩形的目標(biāo)區(qū)域，小組2應(yīng)搜索此塊矩形的目標(biāo)區(qū)域，小組3應(yīng)搜索此塊矩形的目標(biāo)區(qū)域。也就將此塊矩形分成了三塊。我們根據(jù)哈密度通路原則確定三個(gè)小組的通路后，三個(gè)小組所花費(fèi)的時(shí)間分別為20.16小時(shí)、20.16小

4、時(shí)、20.08小時(shí)，從而搜索完整個(gè)區(qū)域所需的時(shí)間是 20.08小時(shí)。關(guān)鍵詞： 哈密頓通路 最短路徑 彎道策略 圖論一、 問(wèn)題重復(fù)與分析·5.12汶川大地震使震區(qū)地面交通和通訊系統(tǒng)嚴(yán)重癱瘓。救災(zāi)指揮部緊急派出多支小分隊(duì)，到各個(gè)指定區(qū)域執(zhí)行搜索任務(wù)，以確定需要救助的人員的準(zhǔn)確位置。在其它場(chǎng)合也常有類(lèi)似的搜索任務(wù)。在這種緊急情況下需要解決的重要問(wèn)題之一是：制定搜索隊(duì)伍的行進(jìn)路線，對(duì)預(yù)定區(qū)域進(jìn)行快速的全面搜索。通常，每個(gè)搜索人員都帶有GPS定位儀、步話機(jī)以及食物和生活用品等裝備。隊(duì)伍中還有一定數(shù)量的衛(wèi)星電話。GPS可以讓搜索人員知道自己的方位。步話機(jī)可以相互進(jìn)行通訊。衛(wèi)星電話用來(lái)向指揮部報(bào)告

5、搜索情況。下面是一個(gè)簡(jiǎn)化的搜索問(wèn)題。有一個(gè)平地矩形目標(biāo)區(qū)域，大小為11200米×7200米，需要進(jìn)行全境搜索。假設(shè)：出發(fā)點(diǎn)在區(qū)域中心；搜索完成后需要進(jìn)行集結(jié)，集結(jié)點(diǎn)（結(jié)束點(diǎn)）在左側(cè)短邊中點(diǎn)；每個(gè)人搜索時(shí)的可探測(cè)半徑為20米，搜索時(shí)平均行進(jìn)速度為0.6米/秒；不需搜索而只是行進(jìn)時(shí),平均速度為1.2米/秒。每個(gè)人帶有GPS定位儀、步話機(jī)，步話機(jī)通訊半徑為1000米。搜索隊(duì)伍若干人為一組,有一個(gè)組長(zhǎng)，組長(zhǎng)還擁有衛(wèi)星電話。每個(gè)人搜索到目標(biāo)，需要用步話機(jī)及時(shí)向組長(zhǎng)報(bào)告，組長(zhǎng)用衛(wèi)星電話向指揮部報(bào)告搜索的最新結(jié)果。現(xiàn)在有如下問(wèn)題需要解決：1假定有一支20人一組的搜索隊(duì)伍, 擁有1臺(tái)衛(wèi)星電話。請(qǐng)?jiān)O(shè)計(jì)

6、一種你認(rèn)為耗時(shí)最短的搜索方式。按照你的方式，搜索完整個(gè)區(qū)域的時(shí)間是多少? 能否在48小時(shí)內(nèi)完成搜索任務(wù)? 如果不能完成，需要增加到多少人才可以完成。2為了加快速度，搜索隊(duì)伍有50人，擁有3臺(tái)衛(wèi)星電話，分成3組進(jìn)行搜索。每組可獨(dú)立將搜索情況報(bào)告給指揮部門(mén)。請(qǐng)?jiān)O(shè)計(jì)一種你認(rèn)為耗時(shí)最短的搜索方式。按照你的搜索方式, 搜索完整個(gè)區(qū)域的時(shí)間是多少?該問(wèn)題來(lái)源于實(shí)際，我們認(rèn)為合理的方案需要考慮如下因素：1盡可能少走重復(fù)路線2由于是搜救傷員，應(yīng)該把所有區(qū)域搜索一遍3盡可能讓每組和每位搜救人員的工作量相等4過(guò)拐角時(shí)，搜索人員行走路程盡量相同，盡可能少走問(wèn)題分析和擬解決思路：從題目要求出發(fā)，主要解決以下兩個(gè)大問(wèn)題

7、：1一支20人的搜索隊(duì)伍, 擁有1臺(tái)衛(wèi)星電話，為了保證他們及時(shí)向組長(zhǎng)報(bào)告情況，他們要同時(shí)進(jìn)行搜索任務(wù)；為了不重復(fù)搜索某一區(qū)域，且任務(wù)同時(shí)進(jìn)行，搜救人員應(yīng)一字排開(kāi)，組長(zhǎng)在隊(duì)伍中間；確定區(qū)域搜索通道，確定搜索路線，計(jì)算搜索時(shí)間，若所用時(shí)間大于48小時(shí)，還要確定需要增加多少人才能在48小時(shí)以內(nèi)完成此任務(wù)。250人分成三組，確定每組人員的數(shù)量，確定確定區(qū)域搜索通道，根據(jù)每組人員比例分配搜索任務(wù)，確定搜索路線，計(jì)算出每組所用時(shí)間。二、模型假設(shè)1. 搜索可一直進(jìn)行，中途不會(huì)因任何情況而停止；2. 不考慮搜索目標(biāo)區(qū)域是否平地、儀器的準(zhǔn)確度，人員的個(gè)人因素等；3. 所給的數(shù)據(jù)，如搜索的平均速度都準(zhǔn)確，不影響搜

8、索所需的時(shí)間；4. 搜索的區(qū)域盲點(diǎn)搜索沒(méi)有忽略；5. 定位儀與通信工具一直正常使用；6. 無(wú)論什么天氣，無(wú)論白天黑夜，搜索半徑保持20米；7. 先拐完彎并站好陣型的隊(duì)員要等最后一個(gè)站好陣型的隊(duì)員后，同時(shí)搜索；三、數(shù)據(jù)分析與建模：?jiǎn)栴}一問(wèn)題一是求解問(wèn)題二的前提，首先應(yīng)該確保搜索的范圍包括全部的矩形區(qū)域，其次盡量不要走重復(fù)路線，走重復(fù)路線很費(fèi)時(shí)間。因?yàn)橹挥幸粋€(gè)衛(wèi)星電話，所以組長(zhǎng)要與隊(duì)員同時(shí)一塊行走。隊(duì)伍一字排開(kāi)。搜索的寬度為800米，長(zhǎng)和寬正好是800的整數(shù)倍。這樣我們就確定了，基本的路線。隊(duì)伍最后留一個(gè)通道到達(dá)左邊中點(diǎn)處，由一個(gè)方向搜索到距離盡頭800米處折回。模型一（圖一）隊(duì)伍行進(jìn)(綠色線的時(shí)

9、間tt=5546.9271.2+876.581.2=5352.84s這個(gè)人搜索的時(shí)間為tt=1498000.6=168000s此人經(jīng)過(guò)拐角的時(shí)間tt=108001.2=6666.67s從而得出搜索完畢后所需總時(shí)間為180019.5067s,即50.01小時(shí)不過(guò)這樣，需要走重復(fù)的路線。為了減少重復(fù)搜索所費(fèi)的時(shí)間，我們認(rèn)為路線不能左右方向來(lái)回搜索，所以經(jīng)過(guò)進(jìn)一步修改后，我們?cè)O(shè)計(jì)出了另一種方案。即模型2 （圖二）這個(gè)人搜索的時(shí)間為tt=1498000.6=168000s拐彎所耗費(fèi)的時(shí)間為tt=178001.2+7801.2=11983.333s集合與分散的時(shí)間為tt=3801.2+1.2=1042.

10、666s模型二完成任務(wù)所花費(fèi)的總時(shí)間為181025.0s，即50.28小時(shí)模型二中我們發(fā)現(xiàn)在拐角處，隊(duì)伍分散與集合大概需要11分鐘，而且此模型有18個(gè)拐角，隊(duì)伍在拐角處就要浪費(fèi)198分鐘。我們對(duì)模型二進(jìn)行了優(yōu)化，盡量減少拐角，我們?cè)O(shè)計(jì)了模型三，如下圖。（圖三）搜索時(shí)間為tt=1498000.6=168000s隊(duì)伍通過(guò)拐角所浪費(fèi)的時(shí)間為tt=148001.2+78021.2=10633.333s集合與分散所需時(shí)間為tt=3801.2+3801.2=633.333s完成任務(wù)所需的總時(shí)間為179266.666s，即49.796小時(shí)。這樣模型三少了2個(gè)拐角，即省了33分鐘。問(wèn)題2在問(wèn)題1的前提下，主要

11、考慮盡量縮短搜索時(shí)間。首先，我們考慮了如何將50個(gè)人分到三個(gè)小組里，如果小組中的人數(shù)不是10的整數(shù)倍，隊(duì)伍一字排開(kāi)后的寬度將不會(huì)被7200和11600整除， 經(jīng)過(guò)商討后，我們確定了三個(gè)小組的人數(shù)分別為20,20,10。這樣就避免了，人員浪費(fèi)問(wèn)題。根據(jù)人數(shù)，我們認(rèn)為，三個(gè)小組的搜索范圍，分別為矩形面積的， 。為了降低問(wèn)題的難度，我們假設(shè)組員為20人的兩個(gè)小組所走路線對(duì)稱(chēng)，所以我們擬出模型一（圖四）小組1和小組2完成任務(wù)所需要的時(shí)間為tt=50.58000.6+38001.2+7801.2+7801.2+11801.2=70966.67s即19.71小時(shí)。小組3完成任務(wù)所需要的時(shí)間為tt=2544

12、000.6+144001.2+33801.2+3801.2+1.2=73638.29s，即20.455小時(shí)三個(gè)小組完成任務(wù)所需的時(shí)間分別為19.71小時(shí)，19.71小時(shí)，20.455小時(shí)。即整個(gè)任務(wù)完成所需時(shí)間為20.455小時(shí)。先完成任務(wù)的隊(duì)員需要等后來(lái)的隊(duì)員44.7分鐘。說(shuō)明10人一組的小組搜索任務(wù)較重，我們想到可以由先前兩個(gè)小組分擔(dān)一批任務(wù)，這樣既縮短了等待時(shí)間，也縮短了整個(gè)任務(wù)完成的時(shí)間，于是我們優(yōu)化設(shè)計(jì)出了模型二。（圖五）小組1和小組2完成任務(wù)需要的時(shí)間為tt=518000.6+7801.2+7801.2+38001.2+27801.2=72600s即20.16小時(shí)。小組3完成任務(wù)需

13、要的時(shí)間為tt=2444000.6+144001.2+33801.2+3801.2+1.2+21.2=72304.96s,即20.08小時(shí)模型二中10人小組比模型一10人小組少用了大約22.5分鐘，比20人小組的兩個(gè)小組多用了大約27分鐘。從而完成整個(gè)任務(wù)所需要的時(shí)間縮短到20.08小時(shí)。四，模型的評(píng)價(jià)與改進(jìn)1模型的評(píng)價(jià)模型的優(yōu)點(diǎn)由簡(jiǎn)單到復(fù)雜,但重復(fù)的越來(lái)越少,完成搜索任務(wù)所用時(shí)間越來(lái)越少；能夠保證通訊暢通。該模型避免了隊(duì)員盲目搜索，遇到突發(fā)事情，可以在第一時(shí)間通知到指揮部，也比較好統(tǒng)一指揮，特別適合于大面積的搜索范圍。路線規(guī)則，覆蓋了全部的搜索區(qū)域，隊(duì)員分散與集合速度較快，模型的缺點(diǎn)方案拐彎較多,拐彎處耗時(shí)較多，搜索死板，隊(duì)伍成員搜索耗時(shí)不等，在分散，集合，經(jīng)過(guò)拐角時(shí)，先完成的隊(duì)員需要等待后完成的隊(duì)員，拖緩了任務(wù)進(jìn)程，問(wèn)題二中的20人小組與10人小組無(wú)法在同一時(shí)刻完成所分配的任務(wù)。2模型的推廣以上幾種方案的思想都可以地面搜索領(lǐng)域應(yīng)用.3模型