【ダイナミックプランニング】バイナリ思考でTSP(旅行者問題)最短経路とその長さを巧みに解く(C++)

30289 ワード
Algorithm
考え方の参考:https://blog.csdn.net/joekwok/article/details/4749713
ネット上で1周見て、比較的に優雅な旅行者の問題の動態的な計画のC++コードがないことを発見して、そこで1篇のブログを書いて分かち合って、まずこの上を見て参考の構想に言及することを提案して、それから本文のコードを見ます.
マクロ表示の都市個数N,グローバル変数表示の重み付き距離行列distances[N][N]を異なる重み付きマップに対して修正することで異なるTSP(旅行者問題)を解決できるように,上のリンクコードを改良した.このコードではdistances[N][N]は乱数で生成され,必要に応じて変更できる.
メモリの制限のため、本コードは都市の個数N≦le≦15の時に正常に運行します;都市数N>>15の場合、ファイルにデータを格納し、ファイルを読み込むことで実現することを推奨します.
コードの鍵は、都市集合をバイナリ01で表すことであり、例えば、都市1,2,3からなる集合{1,2,3}{1,2,3}{1,2,3}、バイナリ111 111 111 111で表す、すなわち、10進数の7 7 7 7,7,2次元配列dpの7列目である.都市1,3からなる集合{1,3}{1,3}{1,3}については、10進法の5 5 5 5,2次元配列dpの5列目であるバイナリ101 101 101 101 101で表される.
したがって,我々の目標はd p[0][11 1 2]dp[0][111_2]dp[0][1112]、すなわちd p[0][7 10]dp[0][7_{10}]dp[0][710]であり,0 0番都市から出発して都市群{1,2,3}{1,2,3}{1,2,3}{1,2,3}を通過することを表し,動的計画の過程は上記のリンクを参照する.
次のコードの理解では、中の多くのバイナリ数の操作を理解することに重点を置いています.他は理解しにくくありません.
記入法のダイナミックプランニング結果印刷はいずれも再帰的な方法であり、path[i][j]はi番都市からjのバイナリ形式で表示される都市群、i番都市の次の都市の番号を格納する.
#include 
#include 
#include 
#include 
using namespace std;

#define N 15
#define MAX 0x3f3f3f3f

// int distances[N][N] = {{MAX, 3, 6, 7}, {5, MAX, 2, 3}, {6, 4, MAX, 2}, {3, 7, 5, MAX}};

int removeCity(int j, int k) { //  j             k   （k   0）
    return j - (1 << (k-1));
}

int TSP(int dp[][1 << (N-1)], int path[][1 << (N-1)], int distances[][N]) {
    if (N == 1) return 0; //       

    for (int i = 1; i < N; i++) {
        dp[i][0] = distances[i][0]; //         0      
    }

    for (int j = 1; j < (1 << (N-1)); j++) {
        for (int i = 1; i < N; i++) {
            if ((j >> (i-1)) % 2 == 0) { // i     j             
                int min = MAX;
                int next_city = i;
                for (int k = 1; k < N; k++) {
                    if ((j >> (k-1)) % 2 != 0) { // k    j             
                        int temp = distances[i][k] + dp[k][removeCity(j, k)]; //    k    j       
                        if (temp < min) {
                            min = temp;
                            next_city = k;
                        }
                    }
                }
                dp[i][j] = min;
                path[i][j] = next_city;
            }
        }
    }
    
    //       
    int min = MAX;
    int next_city = 0;
    int j = (1 << (N-1)) - 1; //    0              
    for (int k = 1; k < N; k++) {
        int temp = distances[0][k] + dp[k][removeCity(j, k)];
        if (temp < min) {
            min = temp;
            next_city = k;
        }
    }
    dp[0][j] = min;
    path[0][j] = next_city;

    
    /*for (int i = 0; i < N; i++) { //        
        for (int j = 0; j < 1 << (N-1); j++) {
            if (dp[i][j] == 0)
                cout << "\\" << " ";
            else
                cout << dp[i][j] << " ";
        }
        cout << endl;
    }*/

    return dp[0][j];
}

void printPath(int path[][1 << (N-1)], int i, int j) { //      i        j          
    if (j != 0) {
        cout << i << " -> ";
        int next_city = path[i][j];
        printPath(path, next_city, removeCity(j, next_city));
    }
    else {
        cout << i << " -> " << 0;
    }
}

int main() {
    int distances[N][N] = {0};
    int path[N][1 << (N-1)] = {0};
    int dp[N][1 << (N-1)] = {0};
    // 1 << (N-1) == pow(2, N-1)
    //    0，1，2...      
    //    000，001，010，... x  1，        x   

    //      distances[N][N]
    srand((unsigned int) time(NULL));
    for (int i = 0; i < N; i++) {
        for (int j = i; j < N; j++) {
            if (i == j) distances[i][j] = MAX;
            else {
                int temp = rand();
                while (temp == 0) {
                    temp = rand();
                }
                distances[i][j] = distances[j][i] = temp;
            }
        }
    }

    //       
    cout << "    ：[" << N << "]" << endl;
    cout << "     ：" << endl;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (distances[i][j] == MAX) cout << setw(5) << "INF" << " ";
            else cout << setw(5) << distances[i][j] << " ";
        }
        cout << endl;
    }

    //          (   ms)
    clock_t start = clock();
    int d = TSP(dp, path, distances);
    clock_t spent = (double) (clock() - start) / CLOCKS_PER_SEC * 1000;
    cout << "    ：" << spent << "ms" << endl;
    cout << "     ：" << d << endl;
    cout << "     ：";
    printPath(path, 0, (1 << (N-1))-1);

    return 0;
}

コード実行結果:
    ：[15]
     ：
  INF  3729 13549 16032  5214 16144 28132 31901 18181 27523 31894 28842 30136 32028 13307
 3729   INF 13870 20822  6156 17167 11654 12498  3912 27011 11758  2954 17805 25778  3749
13549 13870   INF 28116  8097 10456 19276  7130 27613 14974 18319 22185 25320 15417 30216
16032 20822 28116   INF 30596  9669  1172 26208 21886 23824 20555 32440 10568 23940 25786
 5214  6156  8097 30596   INF 25671 25415 30145 13972 22340 10217 18764 26840  1542 26170
16144 17167 10456  9669 25671   INF 23768 14337  7018 15538 14276  9598  3189  8273 16100
28132 11654 19276  1172 25415 23768   INF 30561 26938 31215 11396 24667 13566 11725 18858
31901 12498  7130 26208 30145 14337 30561   INF 25576  2459 16751 19612 19143  2594  5038
18181  3912 27613 21886 13972  7018 26938 25576   INF   162 15277 26820 23305  6925 19514
27523 27011 14974 23824 22340 15538 31215  2459   162   INF  1011 24124 24952  7724 24260
31894 11758 18319 20555 10217 14276 11396 16751 15277  1011   INF  6932  1358 23763 30872
28842  2954 22185 32440 18764  9598 24667 19612 26820 24124  6932   INF 20353 22669 11973
30136 17805 25320 10568 26840  3189 13566 19143 23305 24952  1358 20353   INF 18427  6381
32028 25778 15417 23940  1542  8273 11725  2594  6925  7724 23763 22669 18427   INF 16329
13307  3749 30216 25786 26170 16100 18858  5038 19514 24260 30872 11973  6381 16329   INF
    ：13ms
     ：79328
     ：0 -> 1 -> 11 -> 10 -> 9 -> 8 -> 13 -> 6 -> 3 -> 5 -> 12 -> 14 -> 7 -> 2 -> 4 -> 0
externキーワードの詳細
以前に実行したコマンドをもう一度すばやく実行する方法