жадный — мультифрагментная эвристика для коммивояжера (C ++)

Я пытаюсь реализовать эвристический алгоритм 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;
}

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

Большое спасибо.

1

Решение

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

0

Другие решения

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

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

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

-1

По вопросам рекламы [email protected]