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

Question

###前提・実現したいこと

Javaで山登り法を用いて，２つの都市を入れ替え続けるソースコードを書きました．最終的にツアーの経路がより短い物を選ぶというものです．
エラーメッセージは出ていないのですが，毎回ランダムの乱数を作っているはずなのに，同じベストスコア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 を返す。
    // ２つ選んで良くなるものを交換する、ということを繰り返す。
    // 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 {
    // 現在の状態集合の中で最もよいものを得る。１つしかなければそれを返す。
    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/ツール等のバージョンなど)
より詳細な情報

Comments

[abs123]

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

[randmaster]

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

Answer 1

最初に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]

Comments

[randmaster]

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