アルゴリズム入門編:貪欲法を考えよう

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) {
        return points;
    }
    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) {
        return points;
    }
    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会員登録が必要です

Tips

次のチャプターへ前のチャプターへ

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

会員登録する

＃07:貪欲法を考えよう

このチャプターでは巡回セールスマン問題を解くための貪欲法のロジックを考えて、コメントとして整理します。

貪欲法

貪欲法 - Wikipedia
https://ja.wikipedia.org/wiki/%E8%B2%AA%E6%AC%B2%E6%B3%95

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

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

コードの実行

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

出力タイプ：