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

Question

###前提・実現したいこと
Javaで山登り法というアルゴリズムを用いて，２つの都市を入れ替え続けるというソースコードです．最終的にツアーの経路がより短い物を選ぶというものです．
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 を返す。
    // ２つ選んで良くなるものを交換する、ということを繰り返す。
    // 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 {
    // 現在の状態集合の中で最もよいものを得る。１つしかなければそれを返す。
    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 + "]";
    }

}

Answer 1

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

---

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とは、
より最適な値を得ながら一段階ずつステップ実行する、
そのループを制御するためのメソッドです。