Paizaの「巡回セールスマン問題」にチャレンジしていて、Scannerの扱い方でまたしてもハマったのでメモメモ。
Paizaはこちらのサイトです。
巡回セールスマン問題
巡回セールスマン問題（じゅんかいセールスマンもんだい、英: traveling salesman problem、TSP）は、都市の集合と各2都市間の移動コスト（たとえば距離）が与えられたとき、全ての都市をちょうど一度ずつ巡り出発地に戻る巡回路の総移動コストが最小のものを求める（セールスマンが所定の複数の都市を1回だけ巡回する場合の最短経路を求める）組合せ最適化問題である。
さすが、Wikipediaさん、載ってます。そして、この「巡回セールスマン問題」、まだ有効な解法が見つかっていない未解決の難問らしいです。様々な解法が研究されてるみたいです。
・百億年かかっても解けない問題 巡回セールスマン問題と遺伝的アルゴリズム | JBpress(日本ビジネスプレス)
し、知らなかった...。だから、Paizaの「巡回セールスマン問題」 もそういったアルゴリズムが存在するっていう紹介みたいな感じだと思います。
PaizaのScanner
「巡回セールスマン問題」以前に、「標準入力」の取得で思いっきりつまづきました。
まず、Paizaでは標準入力を取得するという考え方があるらしい（EclipseでしかScannerを使ったことがない自分にとっては、カルチャーショック）
こんな感じで、与えられる。普通だと、Scannerクラスを使ったらコンソールから入力する形になると思うのですが、Paizaでは、まず、この用意された値を取得することから始めないといけないらしい。（特殊ルール？）
import java.util.*;
import java.awt.Point;
class Main {
// 経路の表示
static void info(int n, List route) {
for (int i=0; i<n; i++) {
System.out.println(route.get(i).x + " " + route.get(i).y);
}
}
public static void main(String[] args) {
// 入力処理
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
List<point> points = new ArrayList<>();
points.add(new Point(0, 0)); // 最初の点として(0, 0)を追加
// ここにコードを記入
for(int i = 0; i < n +1 ; i++) {
// ここでは、要素が3つ、つまり
// 「1 9」、「2 3」、「4 5」
// で取得される、nextLine()は1行分取得だから
String s = scanner.nextLine();
// splitしてlengthを調べてみたら、なぜか「1」、「2」、「2」、「2」となって
// 最初の「1」が謎でした
String[] array = s.split(" ");
if(array.length == 1) {
continue;
} else {
Point p = new Point(Integer.parseInt(array[0]), Integer.parseInt(array[1]));
points.add(p);
}
}
// 経路を表示する
info(n +1, points);
}
}
というコードで一応通るには通ったけど、これ、標準入力の取得とScannerの関係性がいまいちよく分からんです。
貪欲法
「巡回セールスマン問題」 の解法アルゴリズムの1つで、Wikipediaさんによると、
貪欲法は局所探索法と並んで近似アルゴリズムの最も基本的な考え方の一つである。
このアルゴリズムは問題の要素を複数の部分問題に分割し、それぞれを独立に評価を行い、評価値の高い順に取り込んでいくことで解を得るという方法である。動的計画法と異なり保持する状態は常に一つであり、一度選択した要素を再考する事は無い。このため得られる解は最適解であるという保証は無いが部分問題の解法と単純なソートのみでプログラムを実装することが可能であり、多く問題に対して多項式時間での近似アルゴリズムとなる。
問題を複数に分割する方法は特に組合せ最適化問題と相性が良い。問題によっては厳密解（最適解）を得られたりするものや最低限の精度保証（近似度）が算出可能なものもある。このため、現在でもしばしば同問題の研究に用いられている。
となっています。「貪欲法」は必ずしも最適解になるとは限らないと、Paizaの動画で紹介されてました。どいういうことかというと、現在地から一番近い通路を優先して選択していくと、
というような場合があるとのこと、確かに、これは「貪欲法」を使っていると回避できないですね、「巡回セールスマン問題」 激ムズですね。
Paizaで紹介されていた「貪欲法」の演習課題では、
import java.util.*;
import java.awt.Point;
class Main {
// 2点間の距離
static double distancePoint(Point p, Point q) {
// return Math.sqrt((p.x-q.x)*(p.x-q.x)+(p.y-q.y)*(p.y-q.y));
return p.distance(q);
}
// 経路の表示
static void info(int n, List<Point> route) {
for (int i=0; i<n; i++) {
System.out.println(route.get(i).x + " " + route.get(i).y);
}
}
// pointsを並べ替えた経路
static List<Point> tsp(int n, List<Point> points) {
List<Point> resultRoute = new ArrayList<>(); // 結果を保存
List<Point> openPoints = new ArrayList<>(points); // 未訪問の点の一覧
resultRoute.add(openPoints.remove(0));
while (!openPoints.isEmpty()) {
// a: 今いる点, b: 移動候補の点
Point a = resultRoute.get(resultRoute.size()-1);
Point b = null;
// 全ての未訪問の点について、aとの距離を調べ、最も距離の短い点をbとする
for (Point p : openPoints) {
if (b == null || distancePoint(a, p) < distancePoint(a, b)) {
b = p;
}
}
resultRoute.add(b);
openPoints.remove(b);
}
return resultRoute;
}
public static void main(String[] args) {
// 入力処理
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
List<Point> points = new ArrayList<>();
points.add(new Point(0, 0)); // 最初の点として(0, 0)を追加
for (int i=0; i< n +1; i++) {
String s = scanner.nextLine();
String[] array = s.split(" ");
if(array.length == 1) {
continue;
} else {
Point p = new Point(Integer.parseInt(array[0]), Integer.parseInt(array[1]));
points.add(p);
}
}
// 座標を並べ替えた経路を作る
List<Point> resultRoute = tsp(n+1, points);
// 経路を表示する
info(n+1, resultRoute);
}
}
2問目は、
import java.util.*;
import java.awt.Point;
class Main {
// 2点間の距離
static double distancePoint(Point p, Point q) {
// return Math.sqrt((p.x-q.x)*(p.x-q.x)+(p.y-q.y)*(p.y-q.y));
return p.distance(q);
}
// 経路の表示
static void info(int n, List<Point> route) {
for (int i=0; i<n; i++) {
System.out.println(route.get(i).x + " " + route.get(i).y);
}
}
// pointsを並べ替えた経路
static List<Point> tsp(int n, List<Point> points) {
List<Point> resultRoute = new ArrayList<>(); // 結果を保存
List<Point> openPoints = new ArrayList<>(points); // 未訪問の点の一覧
resultRoute.add(openPoints.remove(0));
while (!openPoints.isEmpty()) {
// a: 今いる点, b: 移動候補の点
Point a = resultRoute.get(resultRoute.size()-1);
Point b = null;
// 全ての未訪問の点について、aとの距離を調べ、最も距離の短い点をbとする
for (Point p : openPoints) {
if (b == null || distancePoint(a, p) < distancePoint(a, b) ) {
b = p;
}
}
resultRoute.add(b);
openPoints.remove(b);
}
return resultRoute;
}
public static void main(String[] args) {
// 入力処理
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
List<Point> points = new ArrayList<>();
points.add(new Point(0, 0)); // 最初の点として(0, 0)を追加
for (int i=0; i<n; i++) {
Point p = new Point(scanner.nextInt(), scanner.nextInt());
points.add(p);
}
// 座標を並べ替えた経路を作る
List<Point> resultRoute = tsp(n+1, points);
// 経路を表示する
info(n+1, resultRoute);
}
}
普通に、「標準入力」の取得をしないでもいけました、最初の頑張りは何だったんだろう。一応、認定書いただきました、ありがとうございます。
今回はこのへんで。
