0

最近傍ヒューリスティックを実装する学校向けのプロジェクト(私はすでに行っています)と、徹底的な検索を行う巡回セールスマン問題(アルゴリズム、時間計算量などを分析します)を実行します。私たちの先生は、最近傍部分のように全体をプログラミングするのではなく、全数検索部分に使用(または変更)するコードを探し回ると言いました。私は周りを見回して、私たちがプログラムを実行するように指示された方法に関係のないものだけを見つけました。整数を使用する一般的な問題とは対照的に、ポイント(x、y)を使用しています。私の目標は、最短の順列を計算し、その順列が何であるかを知ることができるようにすることです。だから私は配列の配列(順列を含む)を持つことを考えています。

誰かが徹底的な検索で私を手伝ってくれるなら、それは素晴らしいことです。

これが私のコードからの抜粋です(メンバー変数、2つのポイント間の距離を計算する関数、およびすべてのポイントが格納されている場所):

private int x;
private int y;
private boolean visited;

public double dist( point pt ){
    int xdist = this.getX() - pt.getX();
    int ydist = this.getY() - pt.getY();
    double xsr = xdist*xdist;
    double ysr = ydist*ydist;
    return Math.sqrt( xsr + ysr );
}

point[] points = new point[n];

どんな助けでも大歓迎です。

4

2 に答える 2

1

単一のTSPで可能な解決策は、基本的に、開始都市なしで、それらを訪問する順序を表す都市の配列にすぎません。

したがって、n(都市の数)= 5と仮定します。次に、単一の可能な解が長さ4の配列として表されます。ここで、都市[B、C、D、E]を注文する方法はいくつありますか。BCDE、BCED、BDCE、BDEC、...それは4!24の組み合わせです。したがって、nの都市では(n-1)!組み合わせが得られます。362880の組み合わせを作成する10都市の場合。20の都市または10^17の組み合わせの場合、それらすべてをメモリに保持したい場合は、メモリが不足します。

追加の問題は、n個のネストされたforループが必要になることですが、n個あるため、これらのforループを記述することは不可能です。(書き始めることができfor() for() for() ...ます。したがって、実装にはおそらく、ある種のウォーカー アプローチが必要になります。このアプローチでは、配列内の1つのインデックスを表す各桁を持つデジタル時計のように、すべての組み合わせをチェックする単一のループがあります。

于 2012-09-06T06:42:09.203 に答える