Я пытаюсь реализовать эвристический алгоритм Multi Fragment для TSP.
Алгоритм такой:
Я застрял с проверкой, если есть цикл.
#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;
}
Есть ли способ проверить, есть ли цикл?
Большое спасибо.
Чтобы проверить график для цикла, установите два указателя на первое ребро / вершину. Переместите один шаг на каждую итерацию, остальные два шага на каждую итерацию. Проверяйте два указателя на равенство после каждого приращения. Если у нас есть равенство, второй указатель зациклился и догонял, и есть цикл.
При построении фрагментов проверяйте на каждой итерации, совпадает ли начальный город обновленного фрагмента с последним.
Возможно, вам придется изменить свою реализацию, чтобы упростить эту проверку.
Также я предлагаю вам прочитать мою статьюЭмпирическое исследование алгоритма построения многофрагментного тура для задачи коммивояжера«появился в материалах 16-й Международной конференции по гибридным интеллектуальным системам (HIS 2016), стр. 278-287. DOI: 10.1007 / 978-3-319-52941-7_28.