資源簡介
用無向網表示校園景點平面圖，圖中頂點表示主要景點，存放景點的編號、名稱、簡介等信息，圖中的邊表示景點間的道路，存放路徑長度等信息。要求能夠回答有關景點介紹、游覽路徑等問題。?
基本要求：?
①?查詢任意景點的相關信息；
②?查詢圖中任意兩個景點間的最短路徑。
③?查詢圖中任意兩個景點間的所有路徑。
④?增加、刪除、更新有關景點和道路的信息。
（選作）*?求多個景點的最佳（最短）游覽路徑。
帶圖形界面，動態標記路線，95分的課設
代碼片段和文件信息
package?com.schoolguider.algorithms;
import?java.util.ArrayList;
import?com.schoolguider.components.Node;
import?com.schoolguider.utility.Manager;
/**
?*?雙調歐幾里得旅行商問題
?*?
?*?@author?xing
?*
?*/
public?class?TSP?{
/**
?*?用來獲取結點和邊的管理類
?*/
private?Manager?manager;
/**
?*?景點的個數
?*/
private?int?num?=?0;
/**
?*?存儲最短路徑
?*/
private?double?d[][];
/**
?*?存儲任意兩個結點之間的直線距離
?*/
private?double?p[][];
/**
?*?存儲結點的數組
?*/
private?TSPNode[]?tspNodeArray;
/**
?*?存儲路徑
?*/
private?int?kay[][];
public?TSP（Manager?manager）?{
this.manager?=?manager;
init（）;
qsort（1?num）;
getAllDis（）;
}
/**
?*?初始化數據，為算法做準備
?*/
private?void?init（）?{
ArrayList?nodeList?=?manager.getNodeList（）;
num?=?nodeList.size（）;
tspNodeArray?=?new?TSPNode[num?+?1];
d?=?new?double[num?+?1][num?+?1];
p?=?new?double[num?+?1][num?+?1];
kay?=?new?int[num?+?1][num?+?1];
/*
?*?構造結點數組
?*/
for?（int?i?=?1;?i?<=?num;?i++）?{
Node?node?=?nodeList.get（i-1）;
int?x?=?node.getX（）;
int?y?=?node.getY（）;
tspNodeArray[i]?=?new?TSPNode（x?y）;
}
getAllDis（）;
}
/**
?*?計算兩點之間的直線距離
?*?
?*?@param?x1
?*?@param?y1
?*?@param?x2
?*?@param?y2
?*?@return
?*/
private?double?getDistance（int?x1?int?y1?int?x2?int?y2）?{
int?x?=?（x1?-?x2）?*?（x1?-?x2）;
int?y?=?（y1?-?y2）?*?（y1?-?y2）;
return?Math.sqrt（x?+?y）;
}
/**
?*?計算所有的道路的長度
?*/
private?void?getAllDis（）?{
for?（int?i?=?1;?i? for?（int?j?=?i?+?1;?j?<=?num;?j++）
p[i][j]?=?p[j][i]?=?getDistance（tspNodeArray[i].getX（）
tspNodeArray[i].getY（）?tspNodeArray[j].getX（）
tspNodeArray[j].getY（））;
}
/**
?*?快速排序的算法
?*?
?*?@param?l
?*?@param?r
?*/
private?void?qsort（int?l?int?r）?{
/*
?*?利用移位操作獲取終點坐標
?*/
int?i?=?l?j?=?r?mid?=?tspNodeArray[（i?+?j）?>>?1].getX（）;
while?（i? while?（tspNodeArray[i].getX（）? i++;
while?（mid? j--;
if?（i?<=?j）?{
/*
?*?交換兩個結點的x坐標和y坐標
?*/
swap（tspNodeArray[i].getX（）?tspNodeArray[j].getX（））;
swap（tspNodeArray[i].getY（）?tspNodeArray[j].getY（））;
i++;
j--;
}
}
/*
?*?將原來的數組分為兩部分繼續遞歸
?*/
if?（l? qsort（l?j）;
if?（i? qsort（i?r）;
}
/**
?*?交換兩個數的值
?*?
?*?@param?x
?*?@param?y
?*/
private?void?swap（int?x?int?y）?{
int?temp?=?x;
x?=?y;
y?=?temp;
}
/**
?*?動態規劃計算最短路徑
?*/
public?double?DP（）?{
d[1][2]?=?p[1][2];//?最小的子問題
for?（int?j?=?3;?j?<=?num;?j++）?{
//?i=1時的情況
for?（int?i?=?1;?i? d[i][j]?=?d[i][j?-?1]?+?p[j?-?1][j];
kay[i][j]?=?j?-?1;
}
//?i=j-1的情況
d[j?-?1][j]?=?d[1][j?-?1]?+?p[1][j];//?先設初值為kay=1時的值
kay[j?-?1][j]?=?1;
/*
?*?從頭到尾進行遍歷
?*/
for?（int?k?=?1;?k? double?q?=?d[k][j?-?1]?+?p[k][j];
if?（q? d[j?-?1][j]?=?q;
kay[j?-?1][j]?=?k ?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----
?????目錄???????????0??2016-01-19?21:07??SchoolGuider3.1\
?????文件?????????402??2016-01-19?21:07??SchoolGuider3.1\.classpath
?????文件?????????391??2016-01-19?21:07??SchoolGuider3.1\.project
?????目錄???????????0??2016-01-19?21:07??SchoolGuider3.1\.settings\
?????文件?????????598??2016-01-19?21:07??SchoolGuider3.1\.settings\org.eclipse.jdt.core.prefs
?????目錄???????????0??2016-01-19?21:07??SchoolGuider3.1\bin\
?????目錄???????????0??2016-01-19?21:07??SchoolGuider3.1\bin\com\
?????目錄???????????0??2016-01-19?21:07??SchoolGuider3.1\bin\com\schoolguider\
?????目錄???????????0??2016-01-19?21:07??SchoolGuider3.1\bin\com\schoolguider\algorithms\
?????文件????????3733??2016-01-19?21:07??SchoolGuider3.1\bin\com\schoolguider\algorithms\TSP.class
?????文件?????????715??2016-01-19?21:07??SchoolGuider3.1\bin\com\schoolguider\algorithms\TSPNode.class
?????文件????????3196??2016-01-19?21:07??SchoolGuider3.1\bin\com\schoolguider\algorithms\TwoAllPath.class
?????文件????????2311??2016-01-19?21:07??SchoolGuider3.1\bin\com\schoolguider\algorithms\TwoShortPath.class
?????目錄???????????0??2016-01-19?21:07??SchoolGuider3.1\bin\com\schoolguider\client\
?????文件?????????752??2016-01-19?21:07??SchoolGuider3.1\bin\com\schoolguider\client\Addfr
?????文件????????2037??2016-01-19?21:07??SchoolGuider3.1\bin\com\schoolguider\client\Addfr
?????文件????????2777??2016-01-19?21:07??SchoolGuider3.1\bin\com\schoolguider\client\Addfr
?????文件????????6141??2016-01-19?21:07??SchoolGuider3.1\bin\com\schoolguider\client\Addfr
?????文件???????12079??2016-01-19?21:07??SchoolGuider3.1\bin\com\schoolguider\client\DisplayPanel.class
?????文件????????1124??2016-01-19?21:07??SchoolGuider3.1\bin\com\schoolguider\client\ImagePane.class
?????文件?????????475??2016-01-19?21:07??SchoolGuider3.1\bin\com\schoolguider\client\MainClient.class
?????文件????????3144??2016-01-19?21:07??SchoolGuider3.1\bin\com\schoolguider\client\Mainfr
?????文件?????????811??2016-01-19?21:07??SchoolGuider3.1\bin\com\schoolguider\client\OperationPanel$1.class
?????文件????????1111??2016-01-19?21:07??SchoolGuider3.1\bin\com\schoolguider\client\OperationPanel$2.class
?????文件????????1211??2016-01-19?21:07??SchoolGuider3.1\bin\com\schoolguider\client\OperationPanel$3.class
?????文件?????????939??2016-01-19?21:07??SchoolGuider3.1\bin\com\schoolguider\client\OperationPanel$4.class
?????文件????????2690??2016-01-19?21:07??SchoolGuider3.1\bin\com\schoolguider\client\OperationPanel$5.class
?????文件????????2719??2016-01-19?21:07??SchoolGuider3.1\bin\com\schoolguider\client\OperationPanel$6.class
?????文件????????1537??2016-01-19?21:07??SchoolGuider3.1\bin\com\schoolguider\client\OperationPanel$7.class
?????文件????????1118??2016-01-19?21:07??SchoolGuider3.1\bin\com\schoolguider\client\OperationPanel$8.class
?????文件????????1930??2016-01-19?21:07??SchoolGuider3.1\bin\com\schoolguider\client\OperationPanel$9.class
............此處省略58個文件信息
評論
共有 條評論
川公網安備 51152502000135號