多目標的距離之和最小問題

演算法與資料結構設計報告

（ 2015 / 2016 學年第二學期）

題目：多目標的距離之和最小問題

專業學生姓名

班級學號

指導教師

指導單位

日期一、課題名稱

二、課題內容和要求

【問題描述】

小明正在玩《文明iii》遊戲，現在他有n個洲際飛彈(簡稱icbm)。他需要在最短的時間內，用這n個icbm摧毀敵方n個目標(1個icbm只能摧毀1個目標)。n個icbm和目標的位置不一定相同，小明覺得給每個icbm確定目標是一件很麻煩的事情。

請你程式設計幫助小明給每個icbm確定目標，使每個icbm到其目標的距離之和最小。

輸入：第一行：n (n<=12)

第2到n+1行：x,y

說明：每一行包含乙個座標(x,y)，表示乙個icbm，-10000第n+2到2n+1行：x,y

說明：每一行包含乙個座標(x,y)，表示乙個目標，-10000輸出：

僅一行：min

說明：min是每個icbm到其目標距離之和的最小值。結果保留3位小數。

sample input:

21 1

-1 -1

-2 -2

2 2sample output:

2.828

三、需求分析

（1）由主函式呼叫init（）函式

（2）以唯讀形式調取十個測試資料和十個結果比對資料，十個測試資料一次呼叫km()函式，算出結果與結果比對，因為資料都是保留小數點後三位，所以加上myans = int(myans*1000+0.5)/1000.0; 這條命令，可以使演算結果與比對結果一直。

如果結果一致輸出「true!」;結果不一致，輸出「flase!」

（3）km()函式求最佳路徑，定義nx,ny分別為x點集y點集的個數,lx,ly為可行頂標,lx初始化為與它關聯邊中最大的，呼叫int dfs函式増廣路，修改頂標，返回多目標的最小路徑和。

（4）若ny是圖g中一條連通飛彈和目標的路徑，並且屬於nx的邊和不屬於nx的邊（即已匹配和待匹配的邊)在ny上交替出現，則稱p為相對於nx的一條增廣路徑。該步驟即開始分配ny，即找到n個不同行不同列的ny；其中包括當找到不同行不同列的元素小於lx(初始化為與它關聯邊中最大的)時（飛彈和目標的之間的年限不足）既要開始重新重新整理ny資訊,即不在相等子圖中slack 取最小的。

四、概要設計

五、詳細設計

#include <>

#define m 500

#define inf 0x3f3f3f3f

int n,nx,ny;//nx,ny分別為x點集y點集的個數

int link[m],slack[m];

int visx[m],visy[m];

double x[m][3],y[m][3],w[m][m],lx[m],ly[m]; //lx,ly為可行頂標，

int dfs(int x)//dfs增廣路

else if (slack[y] > t) //不在相等子圖中slack 取最小的

slack[y] = t;

}return 0;

}double km()

}double res = 0;

for (i = 1;i <= ny;i ++)

if (link[i] > -1)

res += w[link[i]][i];

return -1.0*res;

}void init(){//初始化輸入

int i,j,len,t;

char s[1];

double temp,ans;

//char filein = "c:\\users\\administrator\\desktop\\測試\\"; //檔名

char filein = "";

char fileout = "";

//char fileout = "c:\\users\\administrator\\desktop\\測試\\"; //檔名

file *fp;

for(t=1;t<=9;t++)

{if(t==6) continue;

len = strlen(filein);

itoa(t,s,10);

filein[len-1] = s[0];

fileout[len-1] = s[0];

fp = fopen(filein,"r");

fscanf(fp,"%d",&n);

nx=ny=n;

for(i=1;i<=n;i++)

fscanf(fp,"%lf%lf",&x[i][1],&x[i][2]);

for(i=1;i<=n;i++)

fscanf(fp,"%lf%lf",&y[i][1],&y[i][2]);

fclose(fp);

for(i=1;i<=n;i++)

for(j=1;j<=n;j++){

temp=0;

temp = (x[i][1]-y[j][1])*(x[i][1]-y[j][1]);

temp += (x[i][2]-y[j][2])*(x[i][2]-y[j][2]);

w[i][j] = -1*sqrt(temp);

double myans = km();

myans = int(myans*1000+0.5)/1000.0;

fp = fopen(fileout,"r");

fscanf(fp,"%lf",&ans

if(fabs(ans-myans)>1e-5)

printf("輸入資料%d：flase!\n",t);

else

printf("輸入資料%d：true!\n",t);

多目標的距離之和最小問題

《我與我的目標的距離》主題班會活動方案

第10章多目標規劃簡介

Matlab學習系列27多目標規劃

多目標的距離之和最小問題

《我與我的目標的距離》主題班會活動方案

第10章多目標規劃簡介

Matlab學習系列27多目標規劃

相關推薦