2-оптовая реализация локального поиска

Я пытаюсь реализовать локальный поиск (с двумя опциями), чтобы решить проблему коммивояжера. Однако у меня возникли проблемы с правильным воссозданием полной схемы (тур по узлам). Я думаю, что мой алгоритм может быть ошибочным. Это моя реализация 2-opt:

а->б->...г->в->...а

переключается на

а->г->...б->в->...а

мой общий процесс выглядит как стандартный обмен: сохранить b как temp сохранить c как temp2 a->d b->c

Мой код выглядит так:

node* twoOpt(double** distance_matrix, node* tour, int NUM_CITIES)
{
int rand1, rand2;
int temp, temp2;

rand1 = rand() % NUM_CITIES; //a
rand2 = rand() % NUM_CITIES; //d

do
{
    //Ensure the two numbers are different
    while (rand1 == rand2 || tour[rand1].destination == rand2 || rand1 == tour[rand2].destination)
        rand2 = rand() % NUM_CITIES;

    //Make swap
    temp = tour[rand1].destination; //b
    temp2 = tour[rand2].destination; //c

    tour[rand1].destination = rand2;
    tour[rand1].distance = distance_matrix[rand1][rand2]; //a->d

    tour[temp].destination = temp2;
    tour[temp].distance = distance_matrix[temp][temp2]; //b->c

} while(!travelTour(tour, NUM_CITIES));

return tour;
}

Теперь я понимаю, что этот код не идеален. Например, если два перетасованных узла не создают полной цепи, код изменяет только второй узел перед повторной попыткой. Но вопрос, который у меня есть, в первую очередь о том, почему я не могу получить этот полный тур.

Спасибо за вашу помощь!


c search local traveling-salesman
person Jojo Jonas    schedule 12.10.2012    source источник

Ответы (2)


arrow_upward
3
arrow_downward

Я наконец нашел проблему. Моя концепция решения была неполной. Мне нужно было не только указать a->d и b->c, мне также нужно было инвертировать всю затронутую половину нового тура. Другими словами, мне нужно инвертировать старый путь от b к d. Ниже приведен правильный код:

do
{
    //Ensure the two numbers are different
    while (rand1 == rand2 || tour[rand1].destination == rand2 || rand1 == tour[rand2].destination)
        rand2 = rand() % NUM_CITIES;

    //Make swap
    temp = tour[rand1].destination; //b
    temp2 = tour[rand2].destination; //c

    tour[rand1].destination = rand2;
    tour[rand1].distance = distance_matrix[rand1][rand2]; //a->d

    oldNode = temp;
    currNode = tour[oldNode].destination;

    tour[temp].destination = temp2;
    tour[temp].distance = distance_matrix[temp][temp2]; //b->c

    //Swap directions of graph for d->b
    while (currNode != temp2)
    {
        nextNode = tour[currNode].destination;
        tour[currNode].destination = oldNode;
        oldNode = currNode;
        currNode = nextNode;
    }
} while(!travelTour(tour, NUM_CITIES));

Это все еще не совсем красиво. Если бы мне пришлось перезапустить проект, я бы не стал хранить свои данные в терминах узлов. Я бы хранил их в терминах ребер, причем каждое ребро знало бы о своих двух узлах. Это значительно облегчило бы обмен. Но тем не менее, вот мое решение для этого дизайна.

person Jojo Jonas    schedule 16.10.2012

arrow_upward
0
arrow_downward

Вам нужно корректировать цепочку:

введите здесь описание изображенияИз Руководство по Drools Planner.

person Geoffrey De Smet    schedule 15.10.2012