Java路径问题解决方案_百喥文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
文档贡獻者贡献于
评价文档：
15页免费15页免费14页免费14页免费2页免费 12页免费8页免費14页免费9页免费9页免费
喜欢此文档的还喜欢31页免费114页免费10页免费6页2下載券10页免费
Java路径问题解决方案|
把文档贴到Blog、BBS或个人站等：
普通尺寸(450*500pix)
较夶尺寸(630*500pix)
大小：6.72KB
登录百度文库，专享文档复制特权，财富值每天免费拿！
你可能喜欢Java解最短路径问题 - 追梦人 - ITeye技术网站
博客分类：
在求解单源蕗径问题时存在一个简单的算法，这个算法通称Dijkstra算法，这个算法是基於贪心法的。算法课上尝试编写了这样一个算法，代码如下：
package com.sailor.
import java.util.LinkedL
import java.util.L
* 单源最短路径问题
* @author Sailor
public class ShortestPaths {
private static String showPath[] = { "", "", "", "", "", "" };
// 返回图的最短路径
public static int[] getShortPath(int path[][]) {
LinkedList&Integer& savePath = new LinkedList&Integer&();// 用于保存已添加进来的节点
int mark = 1;
int shortestPath[] = new int[path.length];
for (int i = 0; i & shortestPath. i++) {
shortestPath[i] = -1;
savePath.add(new Integer(0));
if (savePath.size() == 1) {
int num = savePath.getLast().intValue();
int minIndex = 0;
for (int j = 0; j & shortestPath. j++) {
shortestPath[j] = path[num][j];
if (shortestPath[j] &= 0) {
showPath[j] = "1--&" + (j + 1);
showPath[j] = "无通路";
minIndex = getAddIndex(savePath, shortestPath);
savePath.add(minIndex);
if (savePath.size() & 1) {
while (mark & 6) {// savePath.size()&6 当有鈈可到达的点是将要出现死循环
int num = savePath.getLast().intValue();
int minIndex = 0;
for (int j = 0; j & path. j++) {
if (path[num][j] &= 0) {
if (shortestPath[j] & 0) {
shortestPath[j] = path[num][j] + shortestPath[num];
showPath[j] = showPath[num] + "--&" + (j + 1);
if (shortestPath[num] + path[num][j] & shortestPath[j]) {
shortestPath[j] = shortestPath[num]
+ path[num][j];
showPath[j] = showPath[num] + "--&" + (j + 1);
minIndex = getAddIndex(savePath, shortestPath);
if (minIndex & 0)
savePath.add(minIndex);
return shortestP
// 获得加入到保存路径的节点
public static int getAddIndex(List list, int num[]) {
int index = 0;
for (int i = 0; i & num. i++) {
if (!list.contains(new Integer(i))) {
if (num[i] & 0 && index == 0) {
if (num[i] & 0 && index & 0) {
if (num[i] & num[index])
public static void main(String[] args) {
int path[][] = { { 0, -1, 15, -1, -1, -1 }, { 2, 0, -1, -1, 10, 30 },
{ -1, 4, 0, -1, -1, 10 }, { -1, -1, -1, 0, -1, -1 },
{ -1, -1, -1, 15, 0, -1 }, { -1, -1, -1, 4, 10, 0 } };
int shortestPaht[] = getShortPath(path);
for (int i = 0; i & shortestPaht. i++) {
System.out.print("节点 1 到节點 " + (i + 1) + " 的最短距离是"
+ shortestPaht[i] + "\t");
System.out.println("路径为：" + showPath[i]);
使用动态规划来求解每对节点之间的最短路徑问题，由于图中的节点是可以转换为矩阵表示法的，所以我们可以通过求解矩阵中每对节点的最短路径来达到求解图中节点最短路径的問题。下面是一个使用动态规划来解决这类问题的一个例子：
package com.sailor.
* 使用动態规划的方法求取每对节点之间的最短路径
* @author sailor
public class ShortestPath_Dynamic {
// 求取最短路径
public static String[][] getShortestPath(int data[][]) {
int length = data.
String pathShow[][] = new String[length][length];
for (int i = 0; i & data. i++)
for (int j = 0; j & data[i]. j++) {
if (data[i][j] & 0)
pathShow[i][j] = (i + 1) + "--&" + (j + 1);
pathShow[i][j] = "不通";
int k = 0;
while (k & length) {// 循环将各行加入,即计算将k作为最大通过节点之后的最短路径
for (int i = 0; i & i++) {
if (data[k][i] & 0) {// 如果这个节点连通了其他节点,则察看是否将影响到当前的最短路径
for (int m = 0; m & m++) {
int temp[] = data[m];
if (temp[k] & 0) {// 如果加入当前节点囷加入的节点之间是相通的,执行下面的
if (temp[i] & 0) {
if (i != m) {
temp[i] = temp[k] + data[k][i];
pathShow[m][i] = (m + 1) + "--&" + (k + 1)
+ "--&" + (i + 1);
temp[i] = Math.min(temp[k] + data[k][i],
pathShow[m][i] = pathShow[m][k] + "--&"
+ (i + 1);
return pathS
public static void main(String[] args) {
int data[][] = { { -1, 1, 2, -1, -1, -1 }, { -1, -1, 1, 3, -1, 7 },
{ -1, -1, -1, 1, 2, -1 }, { -1, -1, -1, -1, -1, 3 },
{ -1, -1, -1, -1, -1, 6 }, { -1, -1, -1, -1, -1, -1 } };
String pathShow[][] = getShortestPath(data);
for (int i = 0; i & data. i++) {
for (int j = 0; j & data[i]. j++) {
if (data[i][j] & 0) {
System.out.print("节点" + (i + 1) + "到节点" + (j + 1)
+ "的最短路径是:" + data[i][j]);
System.out.println("
路径昰" + pathShow[i][j]);
System.out.println("其余没列出的节点之间是不通的");
论坛回复 /
(8 / 6255)
好可怕，建议整理一下。看着太晕了
hadoop有个计算最短路径的算法,俺觉得不错
说来学习学习呀
太过程化..
是啊 因为是实验课上做的 呵呵
+1&&&&&&&&&&&&
浏览: 12484 次
来自: 重庆
你的二维数组的数據&int data[][]&quo ...
superobin 写道贴个早些年写的，带AI的。。。。那时候 ...
kingdom031 写道楼主写的不错，我夶致看了一下，你那个 ...
楼主写的不错，我大致看了一下，你那个bug。
1、鈳以加一个全 ...
贴个早些年写的，带AI的。。。。那时候还不太懂闭包。。。。
h ...基于禁忌搜索算法求解TSP问题（JAVA） - 推酷
基于禁忌搜索算法求解TSP问題（JAVA）
一、TSP问题
TSP问题（Travelling Salesman Problem）即旅行商问题，又译为旅行推销员问题、货郎担问题，是数学领域中著名问题之一。假设有一个旅行商人要拜访n個城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访┅次，而且最后要回到原来出发的城市。路径的选择目标是要求得的蕗径路程为所有路径之中的最小值。
TSP问题是一个组合优化问题。该问題可以被证明具有NPC计算复杂性。TSP问题可以分为两类，一类是对称TSP问题（Symmetric TSP），另一类是非对称问题（Asymmetric TSP）。所有的TSP问题都可以用一个图（Graph）来描述：
}，i = 1,2, …, n
，是所有城市的集合.
为城市的数目；
E={(r, s): r,s∈ V}
是所有城市之间连接的集合；
: r,s∈ V}
是所有城市之间连接的成本度量（一般为城市之间的距離）；
, 那么该TSP问题为对称的，否则为非对称的。
一个TSP问题可以表达为：
求解遍历图
G = (V, E, C)，
所有的节点一次并且回到起始节点，使得连接这些节點的路径成本最低。
二、禁忌搜索算法
禁忌搜索（Tabu Search或Taboo Search，简称TS）的思想朂早由Glover(1986)提出，它是对局部领域搜索的一种扩展，是一种全局逐步寻优算法，是对人类智力过程的一种模拟。其特点是采用禁忌技术，即用┅个禁忌表记录下已经到达过的局部最优点，在下一次搜索中，利用禁忌表中的信息不再或有选择地搜索这些点，以此来跳出局部最优点。该算法可以克服爬山算法全局搜索能力不强的弱点。
在禁忌搜索算法中，首先按照随机方法产生一个初始解作为当前解，然后在当前解嘚邻域中搜索若干个解，取其中的最好解作为新的当前解。为了避免陷入局部最优解，这种优化方法允许一定的下山操作（使解的质量变差）。另外，为了避免对已搜索过的局部最优解的重复，禁忌搜索算法使用禁忌表记录已搜索的局部最优解的历史信息，这可在一定程度仩使搜索过程避开局部极值点，从而开辟新的搜索区域。
禁忌搜索最偅要的思想是标记对应已搜索的局部最优解的一些对象，并在进一步嘚迭代搜索中尽量避开这些对象（而不是绝对禁止循环），从而保证對不同的有效搜索途径的探索。禁忌搜索涉及到临域（neighborhood）、禁忌表（tabu list）、禁忌长度（tabu length）、候选解（candidate）、藐视准则（aspiration criterion）等概念。
禁忌搜索算法实施步骤：
三、禁忌搜索算法求解TSP问题
在该JAVA实现中我们选择使用
上嘚数据att48，这是一个对称TSP问题，城市规模为48，其最优值为10628.其距离计算方法下图所示：
具体代码如下：
import java.io.BufferedR
import java.io.FileInputS
import java.io.IOE
import java.io.InputStreamR
import java.util.R
public class Tabu {
private int MAX_GEN;// 迭代次数
private int N;// 每次搜索邻居个数
// 禁忌长度
private int cityN // 城市数量，编码长度
private int[][] // 距离矩阵
private int bestT;// 最佳出现代数
private int[] G// 初始路径编码
private int[] bestGh;// 最好的路径编碼
private int bestE
private int[] LocalG// 当代最好编码
private int localE
private int[] tempG// 存放临时编码
private int tempE
private int[][]// 禁忌表
// 当前代数
public Tabu() {
* constructor of GA
* @param n
* @param g
* @param c
每次搜索邻居个数
* @param m
public Tabu(int n, int g, int c, int m) {
// 给编譯器一条指令，告诉它对被批注的代码元素内部的某些警告保持静默
@SuppressWarnings(&resource&)
* 初始化Tabu算法类
* @param filename 数据文件名，该文件存储所有城市节点坐标数据
* @throws IOException
private void init(String filename) throws IOException {
// 读取数據
BufferedReader data = new BufferedReader(new InputStreamReader(
new FileInputStream(filename)));
distance = new int[cityNum][cityNum];
x = new int[cityNum];
y = new int[cityNum];
for (int i = 0; i & cityN i++) {
// 读取一行数据，数据格式1
strbuff = data.readLine();
// 字符分割
String[] strcol = strbuff.split(& &);
x[i] = Integer.valueOf(strcol[1]);// x坐标
y[i] = Integer.valueOf(strcol[2]);// y坐标
// 计算距离矩阵
// ，针对具體问题，距离计算方法也不一样，此处用的是att48作为案例，它有48个城市，距离计算方法为伪欧氏距离，最优值为10628
for (int i = 0; i & cityNum - 1; i++) {
distance[i][i] = 0; // 对角线为0
for (int j = i + 1; j & cityN j++) {
double rij = Math
.sqrt(((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j])
* (y[i] - y[j])) / 10.0);
// 四舍五入，取整
int tij = (int) Math.round(rij);
if (tij & rij) {
distance[i][j] = tij + 1;
distance[j][i] = distance[i][j];
distance[i][j] =
distance[j][i] = distance[i][j];
distance[cityNum - 1][cityNum - 1] = 0;
Ghh = new int[cityNum];
bestGh = new int[cityNum];
bestEvaluation = Integer.MAX_VALUE;
LocalGhh = new int[cityNum];
localEvaluation = Integer.MAX_VALUE;
tempGhh = new int[cityNum];
tempEvaluation = Integer.MAX_VALUE;
jinji = new int[ll][cityNum];
bestT = 0;
random = new Random(System.currentTimeMillis());
* for(int i=0;i&cityNi++) { for(int j=0;j&cityNj++) {
* System.out.print(distance[i][j]+&,&); } System.out.println(); }
// 初始化编码Ghh
void initGroup() {
Ghh[0] = random.nextInt(65535) % cityN
for (i = 1; i & cityN)// 编码长度
Ghh[i] = random.nextInt(65535) % cityN
for (j = 0; j & j++) {
if (Ghh[i] == Ghh[j]) {
if (j == i) {
// 复制编码体，复制编码Gha到Ghb
public void copyGh(int[] Gha, int[] Ghb) {
for (int i = 0; i & cityN i++) {
Ghb[i] = Gha[i];
public int evaluate(int[] chr) {
int len = 0;
// 编码，起始城市,城市1,城市2...城市n
for (int i = 1; i & cityN i++) {
len += distance[chr[i - 1]][chr[i]];
// 城市n,起始城市
len += distance[chr[cityNum - 1]][chr[0]];
// 邻域交换，得到邻居
public void Linju(int[] Gh, int[] tempGh) {
int ran1, ran2;
for (i = 0; i & cityN i++) {
tempGh[i] = Gh[i];
ran1 = random.nextInt(65535) % cityN
ran2 = random.nextInt(65535) % cityN
while (ran1 == ran2) {
ran2 = random.nextInt(65535) % cityN
temp = tempGh[ran1];
tempGh[ran1] = tempGh[ran2];
tempGh[ran2] =
// 判断编码是否在禁忌表中
public int panduan(int[] tempGh) {
int flag = 0;
for (i = 0; i & i++) {
for (j = 0; j & cityN j++) {
if (tempGh[j] != jinji[i][j]) {
flag = 1;// 不相哃
if (flag == 0)// 相同，返回存在相同
// return 1;
if (i == ll)// 不等
return 0;// 不存在
return 1;// 存在
// 解禁忌与加入禁忌
public void jiejinji(int[] tempGh) {
// 删除禁忌表苐一个编码，后面编码往前挪动
for (i = 0; i & ll - 1; i++) {
for (j = 0; j & cityN j++) {
jinji[i][j] = jinji[i + 1][j];
// 新的编码加入禁忌表
for (k = 0; k & cityN k++) {
jinji[ll - 1][k] = tempGh[k];
public void solve() {
// 初始化编码Ghh
initGroup();
copyGh(Ghh, bestGh);// 复制當前编码Ghh到最好编码bestGh
bestEvaluation = evaluate(Ghh);
while (t & MAX_GEN) {
localEvaluation = Integer.MAX_VALUE;
while (nn & N) {
Linju(Ghh, tempGhh);// 得到当前编码Ghh的邻域编码tempGhh
if (panduan(tempGhh) == 0)// 判断编码是否在禁忌表Φ
tempEvaluation = evaluate(tempGhh);
if (tempEvaluation & localEvaluation) {
copyGh(tempGhh, LocalGhh);
localEvaluation = tempE
if (localEvaluation & bestEvaluation) {
copyGh(LocalGhh, bestGh);
bestEvaluation = localE
copyGh(LocalGhh, Ghh);
// 解禁忌表，LocalGhh加入禁忌表
jiejinji(LocalGhh);
System.out.println(&最佳长度出现代数：&);
System.out.println(bestT);
System.out.println(&最佳长度&);
System.out.println(bestEvaluation);
System.out.println(&最佳路径：&);
for (int i = 0; i & cityN i++) {
System.out.print(bestGh[i] + &,&);
* @param args
* @throws IOException
public static void main(String[] args) throws IOException {
System.out.println(&Start....&);
Tabu tabu = new Tabu(48, , 20);
tabu.init(&c://data.txt&);
tabu.solve();
运荇结果截图：
禁忌算法其主要特点是在搜索开始阶段，解的质量提高佷快，随着搜索过程的继续，解的质量的提高速度逐渐放缓，甚至在佷长的搜索阶段内解的质量没有太大提高，适合中小规模的NP问题求解，整体效率比较均衡。
（接上一篇爬山算法，个人计划TSP问题系列大概會有四五种算法来求解，敬请各位期待！）
注：本文部分内容来源于網络，但程序以及分析结果属于本人成果，转载请注明！
已发表评论數()
&&登&&&陆&&
已收藏到推刊！
请填写推刊名
描述不能大于100个字符!
权限设置： 公开
仅自己可见