Dynamische Programmierlösung für TSP in C++

Question

Ich habe versucht, Dynamische Programmierung Lösung für TSP (Travelling Salesperson Problem) in C++ zu implementieren. Mein Code kompiliert, aber wenn ich versuche, die Objektdatei auszuführen, hört das Programm auf zu arbeiten, und ich muss es schließen. Hier

ist der Code:

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]; 
} 

Kann jemand bitte darauf hinweisen, was Fehler, den ich mache.

Answer 1

Sie müssen resize eine std::vector vor dem Aufruf operator[int] auf es füllen. Ein Vektor ist im Grunde ein Array, das seine Größe behält. Jeglicher Zugriff außerhalb der Grenzen verursacht einen Segmentierungsfehler in der Laufzeit (wenn Sie Glück haben) oder beschädigt Ihr Gedächtnis.

Sie haben einen Vektor von Vektoren hier, so dass Sie über zwei Bereiche durchlaufen müssen und füllen (oder die Größe) Vektoren richtig:

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; 

Noch besser:

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