公園道路規(guī)劃問題

-.z.A題公園道路最優(yōu)設(shè)計(jì)問題一、摘要本文討論的是公園道路最優(yōu)設(shè)計(jì)問題。在滿足任意兩入口之間最短道路長不大于兩點(diǎn)連線的1.4倍的條件下，建立相應(yīng)最短道路模型，使得修建總道路長度最短。又因公園邊界已經(jīng)存在修建好的道路，所以應(yīng)盡量利用邊界道路。針對問題一，12個(gè)入口和穿插點(diǎn)構(gòu)成稀疏的網(wǎng)，依據(jù)Kruskal算法，構(gòu)造最小生成樹，在滿足要求的情況下，得到最優(yōu)道路設(shè)計(jì)方案〔圖〕，使得公園新修路的總路程最小為364.1458米。針對問題二，先簡化約束條件，分步增加穿插點(diǎn)個(gè)數(shù)，再采用逐步逼近的思想，求得滿足條件的最短道路設(shè)計(jì)。運(yùn)用迭代法結(jié)合C語言編程，得出較優(yōu)道路設(shè)計(jì)方案〔圖〕，使得公園新修路的總路程最小為358.529730米。針對問題三，假設(shè)湖四周已經(jīng)有道路，盡量利用湖四周道路，在第二問的根底上，進(jìn)展局部優(yōu)化，分析道路與湖的穿插點(diǎn)，用迭代法逐步逼近，得到較優(yōu)道路設(shè)計(jì)方案〔圖〕，使得公園新修路的總路程最小為318.727931米。關(guān)鍵詞：Kruskal算法局部優(yōu)化逐步逼近非線性規(guī)劃迭代算法二、問題的提出一矩形公園有假設(shè)干入口，公園四周的邊存在已經(jīng)建好的道路且道路長度不計(jì)入道路總長?，F(xiàn)為滿足公園任意兩個(gè)入口相連，且任意的兩個(gè)入口之間的最短道路長不大于兩點(diǎn)連線的1.4倍，求使總道路長度和最小的最短道路，給出道路設(shè)計(jì)?，F(xiàn)需要解決如下三個(gè)問題：1.假設(shè)公園內(nèi)確定四個(gè)道路穿插點(diǎn)：A〔50，75〕，B〔40，40〕，C〔120，40〕，D〔115，70〕，建立模型給出算法，在滿足條件下，確定使得公園內(nèi)道路總路程最短的設(shè)計(jì)，計(jì)算總路程。2.假設(shè)公園內(nèi)可任意修建道路，建立模型給出算法，在滿足條件下，確定道路穿插點(diǎn)坐標(biāo)，從而獲得公園內(nèi)道路總路程最短的設(shè)計(jì)，計(jì)算總路程。3.假設(shè)公園內(nèi)有一矩形湖，新修的道路不能通過，但可以到達(dá)湖四周的邊。在滿足條件下，確定道路穿插點(diǎn)坐標(biāo)，從而獲得公園內(nèi)道路總路程最短的設(shè)計(jì)，計(jì)算總路程。三、問題的分析針對問題一，給定四個(gè)確定道路穿插點(diǎn)，為使得設(shè)計(jì)的公園道路總路程最短。聯(lián)系數(shù)據(jù)構(gòu)造中的最小生成樹問題——最小生成樹是各邊長度之和最短的連通路徑。可以把入口，道路穿插點(diǎn)及邊界構(gòu)成的圖看作是稀疏的網(wǎng)，求得所有邊的長度，根據(jù)克魯思卡爾算法，在未連通的情況下，依次取出最短的邊，以此類推構(gòu)造出最小生成樹。建立最短路徑模型，求得使總路程最小的設(shè)計(jì)。針對問題二，未規(guī)定穿插點(diǎn)的數(shù)目和位置，這就需要進(jìn)展討論分析。簡化約束條件，逐步分析，增加穿插點(diǎn)的個(gè)數(shù)，用迭代的方法逐步逼近最優(yōu)解，求得滿足條件下的最短新修路的總路程。針對問題三，在問題二的根底上進(jìn)展局部優(yōu)化，再次用迭代法逐步逼近，得到最優(yōu)解。值得注意的是邊界道路不算在總設(shè)計(jì)道路里，但是算到兩入口間最短道路長度里。四、模型假設(shè)1.假設(shè)公園各點(diǎn)處在同一個(gè)平面。2.假設(shè)所有點(diǎn)之間修建道路均為直線。3.穿插點(diǎn)不影響道路的修建。4.假設(shè)湖四周有已修建好的道路，且不計(jì)入道路總長。五、符號及變量說明符號及變量含義備注ij兩點(diǎn)連線長度即兩點(diǎn)間距離表示是否需要取ij兩點(diǎn)連線長度最短總路徑中在通過邊界道路的總長度新建道路總長度ij兩點(diǎn)最短路徑長度k號入口局k+1號入口之間沿邊界經(jīng)過的路徑長度為號入口到1號入口沿邊界的最短路徑六、模型的建立與求解6.1問題一模型與求解為描述方便，我們將穿插點(diǎn)分別定義為點(diǎn)9、10、11、12，如下圖：為求得最短新修路的總路程，聯(lián)系數(shù)據(jù)構(gòu)造中的最短路徑問題，最小生成樹是各邊長度之和最短的路徑?？梢园讶肟?，道路穿插點(diǎn)及邊界構(gòu)成的圖看作是稀疏網(wǎng)，求得所有邊的長度，根據(jù)克魯思卡爾算法，在未連通的根底上，依次取出最短的邊，以此類推構(gòu)造出最小生成樹?？赡艿牡缆吩O(shè)計(jì)如圖：〔圖中標(biāo)注的紅字為構(gòu)造最小生成樹的次序〕構(gòu)造的最小生成樹是道路總路程最短的道路設(shè)計(jì)，但根據(jù)題意，需驗(yàn)證是否滿足任意兩入口之間最短道路長不大于兩點(diǎn)連線的1.4倍。經(jīng)過計(jì)算可知，入口1到入口5之間最短道路長大于兩點(diǎn)連線1.4倍，不滿足題目要求。所以，為滿足題目要求，需改動(dòng)入口1到入口5之間道路路徑，又經(jīng)過計(jì)算比擬可知，在可使得入口1到達(dá)入口5的路徑中，只有選取入口5和入口12之間的道路可使得公園道路總路程最短。故最終新修道路總路程為364.1458米，道路設(shè)計(jì)圖如下：6.2問題二的模型現(xiàn)公園內(nèi)可以任意修建道路，故穿插點(diǎn)個(gè)數(shù)不確定。采用分步添加穿插點(diǎn)個(gè)數(shù)，逐步逼近的思想，分析公園道路總長度的變化情況。先簡化約束條件為ij兩點(diǎn)的線段距離；是對角線為0的對稱矩陣，如下表：編號123456781030140186.815141.421101.118100.49832.0152300110158.113122.065101.118107.703355.9013140110064.031107.703160.078180.2776161.9414186.815158.11364.0312094.339172.409196.4688201.5565141.421122.065107.70394.339085110141.5096105.948101.118160.078172.4098502582.7647100.498100.498180.277196.46811025075.663832.01555.901161.941201.556141.50982.76475.6630為ij兩點(diǎn)間的道路是否需要修建，；C：在同一邊界上的兩入口，需要利用邊界通過的道路長度和；所以目標(biāo)函數(shù)為新修路的總路程l的最小值min；約束條件是任意的兩個(gè)入口之間的最短道路長不大于兩點(diǎn)連線的1.4倍。設(shè)ij兩點(diǎn)間的最短路徑，則;判斷兩入口點(diǎn)的最短路徑有個(gè)約束條件，但是1、2、3和5、6、7三入口點(diǎn)分別在同一條邊界上，已經(jīng)有道路，不需再考慮到約束條件里，則約束條件變?yōu)?2個(gè)；再進(jìn)一步簡化約束條件，經(jīng)過計(jì)算1、4,1、7,2、4,2、8,3、8,4、5,4、6,4、7,4、8,5、8，6、8,7、8都可以在滿足約束條件下經(jīng)邊緣道路連通，所以不需考慮到約束條件里，約束條件進(jìn)一步簡化為10個(gè)。再進(jìn)一步簡化約束條件，因?yàn)?.4倍3-5加5-6小于1.4倍3-6，所以只要3、5點(diǎn)滿足條件，3、6就滿足條件，則3、6也不用考慮，同理3、7點(diǎn)也不用考慮，這樣約束條件就只剩下8個(gè)。即1、5,1、6,1、7,2、5,2、6,2、7,3、4,3、5。約束條件：；假設(shè)沒有交點(diǎn)，延續(xù)第一問的最小生成樹思想，作出最小生成樹，因1到6長度與2到6長度相等，故有兩種可能的道路設(shè)計(jì)。方案一中的道路總長度為426.9344米。如下列圖：方案二中的道路總長度為426.9344米。如下列圖：二.現(xiàn)添加一個(gè)交點(diǎn)M〔9〕，如下列圖所示：在無交點(diǎn)的根底上增加1個(gè)穿插點(diǎn)進(jìn)展進(jìn)一步優(yōu)化，設(shè)穿插點(diǎn)為M〔*,y〕，我們利用C語言編程，采用逐步逼近的思想，在滿足條件的情況下,找到了坐標(biāo)為M〔114.5，32〕最短新修路的總路程為393.015325米。規(guī)劃圖如下：下面是對C程序逐步逼近思想的簡單介紹〔程序見附錄〕：〔1〕建立2個(gè)for循環(huán)，分別以M點(diǎn)的橫縱坐標(biāo)作為循環(huán)變量〔2〕先讓M的縱坐標(biāo)y由0加到100，M的橫坐標(biāo)*由35加到200，以1為步長進(jìn)展逐步逼近，找到一點(diǎn)M〔112，34〕，此時(shí)新修路的總路程為393.181065米；〔3〕再進(jìn)一步逼近，在已求出點(diǎn)的根底上，縮小尋找范圍。以0.1為步長，求出M點(diǎn)〔114.5,32〕，此時(shí)最短新修路的總路程為393.015325米；三.添加一個(gè)交點(diǎn)作進(jìn)一步優(yōu)化在一個(gè)交點(diǎn)的根底上進(jìn)一步優(yōu)化，沿用一個(gè)交點(diǎn)的逐步逼近方法，求出M點(diǎn)坐標(biāo)〔59，79〕，N點(diǎn)坐標(biāo)〔173,44〕，最短新修路的總路程為358.573346米；再進(jìn)一步逼近，在已求出點(diǎn)的根底上，縮小尋找范圍。以0.1為步長，讓N的縱坐標(biāo)由75加到85,找到的最正確位置，再依次讓N的橫坐標(biāo)由170加到180，M的縱坐標(biāo)由40加到50，M的橫坐標(biāo)由75加到85，找到兩點(diǎn)M〔59.7,77.6〕N〔173.1,43.6〕，此時(shí)最短新修路的總路程為358.529730米；四.在上圖的根底上繼續(xù)添加交點(diǎn)，不存在能使兩條相鄰的路徑變短的第三個(gè)點(diǎn)，所以上圖兩交點(diǎn)的規(guī)劃為問題二的最優(yōu)解，最短新修路的總路程為358.529730米。6.3問題三的模型在問題二的根底上把湖考慮進(jìn)去，如下列圖：1、2、6、7、8五點(diǎn)離湖較遠(yuǎn)，且己規(guī)劃的路徑不受湖的影響，僅需考慮3、4、5與湖的關(guān)系，道路不能通過湖，但可以利用湖的四周已經(jīng)有的道路進(jìn)一步優(yōu)化。為了利用湖已經(jīng)有的道路，所以道路與湖的交點(diǎn)個(gè)數(shù)至少為2個(gè)，經(jīng)分析，如果道路與湖的交點(diǎn)多于2個(gè)，則3、4點(diǎn)不滿足約束條件，故連接湖與道路的交點(diǎn)必然有兩個(gè)，共有四種情況。從入口5出發(fā)的道路與湖的交點(diǎn)可能在R1R4或R1R2上，從n點(diǎn)出發(fā)的道路與湖的交點(diǎn)可能在R2R3或R4R3上。兩交點(diǎn)在湖對邊和兩交點(diǎn)在湖鄰邊均有兩種情況，在湖對邊的繞行距離和修建道路長度都會(huì)比在鄰邊時(shí)長，所以此處只考慮相鄰的兩種情況。延續(xù)之前的逐步逼近方法，設(shè)出道路與湖的交點(diǎn)P、Q的坐標(biāo)和點(diǎn)N的坐標(biāo)，用迭代逼近的思路，求出P、Q、N的坐標(biāo)，求出最短道路長度318.727931米。第一種情況：與湖相交上邊和右邊，求出的結(jié)果N點(diǎn)坐標(biāo)〔169.9,40.8〕、P〔165，45〕Q〔140,70〕，最短道路長度318.727931米。第二種情況：與湖相交于左邊和下邊，求出的結(jié)果N點(diǎn)坐標(biāo)〔169.5,40.8〕、P〔165，45〕、Q〔140,69.9〕，最短道路長度324.866691米。所以最優(yōu)方案為第一種情況的，N點(diǎn)坐標(biāo)〔169.9,40.8〕、P〔165，45〕Q〔140,70〕，最短道路長度318.727931米。道路設(shè)計(jì)如下列圖所示：七、模型的優(yōu)缺點(diǎn)分析及推廣優(yōu)點(diǎn)：1.利用克魯斯卡爾算法建立最小生成樹模型，模型簡單便于求解。2.運(yùn)用逐步逼近的思想，利用c語言編寫程序，解決了lingo因?yàn)樽兞窟^多而不能直接解決的非線性規(guī)劃問題，方法簡單可行。缺點(diǎn)：逐步逼近的方法具有一定的局限性，只能無限逼近最優(yōu)解。推廣：此模型可應(yīng)用于各種最短道路或線路選取和規(guī)劃問題、最小生成樹問題。八、參考文獻(xiàn)【1】嚴(yán)蔚敏、*偉民編著，數(shù)據(jù)構(gòu)造，清華大學(xué)出版，2021【2】韓中庚，數(shù)學(xué)建模方法及其應(yīng)用，高等教育，2005【3】姜啟源、謝金星，數(shù)學(xué)建模，高等教育，2003九、附錄9.1一個(gè)交點(diǎn)的第一次逼近以1為步長，縮小穿插點(diǎn)的查找范圍：#include<iostream>//一個(gè)點(diǎn)的情況第一次逼近#include<cmath>voidmain(){doubleA[6][2];A[0][0]=20;A[0][1]=0;A[1][0]=50;A[1][1]=0;A[2][0]=160;A[2][1]=0;A[3][0]=120;A[3][1]=100;A[4][0]=35;A[4][1]=100;A[5][0]=10;A[5][1]=100;doubled25,a25,d35,a35,d18,d34,d26;a25=122.066;a35=107.703;d18=32.0156;d26=101.1187421;d34=64.0312;double*,y,*0,y0;*=50;y=0;doublet1,t2;doublel=1000;doublel0;doubleD[2][6];for(t2=-5;t2<=110;t2=t2+1){for(t1=-5;t1<=100;t1=t1+1){D[0][1]=sqrt((*+t1-A[1][0])*(*+t1-A[1][0])+(y+t2-A[1][1])*(y+t2-A[1][1]));D[0][2]=sqrt((*+t1-A[2][0])*(*+t1-A[2][0])+(y+t2-A[2][1])*(y+t2-A[2][1]));D[0][3]=sqrt((*+t1-A[3][0])*(*+t1-A[3][0])+(y+t2-A[3][1])*(y+t2-A[3][1]));d25=D[0][1]+D[0][3];d35=D[0][2]+D[0][3];if(d25<=1.4*a25)if(d35<=1.4*a35){l0=d35+d25+d18+d26+d34-D[0][3];if(l0<l){l=l0;*=*+t1;y=y+t2;}}}}printf("m點(diǎn)的大致橫坐標(biāo)\n");printf("%f\n",*);printf("m點(diǎn)的大致縱坐標(biāo)\n");printf("%f\n",y);printf("大致需要修建道路最短長度\n");printf("%f\n",l);}程序運(yùn)行結(jié)果如下：9.2一個(gè)點(diǎn)交點(diǎn)的第二次逼近以0.1為步長，縮小穿插點(diǎn)的尋找范圍：#include<iostream>//一個(gè)點(diǎn)的情況第二次逼近#include<cmath>voidmain(){doubleA[6][2];A[0][0]=20;A[0][1]=0;A[1][0]=50;A[1][1]=0;A[2][0]=160;A[2][1]=0;A[3][0]=120;A[3][1]=100;A[4][0]=35;A[4][1]=100;A[5][0]=10;A[5][1]=100;doubled25,a25,d35,a35,d18,d34,d26;a25=122.066;a35=107.703;d18=32.0156;d26=101.1187421;d34=64.0312;double*,y,*0,y0;*=112;y=34;doublet1,t2;doublel=1000;doublel0;doubleD[2][6];for(t2=-5;t2<=5;t2=t2+0.1){for(t1=-5;t1<=5;t1=t1+0.1){D[0][1]=sqrt((*+t1-A[1][0])*(*+t1-A[1][0])+(y+t2-A[1][1])*(y+t2-A[1][1]));D[0][2]=sqrt((*+t1-A[2][0])*(*+t1-A[2][0])+(y+t2-A[2][1])*(y+t2-A[2][1]));D[0][3]=sqrt((*+t1-A[3][0])*(*+t1-A[3][0])+(y+t2-A[3][1])*(y+t2-A[3][1]));d25=D[0][1]+D[0][3];d35=D[0][2]+D[0][3];if(d25<=1.4*a25)if(d35<=1.4*a35){l0=d35+d25+d18+d26+d34-D[0][3];if(l0<l){l=l0;*=*+t1;y=y+t2;}}}}printf("m點(diǎn)的大致橫坐標(biāo)\n");printf("%f\n",*);printf("m點(diǎn)的大致縱坐標(biāo)\n");printf("%f\n",y);printf("大致需要修建道路最短長度\n");printf("%f\n",l);}程序運(yùn)行結(jié)果如下：9.3兩交個(gè)點(diǎn)的第一次逼近以1為步長，縮小穿插點(diǎn)的尋找范圍：#include<iostream>//兩個(gè)點(diǎn)的情況第一次逼近#include<cmath>voidmain(){doubleA[6][2];A[0][0]=20;A[0][1]=0;A[1][0]=50;A[1][1]=0;A[2][0]=160;A[2][1]=0;A[3][0]=120;A[3][1]=100;A[4][0]=35;A[4][1]=100;A[5][0]=10;A[5][1]=100;doublea12,a67,d15,dn4,a15,d16,a16,d18,d25,a25,d26,a26,d27,a27,d34,a34,d35,a35;a15=141.421;a16=101.119;a25=122.066;a26=101.119;a27=107.703;a35=107.703;a34=64.03124;a12=30;a67=25;doubleN[2][2],N0[2][2];N[0][0]=35;N[0][1]=0;N[1][0]=120;N[1][1]=0;doublet1,t2,t3,t4;doublel=1000,l0=0;doubleD[2][6];for(t1=0;t1<=85;t1=t1+1){for(t2=0;t2<=100;t2=t2+1){for(t3=0;t3<=80;t3=t3+1){for(t4=0;t4<=50;t4=t4+1){D[0][1]=sqrt((N[0][0]+t1-A[1][0])*(N[0][0]+t1-A[1][0])+(N[0][1]+t2-A[1][1])*(N[0][1]+t2-A[1][1]));D[0][3]=sqrt((N[0][0]+t1-A[3][0])*(N[0][0]+t1-A[3][0])+(N[0][1]+t2-A[3][1])*(N[0][1]+t2-A[3][1]));D[0][4]=sqrt((N[0][0]+t1-A[4][0])*(N[0][0]+t1-A[4][0])+(N[0][1]+t2-A[4][1])*(N[0][1]+t2-A[4][1]));D[1][2]=sqrt((N[1][0]+t3-A[2][0])*(N[1][0]+t3-A[2][0])+(N[1][1]+t4-A[2][1])*(N[1][1]+t4-A[2][1]));D[1][3]=sqrt((N[1][0]+t3-A[3][0])*(N[1][0]+t3-A[3][0])+(N[1][1]+t4-A[3][1])*(N[1][1]+t4-A[3][1]));dn4=sqrt((N[1][0]+t3-200)*(N[1][0]+t3-200)+(N[1][1]+t4-50)*(N[1][1]+t4-50));d15=D[0][1]+D[0][3]+a12;d16=D[0][1]+D[0][4]+a12;d18=32.0156;d25=D[0][1]+D[0][3];d26=D[0][1]+D[0][4];d27=D[0][1]+D[0][4]+a67;d34=D[1][2]+dn4;d35=D[1][2]+D[1][3];if(d15<=1.4*a15){if(d16<=1.4*a16){if(d25<=1.4*a25){if(d26<=1.4*a26){if(d27<=1.4*a27){if(d35<=1.4*a35){if(d34<=1.4*a34){l0=d18+D[0][1]+D[0][3]+D[0][4]+D[1][3]+D[1][2]+dn4;if(l0<l){l=l0;N0[0][0]=N[0][0]+t1;N0[0][1]=N[0][1]+t2;N0[1][0]=N[1][0]+t3;N0[1][1]=N[1][1]+t4;}}}}}}}}}}}}printf("m點(diǎn)的大致橫坐標(biāo)\n");printf("%f\n",N0[0][0]);printf("m點(diǎn)的大致縱坐標(biāo)\n");printf("%f\n",N0[0][1]);printf("n點(diǎn)的大致橫坐標(biāo)\n");printf("%f\n",N0[1][0]);printf("n點(diǎn)的大致縱坐標(biāo)\n");printf("%f\n",N0[1][1]);printf("大致需要修建道路最短長度\n");printf("%f\n",l);}程序運(yùn)行結(jié)果如下：9.4兩個(gè)點(diǎn)的第二次逼近以0.1為步長，縮小穿插點(diǎn)的查找范圍：#include<iostream>//兩個(gè)點(diǎn)的情況第二次逼近#include<cmath>voidmain(){doubleA[6][2];A[0][0]=20;A[0][1]=0;A[1][0]=50;A[1][1]=0;A[2][0]=160;A[2][1]=0;A[3][0]=120;A[3][1]=100;A[4][0]=35;A[4][1]=100;A[5][0]=10;A[5][1]=100;doublea12,a67,d15,dn4,a15,d16,a16,d18,d25,a25,d26,a26,d27,a27,d34,a34,d35,a35;a15=141.421;a16=101.119;a25=122.066;a26=101.119;a27=107.703;a35=107.703;a34=64.03124;a12=30;a67=25;doubleN[2][2],N0[2][2];N[0][0]=59;N[0][1]=79;N[1][0]=173;N[1][1]=44;doublet1,t2,t3,t4;doublel=1000,l0=0;doubleD[2][6];for(t1=-5;t1<=5;t1=t1+0.1){for(t2=-5;t2<=5;t2=t2+0.1){for(t3=-5;t3<=5;t3=t3+0.1){for(t4=-5;t4<=5;t4=t4+0.1){D[0][1]=sqrt((N[0][0]+t1-A[1][0])*(N[0][0]+t1-A[1][0])+(N[0][1]+t2-A[1][1])*(N[0][1]+t2-A[1][1]));D[0][3]=sqrt((N[0][0]+t1-A[3][0])*(N[0][0]+t1-A[3][0])+(N[0][1]+t2-A[3][1])*(N[0][1]+t2-A[3][1]));D[0][4]=sqrt((N[0][0]+t1-A[4][0])*(N[0][0]+t1-A[4][0])+(N[0][1]+t2-A[4][1])*(N[0][1]+t2-A[4][1]));D[1][2]=sqrt((N[1][0]+t3-A[2][0])*(N[1][0]+t3-A[2][0])+(N[1][1]+t4-A[2][1])*(N[1][1]+t4-A[2][1]));D[1][3]=sqrt((N[1][0]+t3-A[3][0])*(N[1][0]+t3-A[3][0])+(N[1][1]+t4-A[3][1])*(N[1][1]+t4-A[3][1]));dn4=sqrt((N[1][0]+t3-200)*(N[1][0]+t3-200)+(N[1][1]+t4-50)*(N[1][1]+t4-50));d15=D[0][1]+D[0][3]+a12;d16=D[0][1]+D[0][4]+a12;d18=32.0156;d25=D[0][1]+D[0][3];d26=D[0][1]+D[0][4];d27=D[0][1]+D[0][4]+a67;d34=D[1][2]+dn4;d35=D[1][2]+D[1][3];if(d15<=1.4*a15){if(d16<=1.4*a16){if(d25<=1.4*a25){if(d26<=1.4*a26){if(d27<=1.4*a27){if(d35<=1.4*a35){if(d34<=1.4*a34){l0=d18+D[0][1]+D[0][3]+D[0][4]+D[1][3]+D[1][2]+dn4;if(l0<l){l=l0;N0[0][0]=N[0][0]+t1;N0[0][1]=N[0][1]+t2;N0[1][0]=N[1][0]+t3;N0[1][1]=N[1][1]+t4;}}}}}}}}}}}}printf("m點(diǎn)的大致橫坐標(biāo)\n");printf("%f\n",N0[0][0]);printf("m點(diǎn)的大致縱坐標(biāo)\n");printf("%f\n",N0[0][1]);printf("n點(diǎn)的大致橫坐標(biāo)\n");printf("%f\n",N0[1][0]);printf("n點(diǎn)的大致縱坐標(biāo)\n");printf("%f\n",N0[1][1]);printf("大致需要修建道路最短長度\n");printf("%f\n",l);}程序運(yùn)行結(jié)果如下：9.5有湖的第一種情況有湖的優(yōu)化情況1：#include<iostream>//有湖第一種情況第二次逼近#include<cmath>voidmain(){doubleA[6][2];A[0][0]=20;A[0][1]=0;A[1][0]=50;A[1][1]=0;A[2][0]=160;A[2][1]=0;A[3][0]=120;A[3][1]=100;A[4][0]=35;A[4][1]=100;A[5][0]=10;A[5][1]=100;doubled35,d34,d5,dn,dn4,dn3;doubled18=32.0156,dm6=32.4205,dm5=64.3261,dm2=80.0615;doublea34=64.03124,a35=107.7033;double*,y,*0,y0,p,p0,q,q0;*=169;y=41;q=140;p=45;doublet1,t2,t3,t4;doublel=1000;doublel0;doubleD[1][3];for(t4=-5;t4<0;t4=t4+0.1){for(t3=0;t3<=5;t3=t3+0.1){for(t1=-5;t1<=4;t1=t1+0.1){for(t2=-5;t2<=5;t2=t2+0.1){dn4=sqrt((*+t1-200)*(*+t1-200)+(y+t2-50)*(y+t2-50));dn=sqrt((*+t1-165)*(*+t1-165)+(y+t2-p-t3)*(y+t2-p-t3));d5=sqrt((140-q-t4)*(140-q-t4)+(100-70)*(100-70));D[0][2]=sqrt((*+t1-A[2][0])*(*+t1-A[2][0])+(y+t2-A[2][1])*(y+t2-A[2][1]));d34=D[0][2]+dn4;d35=D[0][2]+dn+d5+(70-p)+(165-q);if(d34<=1.4*a34)if(d35<=1.4*a35){l0=dm2+dm5+d18+dm6+d5+dn+dn4+D[0][2];if(l0<l){l=l0;*0=*+t1;y0=y+t2;p0=p+t3;q0=q+t4;}}}}}}printf("n點(diǎn)的大致橫坐標(biāo)\n");printf("%f\n",*0);printf("n點(diǎn)的大致縱坐標(biāo)\n");printf("%f\n",y0);printf("q點(diǎn)的大致*坐標(biāo)\n");printf("%f\n",q0);printf("p點(diǎn)的大致*坐標(biāo)\n");printf(