Эвристический этюд для путешествующего коммивояжера (C++)

Question

Я пытаюсь реализовать алгоритм эвристики Multi Fragment для TSP.

Алгоритм так:

1. Сортировать края в порядке возрастания их весов (Связи могут быть разбиты произвольно.) Инициализировать набор тура края, чтобы быть построены для пустого множества..
2. Повторите этот шаг n раз, где n - количество городов в разрешаемом экземпляре: добавьте следующий край в список отсортированных краев к набору краев тура, если это добавление не создает вершину степени 3 или цикл длины меньше n; в противном случае пропустите край.
3. Верните набор краев тура.

Я застрял в проверке, есть ли цикл.

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

Есть ли способ проверить, есть ли цикл?

спасибо.

Answer 1

При создании фрагментов проверяйте каждую итерацию, если начальный город обновленного фрагмента совпадает с предыдущим.

Возможно, вам понадобится изменить вашу реализацию, чтобы упростить эту проверку.

Кроме того, я предлагаю вам прочитать мою статью «эмпирического исследования мульти-фрагмент туры Построения алгоритма для задачи коммивояжера» появились в Трудах 16-ой Международной конференции по гибридным интеллектуальным системам (HIS 2016) pp. 278-287. DOI: 10.1007/978-3-319-52941-7_28.

Answer 2

Чтобы проверить график для цикла, установите два указателя на первый край/вершину. Перемещайте один шаг на каждую итерацию, остальные два шага на итерацию. Проверьте два указателя на равенство после каждого приращения. Если у нас есть равенство, второй указатель зацикливается и догоняет, и есть цикл.