2

私は大学の TSP プログラムについて頭を悩ませようとしていますが、非常に難しいことを認めざるを得ません。

基本的に、Haversine を使用して、Lat 値の配列と Lng 値の配列があり、距離を行列に変換しました。
さて、ここからどこへ行こう？
80 の町すべてを訪れて、最短距離を見つけなければなりません。最善の方法を考えようと思います。最近傍アルゴリズムを作成する必要がありますか? 順列を保存して距離を合計するだけですか。またはより良い方法はありますか？正直、1年生にはちょっと難しいと思います！とにかく、ここに私のコードがあります、それはひどいです、アプレットなどは私たちに与えられました.

public class Brain {

    //These are the names of the 80 towns and their north and west GPS co-ordinates

    static double north[] = {53.855,52.794,54.350,53.433,52.992,54.117,53.328,54.800,54.863,55.071,54.502,54.343,51.746,54.660,51.680,54.597,53.091,53.175,55.136,52.831,53.976,53.944,53.861,53.991,51.622,52.354,51.897,54.996,54.322,53.714,53.348,54.009,54.500,52.085,53.345,52.846,52.502,54.345,53.272,52.677,53.728,53.106,52.648,52.059,51.708,53.783,54.851,54.957,55.053,52.665,52.447,53.727,53.197,51.904,54.750,52.131,53.382,52.266,54.248,53.116,53.522,52.863,52.396,54.210,52.451,54.590,53.633,52.714,54.267,53.245,54.830,52.679,52.474,52.268,53.515,53.267,52.257,53.800,52.334,51.952};
    static double west[] = {-6.538,-6.165,-6.655,-7.950,-6.987,-9.167,-8.219,-7.790,-6.284,-6.508,-8.190,-6.260,-8.735,-5.670,-9.453,-5.930,-7.913,-6.525,-7.456,-6.932,-6.719,-8.095,-9.299,-7.360,-8.886,-7.712,-8.470,-7.307,-5.703,-6.350,-6.260,-6.405,-6.770,-7.640,-7.051,-8.981,-6.566,-7.640,-9.049,-6.292,-6.878,-6.065,-7.256,-9.507,-8.531,-8.917,-5.811,-7.720,-6.946,-8.624,-9.486,-7.800,-8.567,-8.957,-6.610,-8.642,-6.591,-8.270,-6.971,-7.324,-7.338,-8.200,-6.945,-5.882,-9.055,-7.290,-8.183,-8.869,-8.483,-9.306,-7.470,-7.814,-8.162,-9.696,-8.851,-7.500,-7.129,-9.533,-6.458,-7.846};
    String names[] = {"Ardee","Arklow","Armagh","Athlone","Athy","Ballina","Ballinasloe","Ballybofe","Ballymena","Ballymoney","Ballyshannon","Banbridge","Bandon","Bangor","Bantry","Belfast","Birr","Blessington","Buncrana","Carlow","Carrickmacross","Carrick-On-Shannon","Castlebar","Cavan","Clonakilty","Clonmel","Cork","Derry","Downpatrick","Drogheda","Dublin","Dundalk","Dungannon","Dungarvan","Edenderry","Ennis","Enniscorthy","Enniskillen","Galway","Gorey","Kells","Kilcoole","Kilkenny","Killarney","Kinsale","Knock","Larne","Letterkenny","Limavady","Limerick","Listowel","Longford","Loughrea","Macroom","Magherafelt","Mallow","Maynooth","Mitchelstown","Monaghan","Mountmellick","Mullingar","Nenagh","New-Ross","Newcastle","Newcastle-West","Omagh","Roscommon","Shannon","Sligo","Spiddal","Strabane","Thurles","Tipperary","Tralee","Tuam","Tullamore","Waterford","Westport","Wexford","Youghal"};
    static double[][] matrix = new double[80][80];
    boolean visit[]=new boolean[80];
    boolean valid = true;

    public static void fillmatrix (){
        double tote = 0;
        for(int i=1;i<80;i++){
            for(int j=1;j<80;j++){
                matrix[i][j]=getDistance(north[i],west[j],north[j],west[j]);
            }
        }
    }

    public String compute () {          
        String solution ="";
        for (int i=0;i<80;i++){
            solution+=(char)(i+40);
        }
        solution+="Anything you add on after the 80 characters will be " + 
            "printed in the textbox (e.g. you can compute the distance)";
        return solution;    
    }

    public static double getDistance(double lat1, double lon1, double lat2, double lon2){
        double R = 6371;
        double dLat = Math.toRadians((lat2-lat1));
        double dLon = Math.toRadians((lon2-lon1)); 
        double a = Math.sin(dLat/2) * Math.sin(dLat/2) + 
            Math.cos(Math.toRadians(lat1)) * Math.cos(Math.toRadians(lat2)) *
            Math.sin(dLon/2) * Math.sin(dLon/2); 
        double c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1-a)); 
        double d = R * c;         
        return d;
    }    
}
4

3 に答える 3

1

すべての順列をチェックすると、非常に小さなインスタンス以外では法外なコストがかかります。

幸いなことに、TSP にはよく知られたヒューリスティック アルゴリズムがたくさんあります。あなたの選択をしてください。

于 2012-05-03T17:14:05.450 に答える
1

最近傍ヒューリスティックに取り組む最善の方法は、アルゴリズムをサブ問題に分解することです。

  1. ランダムな都市を選択します。
  2. 最も近い未訪問の都市を見つけてそこに行きます。
  3. まだ訪れていない都市はありますか？はいの場合は、手順 2 を繰り返します。
  4. 最初の都市に戻ります。

次に、各サブ問題を解決します。

  1. 名前の配列でランダムな値を選択します
  2. 北と西の配列を反復処理して距離を計算することにより、ランダムな都市までの距離をすべての都市で確認します。訪問した都市を配列に格納します。
  3. 繰り返し 2
  4. 最初の都市に戻る

次に、疑似コードについて考え、Java コードを作成してみます。

于 2012-05-03T17:41:04.053 に答える
0

ソースコードについて

最初に、都市座標の定義を City クラスに変更することをお勧めします。都市は事前に定義されているため、外部ファイルに「エクスポート」して、ファイルの開始時にロードすることをお勧めします。例えば、

public class City{
    public double North;
    public double West;
    public String Name;
    public double getDistanceToCity(City target){
        double R = 6371;
        double dLat = Math.toRadians((target.North-this.North));
        double dLon = Math.toRadians((target.West-this.West)); 
        double a = Math.sin(dLat/2) * Math.sin(dLat/2) + 
            Math.cos(Math.toRadians(this.North)) * Math.cos(Math.toRadians(this.West)) *
            Math.sin(dLon/2) * Math.sin(dLon/2); 
        double d = R * 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1-a));         
        return d;}}

次に、たとえば、ファイルを「ArrayList Cities」に読み込んだ後、次のようにマトリックスをビルドします。

double[][] distances = new double[Cities.size()][Cities.size()];
int i=0;
int j=0;
for(City start:Cities){
    for(City end:Cities){
        distances[i][j]=start.getDistanceToCity(end);
        j++;}
    i++;}

そして、同じ行列を取得します。この場合、入力データのサイズを変更できます。たとえば、10 都市でアルゴの正確性をテストし、結局 80 で問題なく動作します。さらに、この場合、この問題の難しさを自分で確認できます。単純に40 と 41 の都市で実行します...

次に、アルゴリズムについて...

これは NP 困難な問題であるため、順列は非常に長い時間機能します。Held–Karp アルゴリズムをお勧めします。これははるかに高速ですが、実現がかなり難しく、多くのメモリを必要とします。(たとえば、(n*n*2^n) の場合、n=80 の場合は 10^27 であり、順列は n! であり、n=80 の場合は 10^121 の場合に推奨される方法 - タスクを解決するために必要な操作を意味します) .

いずれにせよ、今のところ最良の正確な解決策は線形計画法です（正確な方法は思い出せませんが...）。グラフメソッドの使用を検討しているアルゴリズムが見つかるかもしれません。

于 2012-05-04T14:14:54.973 に答える