アルゴリズム入門編:貪欲法で解いてみよう

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 double distanceRoute(int n, List<Point> route) {
        double sum = 0;
        for (int i=0; i<n-1; i++) {
            sum += distancePoint(route.get(i), route.get(i+1));
        }
        return sum;
    }
    // 経路の表示
    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);
        }
        System.out.println("distance: " + distanceRoute(n, route));
    }
    // pointsを並べ替えた経路
    static List<Point> tsp(int n, List<Point> points) {
        List<Point> resultRoute = new ArrayList<>(); // 結果を保存
        // 現在いる点から一番近い未訪問の点を選んで移動する操作を繰り返して全ての点を訪問したい
        // openPoints: 未訪問の点の一覧
        // while (openPointsが空でない) {
        //     a: 今いる点, b: 移動候補の点
        //     全ての未訪問の点について、aとの距離を調べ、最も距離の短い点を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);
    }
}

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 double distanceRoute(int n, List<Point> route) {
        double sum = 0;
        for (int i=0; i<n-1; i++) {
            sum += distancePoint(route.get(i), route.get(i+1));
        }
        return sum;
    }
    // 経路の表示
    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);
        }
        System.out.println("distance: " + distanceRoute(n, route));
    }
    // pointsを並べ替えた経路
    static List<Point> tsp(int n, List<Point> points) {
        List<Point> resultRoute = new ArrayList<>(); // 結果を保存
        // 現在いる点から一番近い未訪問の点を選んで移動する操作を繰り返して全ての点を訪問したい
        // openPoints: 未訪問の点の一覧
        // while (openPointsが空でない) {
        //     a: 今いる点, b: 移動候補の点
        //     全ての未訪問の点について、aとの距離を調べ、最も距離の短い点を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);
    }
}

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);
        }
        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);
    }
}

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);
        }
        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);
    }
}

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 || ここにコードを書く ) {
                    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);
    }
}

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 || ここにコードを書く ) {
                    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);
    }
}

この動画を見るには

paiza会員登録が必要です

演習1
演習2

問題ログインすると模範解答や入力を見ることができます

演習課題「ループで入力を取得しよう」

以下のフォーマットに沿って入力が行われます。

n　（n 訪問点数）
x_1 y_1　（x_1 は訪問点の x 座標、 y_1 訪問点の y 座標）
x_2 y_2　（x_2 は訪問点の x 座標、 y_2 訪問点の y 座標）
・・・
x_n y_n　（x_n は訪問点の x 座標、 y_N 訪問点の y 座標）

右のコードエリアのプログラムは、訪問点の座標一覧を取得して、
貪欲法にもとづいて巡回する順序を(0,0)から出力するプログラムです。
しかし、このまま実行してもエラーになってしまいます。
このプログラムを修正して、正しく表示されるようにしてください。
プログラムを実行して、正しく出力されれば演習課題クリアです！

入力される値

3
1 9
2 3
4 5

標準入力からの値取得方法はこちらをご確認ください

期待する出力値

0 0
2 3
4 5
1 9

問題ログインすると模範解答や入力を見ることができます

演習課題「ループで入力を取得しよう」

以下のフォーマットに沿って入力が行われます。
```
n　（n 訪問点数）
x_1 y_1　（x_1 は訪問点の x 座標、 y_1 訪問点の y 座標）
x_2 y_2　（x_2 は訪問点の x 座標、 y_2 訪問点の y 座標）
・・・
x_n y_n　（x_n は訪問点の x 座標、 y_ 訪問点の y 座標）
```
右のコードエリアのプログラムは、訪問点の座標一覧を取得して、
貪欲法にもとづいて巡回する順序を(0,0)から出力するプログラムです。
しかし、このまま実行してもエラーになってしまいます。
このプログラムを修正して、正しく表示されるようにしてください。
プログラムを実行して、正しく出力されれば演習課題クリアです！

入力される値

3
1 9
2 3
4 5

標準入力からの値取得方法はこちらをご確認ください

期待する出力値

0 0
2 3
4 5
1 9

Tips

動画へ戻る

前のチャプターへ

※paizaに会員登録すると無料で動画学習コンテンツをご利用いただけます

会員登録する

＃08:貪欲法で解いてみよう

このチャプターでは貪欲法を使って巡回セールスマン問題を解くプログラムを完成させます。

入力値

参考になるウェブサイト

拡張for文(for-each文) - 繰り返し処理 - Java入門
https://www.javadrive.jp/start/for/index8.html

学びを深めるためのキーワードの紹介

本レッスンでは、貪欲法による最近傍(Nearest Neighbor)法と呼ばれるアルゴリズムについて学んできました。
巡回セールスマン問題の貪欲法のアルゴリズムは他にもいくつか有名なものがあり、特に近傍挿入法(Nearest Insertion)法は有名です。

2-opt法や3-opt法などのk-opt法は、実装が比較的簡単な、巡回セールスマン問題の局所解探索アルゴリズムです。
焼きなまし法やタブーサーチなどの局所解探索アルゴリズムとして有名な手法を利用してみるのも良いでしょう。

厳密な解の求め方としては、ビット列を利用した動的計画(DP)法による解法が15頂点程度までのデータに対して、現実的な時間で解を求められることが知られています。
また、整数計画法と分枝限定法を組み合わせた手法では、より多くの頂点をもつデータに対して厳密解を求めることができます。

プログラミング学習 > アルゴリズム入門編 > アルゴリズム入門編: 「巡回セールスマン問題」を学ぶ > 貪欲法で解いてみよう

ログインすると採点できます

コードの実行

有料会員になるとエンジニアに質問ができます

出力タイプ：