Multi Fragment Heuristik für Reisende Verkäufer (C++)

Question

Ich versuche, Multi Fragment Heuristik Algorithmus für TSP zu implementieren.

Algorithmus ist wie folgt aus:

1. sortieren die Kanten der Reihenfolge ihrer Gewichte bei der Erhöhung (Krawatten willkürlich gebrochen werden kann.) Initialisieren des Satzes von Tour Kanten auf den leeren Satz zu konstruieren..
2. Wiederholen Sie diesen Schritt n mal, wobei n die Anzahl der Städte in der Instanz ist, die gelöst wird: Fügen Sie die nächste Kante der sortierten Kantenliste zur Menge der Tourenkanten hinzu, sofern diese Addition keine Ecke von Grad 3 oder ein Zyklus mit einer Länge von weniger als n; Überspringen Sie andernfalls die Kante.
3. Die Menge der Tourenkanten zurückgeben.

Ich bin fest mit der Überprüfung, ob es einen Zyklus gibt.

#include <stdio.h> 
#include <math.h> 
#include <limits.h> 
#include <queue> 
static int repeat[6]; 
struct element{ 
    int distance; 
    int x; 
    int y; 
}; 

struct element array[25]; 

void quicksort(struct element x[78400],int first,int last){ 
    int pivot,j,i; 
    struct element temp; 
    if(first<last){ 
     pivot=first; 
     i=first; 
     j=last; 

     while(i<j){ 
      while(x[i].distance<=x[pivot].distance&&i<last) 
       i++; 
      while(x[j].distance>x[pivot].distance) 
       j--; 
      if(i<j){ 
       temp=x[i]; 
       x[i]=x[j]; 
       x[j]=temp; 
      } 
     } 

     temp=x[pivot]; 
     x[pivot]=x[j]; 
     x[j]=temp; 
     quicksort(x,first,j-1); 
     quicksort(x,j+1,last); 

    } 
} 
bool isCycle(){ 



    return true; 
} 

bool canAdd(int a){ 
    repeat[array[a].x]++; 
    repeat[array[a].y]++; 
    if(repeat[array[a].x] > 2 || repeat[array[a].y] > 2){ 
     repeat[array[a].x]--; 
     repeat[array[a].y]--; 
     return false; 
    } 
    return true; 
} 


int main(int argc, const char * argv[]) { 


    int i = 0; 

    int graph[6][6] = { 
     {INT_MAX,4,8,9,12}, 
     {4,INT_MAX,6,8,9}, 
     {8,6,INT_MAX,10,11}, 
     {9,8,10,INT_MAX,7}, 
     {12,9,11,7,INT_MAX} 
    }; 

    int an = 0; 
    for(int a = 0; a<5; a++){ 
     for(int b = a; b<5; b++){ 
      array[an].x = a; 
      array[an].y = b; 
      array[an].distance = graph[a][b]; 
      an++; 
     } 
    } 

    quicksort(array, 0, an-1); 


    static int sayilar[6]; 
    for(int ya = 0; ya<6; ya++){ 
     sayilar[ya] = 0; 
    } 

    std::queue<element> tour; 
    int edges = 0; 

    while(edges != 5){ 
     printf("%d %d %d\n", array[i].x, array[i].y, array[i].distance); 
     if(canAdd(i)){ 
      tour.push(array[i]); 
      printf("oldu\n"); 
      if(isCycle()){ 
       tour.pop(); 
      } 
     } 
     i++; 
     edges = (int)tour.size(); 
     printf("%d\n", edges); 
    } 


    return 0; 
} 

Gibt es eine Möglichkeit zu überprüfen, ob es einen Zyklus gibt?

Vielen Dank.

Answer 1

Wenn Sie Fragmente erstellen, überprüfen Sie bei jeder Iteration, ob die Startstadt des aktualisierten Fragments mit der letzten übereinstimmt.

Möglicherweise müssen Sie Ihre Implementierung ändern, um diese Überprüfung zu vereinfachen.

Außerdem lade ich Sie mein Papier „Eine empirische Untersuchung des Multi-Fragment Tour-Construction-Algorithmus für das Reisen Salesman Problem“ erschien in den Proceedings der 16. Internationalen Konferenz über Hybrid Intelligent Systems (HIS 2016) zu lesen S. 278-287. DOI: 10.1007/978-3-319-52941-7_28.

Answer 2

Um ein Diagramm für einen Zyklus zu testen, setzen Sie zwei Zeiger auf die erste Kante/den ersten Scheitelpunkt. Verschieben Sie einen Schritt in jeder Iteration, die anderen zwei Schritte pro Iteration. Überprüfen Sie die beiden Zeiger nach jedem Inkrement auf Gleichheit. Wenn wir Gleichheit haben, hat der zweite Zeiger eine Schleife gemacht und hat aufgeholt, und es gibt einen Zyklus.