質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

90.03%

山登り法というアルゴリズムのプログラムについてです.教えてください

解決済

回答 1

投稿 編集

  • 評価
  • クリップ 0
  • VIEW 1,893

randmaster

score 29

前提・実現したいこと

Javaで山登り法を用いて,2つの都市を入れ替え続けるソースコードを書きました.最終的にツアーの経路がより短い物を選ぶというものです.
エラーメッセージは出ていないのですが,毎回ランダムの乱数を作っているはずなのに,同じベストスコア5.0と文字化けのような文字が出ます.
HillClimbingクラスのmain文をどう書けばいいのかが分かりません.

発生している問題・エラーメッセージ

エラーは出ないですが,毎回これになります…

maxImprove = 0.000000, i = -1, j = -1
Best found score: 5.0
tsp.Point@2c091cee
tsp.Point@a4a63d8
tsp.Point@19e0ff2f
tsp.Point@29173ef
tsp.Point@1b52513a

該当のソースコード

package tsp.impl;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

import tsp.AbstractTSPSolver;
import tsp.Point;

public class HillClimbing extends AbstractTSPSolver {
    public HillClimbing(List<Point> points) {
        super(points);
    }

    @Override
    public void run() {
        if (this.currentState.getPoints().size() <= 3)
            return;

        while (step()) {
            System.out.println("crimb.");
        }
    }

    // 1 step 進め、解が改ざんされたならば true を返す。
    // 2つ選んで良くなるものを交換する、ということを繰り返す。
    // i, j が並んでいる時は、(j == i + 1 とする)
    // i-1, i, j, j+1 が、i-1, j, i, j + 1 になるので、
    //  -d(i-1, i)-d(i+1,i+2)
    //  +d(i-1, i+1)+d(i,i+2)

    // 並んでいないときは、
    // i-1, i, i + 1, ..., j - 1, j, j + 1
    // -d(i-1, i)-d(i, i+1)-d(j-1, j)-d(j, j+1)
    // +d(i-1, j)+d(j, i+1)+d(j-1, i)+d(i, j+1)

    public boolean step() {
        final int N = currentState.size();

        double maxImprove = 0;
        int iMaxImprove = -1, jMaxImprove = -1;

        // points[0] の位置は固定にする。
        for (int i = 1; i < N - 1; ++i) {
            for (int j = i + 1; j < N; ++j) {
                double improvedScore = scoreImprovementIfSwapped(i, j);
                if (maxImprove < improvedScore) {
                    maxImprove = improvedScore;
                    iMaxImprove = i;
                    jMaxImprove = j;
                }
            }
        }

        System.out.printf("maxImprove = %f, i = %d, j = %d\n",  maxImprove, iMaxImprove, jMaxImprove);

        if (iMaxImprove <= 0)
            return false;

        currentState.swap(iMaxImprove, jMaxImprove);
        return true;
    }

    public double scoreImprovementIfSwapped(int i, int j) {
        assert (i < j);
        if (j == i + 1) {
            double removedDist = currentState.distance(i-1,i) + currentState.distance(i+1,i+2);
            double addedDist = currentState.distance(i-1, i+1) + currentState.distance(i, i+2);
            double improvedDist = removedDist - addedDist;
            return improvedDist;
        } else {
            double removedDist = currentState.distance(i-1, i) + currentState.distance(i, i+1) + currentState.distance(j-1, j) + currentState.distance(j, j+1);
            double addedDist = currentState.distance(i-1, j) + currentState.distance(j, i+1) + currentState.distance(j-1, i) + currentState.distance(i, j+1);
            double improvedDist = removedDist - addedDist;
            return improvedDist;
        }
    }

    public static void main(String[] args) {

        List<Point> points = new ArrayList<Point>();

        for (int i = 0; i < 5; i++) {

            //Randomクラスのインスタンス化
            Random rnd = new Random();

            double x = rnd.nextDouble();
            double y = rnd.nextDouble();

            Point p = new Point(x, y);

            points.add(i, p);


        }

        HillClimbing hc = new HillClimbing(points);

        hc.run();
        hc.showFinalResult();

    }

}

package tsp;

import java.util.List;

public abstract class AbstractTSPSolver implements TSPSolver {
    protected TSPState currentState;

    protected AbstractTSPSolver(List<Point> points) {
        this.currentState = new TSPState(points);
    }

    @Override
    public final TSPState getBestState() {
        return currentState;
    }

    public final void showFinalResult() {
        System.out.println("Best found score: " + currentState.getScore());

        for (Point p : currentState.getPoints())
            System.out.println(p);
    }

    public abstract void run();
    public abstract boolean step();

}


package tsp;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class TSPState {
    private final ArrayList<Point> points;
    private boolean scoreCalculated = false;
    private double score;

    public TSPState(List<Point> points) {
        this.points = new ArrayList<Point>(points);
        this.scoreCalculated = false;
        this.score = 0;
    }

    public TSPState(TSPState s) {
        this.points = new ArrayList<Point>(s.getPoints());
        this.scoreCalculated = s.scoreCalculated;
        this.score = s.score;
    }

    public int size() {
        return points.size();
    }

    public List<Point> getPoints() {
        return Collections.unmodifiableList(points);
    }

    public List<Point> getMutablePoints() {
        scoreCalculated = false;
        return points;
    }

    public double getScore() {
        if (!scoreCalculated) {
            score = calculateScore();
            scoreCalculated = true;
        }

        return score;
    }

    private double calculateScore() {
        if (points.size() <= 1)
            return 0;

        double sumDistance = 0;
        for (int i = 1; i < points.size(); ++i) {
            Point p1 = points.get(i - 1);
            Point p2 = points.get(i);

            sumDistance += p1.attDistance(p2);
        }

        sumDistance +=
                points.get(0).attDistance(points.get(points.size() - 1));
        return sumDistance;

    }

    // 点P_1とP_jの距離を返す
    public double distance(int i, int j) {
        Point p1 = points.get(i % points.size());
        Point p2 = points.get(j % points.size());
        return p1.attDistance(p2);
    }

    // 点Pi, Pjを入れ替える
    public void swap(int i, int j) {
        Point p = points.get(i);
        points.set(i, points.get(j));
        points.set(j, p);

        scoreCalculated = false;
    }


}


package tsp;

public interface TSPSolver {
    // 現在の状態集合の中で最もよいものを得る。1つしかなければそれを返す。
    public TSPState getBestState();

    // 計算を 1step 進める
    public abstract boolean step();
}

package tsp;

public class Point {
    public double x, y;
    public Point(double x, double y) {
        this.x = x;
        this.y = y;
    }

    public double distance(Point p) {
        double dx = x - p.x;
        double dy = y - p.y;
        return Math.sqrt(dx * dx + dy * dy);
    }

    public double attDistance(Point p) {
        double dx = x - p.x;
        double dy = y - p.y;
        double r = Math.sqrt((dx * dx + dy * dy) / 10);
        double t = Math.round(r);
        if (t < r)
            return t + 1;
        else
            return t;
    }

}

試したこと

main文でSystem.out.println(hc.step());としても結果はfalseと出るだけでした.
あとはPointクラスのコンストラクタで乱数がちゃんと生成されているかも確認しましたが,正常に生成されていました.

補足情報(言語/FW/ツール等のバージョンなど)

より詳細な情報

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

質問への追記・修正、ベストアンサー選択の依頼

  • abs123

    2016/09/06 19:59

    TSPStateクラスのコードを追加してください。

    キャンセル

  • randmaster

    2016/09/06 20:07

    失礼いたしました.追加しました

    キャンセル

回答 1

checkベストアンサー

0

最初にPointのリストを作ってますが、Pointのx, yは0.0から1.0の範囲で使う想定なのですか?
以下で試したら、結果は変わりました。

// 試しに変更
            double x = rnd.nextDouble() * rnd.nextInt(100);
            double y = rnd.nextDouble() * rnd.nextInt(100);

Pointクラスですが、toString()メソッドをオーバライドしないため、意図していない表示になっているようです。Eclipseだと以下のように自動で追加するメニューがあります。

// 追加
    @Override
    public String toString() {
        return "Point [x=" + x + ", y=" + y + "]";
    }

上記変更をした時の結果の一例です。

maxImprove = 2.000000, i = 3, j = 4
crimb.
maxImprove = 0.000000, i = -1, j = -1
Best found score: 60.0
Point [x=0.3044315899218193, y=64.43968556761287]
Point [x=27.97325259991755, y=74.05875329212344]
Point [x=42.865450704182685, y=15.452900591989147]
Point [x=2.883819982780386, y=13.108287501315047]
Point [x=1.918928403948095, y=17.61555117140871]

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2016/09/12 21:09

    感謝いたします.
    ありがとうございました.

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 90.03%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

同じタグがついた質問を見る