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

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

ただいまの
回答率

90.21%

stepメソッドが何をしているのか分かりません

受付中

回答 1

投稿 編集

  • 評価
  • クリップ 0
  • VIEW 671

randmaster

score 29

前提・実現したいこと

Javaで山登り法というアルゴリズムを用いて,2つの都市を入れ替え続けるというソースコードです.最終的にツアーの経路がより短い物を選ぶというものです. 
HillClimbingクラスのstepメソッドの中身が具体的に何をしているのかが理解できません.どなたか教えていただけると助かります.

該当のソースコード

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() * rnd.nextInt(100);
            double y = rnd.nextDouble() * rnd.nextInt(100);

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

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

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

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

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

    クリップを取り消します

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

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

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

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

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

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

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

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

    質問の評価を下げる

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

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

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

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

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

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

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

    詳細な説明はこちら

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

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

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

回答 1

0

最初にお断りしておきますと、
細部を見るとキリがないので、全体の処理の流れだけ解説します。


Javaは「public static void main(String[] args)」から開始するルールです。
そこでまず、mainメソッドを読むと、

HillClimbing hc = new HillClimbing(points);
hc.run();
hc.showFinalResult();

この三行がメインのメインのようです。
この三行の前は「points」の処理ですが、
それも結局「HillClimbing hc」に渡すための初期化なので。


public void run() {
//略
while (step()) {
//略
public boolean step() {

次に「hc.run()」を見ると、
「step()」がメインループだと分かります。
booleanで返した値が偽のとき、whileループを抜けます。


if (iMaxImprove <= 0)
    return false;
currentState.swap(iMaxImprove, jMaxImprove);
return true;

そこで「step()」を読むと、上が制御部分だと分かります。
「iMaxImprove」がゼロ以下なら偽を返して終了する。
さもなければ、「currentState.swap」を実行し、ループを続行する。

double improvedScore = scoreImprovementIfSwapped(i, j);
if (maxImprove < improvedScore) {

その前の部分はfor文の多重ループで複雑ですが、
ループの前で「iMaxImprove = -1」と代入しているので、
「scoreImprovementIfSwapped」で「maxImprove」を更新することが、
けっきょく全体の処理の流れを制御しています。


最後にまとめると、けっきょくstepとは、
より最適な値を得ながら一段階ずつステップ実行する、
そのループを制御するためのメソッドです。

投稿

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

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

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

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