c++ - 旅行推销员的多片段启发式方法(C++)

我正在尝试为TSP实现多片段启发式算法。

算法是这样的：


对边缘按权重的升序进行排序。（可以随意打结。）将要构建的巡视边集初始化为空集。
重复此步骤n次，其中n是要解决的实例中的城市数：将排序的边缘列表上的下一个边缘添加到游览边缘集合中，前提是该添加操作不会创建3度的顶点或的循环长度小于n；否则，跳过边缘。
返回巡视边的集合。


我坚持检查是否有周期。

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

有什么方法可以检查是否有周期吗？

非常感谢你。

最佳答案

要测试一个循环的图形，请将两个指针设置到第一个边/顶点。每次迭代移动一个步骤，每次迭代移动另外两个步骤。每次递增后，请检查两个指针​​是否相等。如果我们相等，则第二个指针会循环并追上来，并且存在一个循环。

关于c++ - 旅行推销员的多片段启发式方法(C++)，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/37143426/