Проблема коммивояжера с использованием бэктрекинга - PullRequest
Новая
       73

Проблема коммивояжера с использованием бэктрекинга

0 голосов
/ 11 апреля 2020

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

{ 
  {0, 15, 10, 25},
  {10, 0, 40, 15},
  {45, 15, 0, 20},
  {10, 35, 10, 0}
}

Используемый код 

int tspBacktrackRecursive(int v, int n, int graph[][n], bool *visited, int nodesVisited, int currentCost, int minCost){
    if(currentCost > minCost)
        return minCost;
    visited[v] = true;
    nodesVisited++;
    path[nodesVisited - 1] = v;
    int i;
    if(nodesVisited == n){
        visited[v] = false;
        if(graph[v][0] + currentCost < minCost){
            int j;
            for(j = 0; j < n; j++)
                finalpath[j] = path[j];
            path[nodesVisited - 1] = 0;
            return (graph[v][0] + currentCost);
        }
        return minCost;
    }
    for(i = 0; i < n; i++){
        if(!visited[i]){
            minCost = tspBacktrackRecursive(i, n, graph, visited, nodesVisited, currentCost + graph[v][i], minCost);
        }
    }
    path[nodesVisited - 1] = 0;
    visited[v] = false; 
    return minCost;
}

int tspBackTrack(int n, int graph[][n]){
    bool* visited = (bool*)calloc(n, sizeof(bool));
    finalpath = (int*)calloc(n, sizeof(int));
    path = (int*)calloc(n, sizeof(int));
    return tspBacktrackRecursive(0, n, graph, visited, 0, 0, __INT_MAX__);
}

int *printPath(int n, int graph[][n]){
    return finalpath;
}

Минимальный вес, который я нашел, был таким: - 50

Программа кратчайшего пути выглядела так: - (0, 2, 1, 3)

Проблема в том, что я не знаю, прав ли я. Помоги мне здесь ....

...