Как распечатать путь в задаче коммивояжера - PullRequest
Новая
       21

Как распечатать путь в задаче коммивояжера

0 голосов
/ 04 мая 2019

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

Идея, которую я использовал для решения этой проблемы, заключается в следующем: Я рекурсивно вызываю функцию называемую travelSalesMan, если все города, в которых я побывал (я отслеживаю посещенные города, используя посещенный массив), или текущий путь больше, чем предыдущий, я просто возвращаю минимум между текущим расстоянием, который хранится в переменной, и текущее минимальное расстояние (в начале установлено значение max).

Я пытался отслеживать путь, используя массив с именем currentPath, а также pathLen, который сообщает мне, сколько элементов в пути.

Вот код, который у меня сейчас есть: 

int travelingSalesMan(int** distMatrix, int arrSize,  int* visited, int currentCity, int* currentPath, int cur_dist, int min_dist, int* minPath, int pathLen){


    if (complete(visited, arrSize) == arrSize) {
        // minPath[index] = currentPath[index];
        printf("Path len: %d\n", pathLen);
        for(int i = 0; i<arrSize; i++){
            minPath[i] = currentPath[i];
        }
        minPath[arrSize - 1] = currentCity;
        return min(cur_dist, min_dist);
    }

    // no need to pursue the path that is not minimum
    if(cur_dist >= min_dist){
        pathLen--;
        return min(cur_dist, min_dist);
    }

    for (int i = 0; i<arrSize; i++) {
        if (visited[i] == 0 && i != currentCity) {
            cur_dist += distMatrix[currentCity][i];

            currentPath[pathLen++] = currentCity;
            visited[i] = 1;
            min_dist = travelingSalesMan(distMatrix, arrSize, visited, i, currentPath, cur_dist, min_dist, minPath, pathLen);
            visited[i] = 0;

            cur_dist -= distMatrix[currentCity][i];
            pathLen--;
        }
    }


    return min_dist;
}

Я вызывал функцию выше со следующими параметрами: 

distance = travelingSalesMan(distMatrix, N, visited, 0, currentPath, 0, INT_MAX, minPath, 1);

Для данного distMatrix: 

[
{0 10 10 10 10}
{10 0 2 4 11}
{10 2 0 12 4} 
{10 4 12 0 8}
{10 11 4 8 0}
]

Минимальный вес равен 20, поэтому я ожидаю увидеть такой путь, как: 

0 3 1 2 4

Спасибо!

1 Ответ

0 голосов
/ 04 мая 2019

в блоке if (complete(visited, arrSize) == arrSize) { Вы должны писать в min_path, только если текущий путь короче, чем лучший найденный путь.

...