【正文】 題中給出了12個多邊形障礙物的區(qū)域，故我們根據(jù)圖中的約束條件利用Matlab(程序見附錄一)將障礙物擴充為如圖9：圖9即形成一個新的障礙區(qū)域，先求出所有的切線，包括出發(fā)點和目標(biāo)點到所有圓弧的切線以及所有圓弧與圓弧之間的切線，給這些定點賦一個等于切線長度的權(quán)值，如果某兩條切線有一個公切圓弧，則代表這兩條曲線的頂點是一條直線的兩個端點，邊上的權(quán)值等于這兩條切線之間的劣弧長度。對于最短路徑的求解，有以下步驟：1）畫出出發(fā)點和目標(biāo)點和各個圓弧的切線，以及圓弧與圓弧之間的切線，但是切線有可能經(jīng)過障礙物的內(nèi)部或危險區(qū)域，也可能出現(xiàn)切線重復(fù)的狀況，既有很多不合理的切線，再根據(jù)約束條件我們對模型做了以下修正：l 檢驗切線兩個端點是否在障礙物內(nèi)部。除上述三個指標(biāo)外還需考慮一種特殊情況，即公切線在一個圓弧上只有一個切點(如圖10)因此我們作如下規(guī)定:如果某條切線與某段圓弧相切，且切點不在切線的端點上，則該切線為不合理。為邊的權(quán)值，即第條弧的長度。利用Dijkstra算法對其求解出最短路徑。模型的結(jié)果通過編程求解得出最短路徑的線路坐標(biāo)和最短路徑： 表一 各線路的最短路徑路徑最短路徑的坐標(biāo)線路最短路徑的長度(個單位)OAOBOCOABCO其中：OA:圓弧圓心坐標(biāo)為（80,210）。OC:圓弧圓心坐標(biāo)依次為（230,60），（410,100），（500,200），（720,520），（720,600）。各路徑最短線路圖如下： 圖11 OA的最短路徑 圖12 OB的最短路徑 圖13 OC的最短路徑 圖14 OABCO最短路徑圖模型分析由第一問的模型可知，當(dāng)轉(zhuǎn)彎圓弧的圓心在頂點時，行走路徑越靠近兩點連線，且圓弧半徑越小路徑越短，所花的時間也就越少；但根據(jù)最大轉(zhuǎn)彎速度為，其中是轉(zhuǎn)彎半徑，圓弧半徑越小轉(zhuǎn)彎的速度也就越慢，所花的時間又更長，基于這兩者結(jié)合，將轉(zhuǎn)彎路徑的圓弧與問題一中O點到A點圓弧相內(nèi)切，如圖15所示 圖15設(shè)圓弧的圓心為，問題一中的頂點圓心為（80,210），,。模型的建立與求解機器人從O點到A點，由第一問得最短路徑，設(shè)第一段線段所用時間為,第二段圓弧段所用時間為，第三段線段所用時間為,為兩圓心的距離，那么目標(biāo)函數(shù)可以表示為：利用Matlab編程求得總時間最小為秒，其中轉(zhuǎn)彎處圓弧圓心坐標(biāo)為，圓弧兩切點的坐標(biāo)分別為（,）、（,）。2. 問題一中利用權(quán)值網(wǎng)絡(luò)對問題的整體把握，有全局包攬局部的效果，避免了只考慮小部分的情況。模型的缺點：1. 此模型利用整體把握的考慮，但由于它遍歷計算的節(jié)點很多，計算具體數(shù)值時可能存在一定的誤差，效率也會更低。七、參考文獻[1]姜啟源，數(shù)學(xué)模型，北京，高等教育出版社 ，2003[2] 尤承業(yè)，解析幾何，北京，北京大學(xué)出版社，2004[3]周培德，計算幾何—算法與設(shè)計，北京清華大學(xué)出版社，2005[4]王文波，數(shù)學(xué)建模及其基礎(chǔ)知識詳解，武漢，武漢大學(xué)出版社，2005[5]祝紅芳 王從慶，機器人路徑規(guī)劃的元胞自動機算法，江西，江西科學(xué)，第27卷第1期，3640,[6]龔劬，圖論與網(wǎng)絡(luò)最優(yōu)化算法，重慶，重慶大學(xué)出版社，2009[7]李明哲,圖論及其算法,北京，機械工業(yè)出版社，2010
[8]王桂平,圖論算法理論、實現(xiàn)及運用，北京，北京大學(xué)出版社，2011附 錄附錄一路徑圖的Matlab程序:運行的約束條件：open text(0,0,39。,39。,12)。A39。fontsize39。R=10。P1=[ ]。line([0 ],[0 ,],39。,2)。an2=angle(plex(P2(1)O(1),P2(2)O(2)))。endan=linspace(an1,an2,50)。LineWidth39。 dot1=[,]。line([dot1(1) dot2(1)],[dot1(2) dot2(2)],39。,2)。O39。fontsize39。text(300,300,39。,39。,12)。O=[80 210]。P2=[ ]。LineWidth39。 an1=angle(plex(P1(1)O(1),P1(2)O(2)))。if an20 an2=an2+2*pi。plot(O(1)+R*cos(an),O(2)+R*sin(an),39。,2)。dot2=[300,300]。LineWidth39。OBopen text(0,0,39。,39。,12)。B39。fontsize39。R=10。 dot1=O。linePic(dot1,dot2)。P1=[,]。arcPic(O1,P1,P2,R) dot1=[,]。linePic(dot1,dot2)。P2=[150,]。arcPic(O1,P1,P2,R)。dot1=dott(1:2)。linePic(dot1,dot2)。P1=arcc(1:2)。O1=arcc(5:6)。 dott=[230 470 230 530]。dot2=dott(3:4)。 arcc=[ 230 530 220,530 ]。P2=arcc(3:4)。arcPic(O1,P1,P2,R)。dot1=dott(1:2)。linePic(dot1,dot2)。P1=arcc(1:2)。O1=arcc(5:6)。 dott=[ 100 700]。dot2=dott(3:4)。 % 163。0,0163。 163。,163。 % 163。,163。 163。,163。 163。60,300163。 10% 163。,163。 163。,163。 % 163。,163。 163。150,163。 163。150,435163。 10% 163。150,163。 163。,163。 % 163。,163。 163。230,470163。 163。220,470163。 10% 163。230,470163。 163。230,530163。 % 163。230,530163。 163。,163。 163。220,530163。 10% 163。,163。 163。,163。 % 163。,163。 163。,163。 163。150,600163。 10% 163。,163。 163。100,700163。 OABCOopen text(0,0,39。,39。,12)。C39。fontsize39。R=10。 data={ [0 0 ] [, , 80,210 ][ , ] [, , ] [ , ] [, , 220,530 ] [, , ] [, , 150,600 ] [, , ] [, , , ][ , , ][ , 272 270,680 ][ 272 368, ] [ 368, 370,670 370,680][ 370,670 430,670 ] [430,670 430,680 ] [ ] [ 540,740 540,730 ][ 540,740 670,740 ] [670,740 , 670,730 ] [, , ][ , , , ][ , ][ 730,600 720,600 ][ 730,600 730,520 ] [730,530 720,520 ]