巡回セールスマン問題

質問

このプログラミングを実際に視覚的（探索している状況など）に表したいんですが、どのようにすべきなのでしょうか？
いろいろ参考書を見たのですが、わかりませんでした。

import java.io.*;
public class TSP {
public static void main(String[] args) {

TSP instance = new TSP();

TspPoint[] points = new TspPoint[5];

//コンポーネントの作成
points[0] = new TspPoint("A", 5, 10);
points[1] = new TspPoint("B", 4, 2);
points[2] = new TspPoint("C", 6, 3);
points[3] = new TspPoint("D", 3, 4);
points[4] = new TspPoint("E", 2, 7);

instance.setPoints(points);
instance.traveling();
instance.dispResult();

}

private TspPoint[] points;
private double min_distance;
private int[] min_route;

public void setPoints(TspPoint[] points) {
this.points = points;
}

public void traveling() {
min_distance = Double.MAX_VALUE;
min_route = new int[points.length];

int p1, p2, p3, p4, p5;

p1 = 0;
for (p2 = 1; p2 < 5; p2++) {
for (p3 = 1; p3 < 5; p3++) {
for (p4 = 1; p4 < 5; p4++) {
for (p5 = 1; p5 < 5; p5++) {
if (p1 == p2 || p1 == p3 || p1 == p4 || p1 == p5
|| p2 == p3 || p2 == p4 || p2 == p5 || p3 == p4
|| p3 == p5 || p4 == p5) {
// 重複する地点は対象外
} else {
// p1→p2→p3→p4→p5→p1への巡回経路長を求める
double distance = 0.0;
distance += calcDistance(points[p1], points[p2]);
distance += calcDistance(points[p2], points[p3]);
distance += calcDistance(points[p3], points[p4]);
distance += calcDistance(points[p4], points[p5]);
distance += calcDistance(points[p5], points[p1]);
if (distance < min_distance) {
// 現在のところの最短経路を覚えておく
min_route[0] = p1;
min_route[1] = p2;
min_route[2] = p3;
min_route[3] = p4;
min_route[4] = p5;
// 最短距離を記憶する
min_distance = distance;
}
}
}
}
}
}
}

public void dispResult() {

System.out.print("最小の巡回経路は ");
for (int i = 0; i < 5; i++) {
System.out.print(points[min_route[i]].toString() + " → ");
}
System.out.println(points[min_route[0]].toString());

System.out.println("巡回経路長は " + min_distance);
}

public double calcDistance(TspPoint a, TspPoint b) {
double temp;
temp = (a.getX() - b.getX()) * (a.getX() - b.getX())
+ (a.getY() - b.getY()) * (a.getY() - b.getY());
return Math.sqrt(temp); //平方根を返す
}

}

class TspPoint {
private String name;
private int x;
private int y;

public TspPoint(String name, int x, int y) {
this.name = name;
this.x = x;
this.y = y;
}

public String getName() {
return name;
}

public int getX() {
return x;
}

public int getY() {
return y;
}

public String toString() {
return name + "(" + x + "," + y + ")";
}

}

回答No.3

komi1341

http://www.javaroad.jp/bbs/answer.jsp?q_id=20090929014231540

マルチポストは迷惑行為です。ネチケットは読まれましたか？
下記ＵＲＬはここへの投稿前に読むよう求められているものです。

http://help.okwave.jp/msncom/beginner/netiquette.html

それと「全部ソース書いてください」は普通、無料で他人に頼めることではありません。予算を提示すれば、どなたか請け負ってくれるかもしれませんね。

既存のソースコードで勉強したいなら、「アプレット」「ソースコード」などで検索すれば出てくるのではないでしょうか？　他のアルゴリズムの表示サンプルであっても十分参考になるでしょう。

お礼

以後このような類の書き込みはしません。
因みに今回のソースは
http://detail.chiebukuro.yahoo.co.jp/qa/question_detail/q1321942563
を参照させていただきました。

補足

知らなかったです。
マナー違反してしまい、申し訳ありません。

回答No.2

komi1341

簡単なアプレットなら作れるんですね。
それならあとはJavaの問題というより見せ方の問題になるので、どう見せたいか、何を見せたいか次第だと思います。
適当に各地点を表す丸か何かと、それらの繋がりを示す線をまず描画して、現在の最短経路が求まるたびにその経路を別の色で表示してやれば、それなりになるでしょう。

TspPointクラスにgetterメソッドが作られているところなどを見ると、それなりにプログラミングに慣れた方ですよね？　描画したいタイミングでアプレットのrepaint()を呼んでやるだけでいけると思いますよ。計算が速すぎて途中経過の絵が見えない場合は、repaint()のあとでThread.sleep()を呼んでわざと処理を休止させればよいです。sleep()の使い方もアプレットの本にはだいたい載っているはずです。

補足

ありがとうございます。
やっぱり演習問題不足のせいかどうやるかわかりません。
ソースコードをのっけていただけると助かります。
今後の勉強に役立てます。
宜しくお願いします。

回答No.1

komi1341

参考になる資料が多そうなのは、アプレットでしょうか。
アプレットを使えば、画面を作ってそこに図形や画像を描画したり、それらをアニメーションさせたり、さらにそのアプリをWebで公開したり、といったことが簡単にできます。「Javaアプレットでアニメーションアプリを作ってみよう！」みたいな本や資料がたくさんあるので、それらを参考に描画方法を勉強してみてください。

あと細かいことですが

> import java.io.*;

この文は不要では？
アプレットはファイル操作に制限があったりするので、もし使う予定があるならそのあたりも勉強しておくとよいです。

お礼

ありがとうございます。
参考書探してみます。
ａｐｐｌｅｔの本読んだんですが、ごく簡単なものはできるんですが、
このプログラムからとなるとどう手をつければよいかわかりません。