Проблема TSP в C с помощью простого решения по возврату - PullRequest
Новая
       34

Проблема TSP в C с помощью простого решения по возврату

0 голосов
/ 15 января 2019

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

Пример ввода и вывода: 

    Please enter the roads 4X4 matrix row by row:
    0 2 -1 2
    -1 0 2 -1
    1 -1 0 2
    2 1 -1 0
    The shortest path is of length: 6

Основная цель

каждое число на дорогах Matrice [N] [N] (в настоящее время N = 4) это расстояние следующим образом: location (i, j) число представляет расстояние от города i до города j. и цель состоит в том, чтобы добраться из города № 0 (строка 0 в матрице) через все города обратно в город 0 по кратчайшему пути.

Мое решение Создайте функцию оболочки ShortestFullPath () со всеми первыми параметрами. и вторая функция возврата назад short_path где я проверяю условия остановки (например, тот же город => 0 или нет города => -1 или закончил прохождение через все города)

Количество посещенных массивов равно количеству городов. В каждом городе, который я посещаю, я отмечаю соответствующий индекс в массиве как true или false и проверяю все параметры в городе для других городов.

Примечания стороны

checkvisited () проверяет, все ли посещенные массивы верны;

min () проверяет минимальное время между current_path и лучшим путем на данный момент. 

int ShortestFullPath(int roads[N][N])


bool visited[N];
for(int i = 0; i < N; i++)
{
    visited[i] = false;
}
int shortest_path = 9999;
int current_path = 0;
int city = 0;
int j = 0; //destinaton city
visited [0] = true;
if(short_path(roads, city, j, current_path, &shortest_path, visited))
    Print(shortest_path);
else
    Print(NO_PATH);
return 0;



bool short_path(int roads[N][N], int city, int j, int current_path,
int *shortest_path, bool visited[N])
{

    if(check_visited(visited))
    {
        *(shortest_path) = min(current_path, *shortest_path);
        current_path = 0;
        return true;
    }
    if((roads[city][j] == -1) ||(roads[city][j] == 0)){
          return false;}
    if(visited[city] == true)
        return false;

    visited[city] = true;
    current_path = current_path + roads[city][j];


    for(int j =0; j< N; j++)
    {
        short_path(roads, city, j, current_path, shortest_path, visited);
    }
    visited[city] = false;
    return true;
}
...