C++でのTSPの動的プログラミングソリューション

Question

私は、C++でTSP (Travelling Salesperson Problem)の動的プログラミングソリューションを実装しようとしています。私のコードはコンパイルされますが、オブジェクトファイルを実行しようとするとプログラムは機能しなくなり、強制的に閉じます。ここで

はコードです：

int tsp(std::vector<std::vector<int>> matrix) { 

    int n = matrix[0].size(); 
    std::vector<std::vector<int>> A; // Vertex, Set-Size 
    std::set<int> S; 

    for(int i = 0; i < n; ++i) { 
     S.insert(i); 
    } 

    for(int i = 0; i < n; i++) { 
     if(S.size() == 2) { 
      A[i][2] = matrix[1][i]; 
     } 
     else if(S.size() > 2) { 
      std::set<int>::iterator it; 
      for(it = S.begin(); it != S.end(); ++it) { 
       int s = S.size(); 
       S.erase(i); 
       int sd = S.size(); 
       int k = *it; 
       if((k != i) && (k != 1) && (A[i][s] > (matrix[k][i] + A[k][sd]))) { 
        A[i][s] = matrix[k][i] + A[k][sd]; 
       } 
      } 
     } 
    } 

    return A[1][n]; 
} 

誰かが私が作っていますどのような間違いを指摘してくださいすることができます。

Answer 1

operator[int]を呼び出す前に、またはresizeのstd::vectorを入力する必要があります。ベクトルは、基本的にサイズを保持する配列です。したがって、アクセス不能になった場合、実行時にセグメンテーション違反が発生するか（幸運な場合）、メモリが破損します。

あなたは二つの範囲を反復して入力する必要があります（またはサイズ変更）しますので、あなたは、ここでベクトルのベクトルを持つベクトル適切：

std::vector<std::vector<int>> A; // Vertex, Set-Size 
for(int i=size; i>0; --i) 
    A.push_back(std::vector<int>); 
for(int i=size; i>0; --i) 
    for(int j=size; j>0; --j) 
    A[i][j] = 0; 

さらに良い：

A.resize(size); 
for(auto& v : a)  // (since you already have c++11) 
    v.resize(size, val); // fill with val