Как рассчитать сложность времени для задачи «Обратный путь - продавец-путешественник»? - PullRequest
Новая
       43

Как рассчитать сложность времени для задачи «Обратный путь - продавец-путешественник»?

0 голосов
/ 01 марта 2020

У меня проблемы с поиском сложности времени для возврата. Я пытался найти временную сложность гамильтонова цикла, так как она используется в задании Backtracking - Traveling Salesman, и вот что я нашел:

Я видел на канале YouTube Абдул Бари, что сложность времени для Backtracking - Hamiltonian Cycle равна n ^ n, а ответ на один из вопросов здесь в stackoverflow: n!

n ^ n Ссылка: https://www.youtube.com/watch?v=dQr4wZCiJJ4&t=389s

n! Ссылка: Как вычислить временную сложность алгоритма обратного отслеживания?

Я действительно не знаю, как вычислить сложность времени, вы, ребята, можете помочь мне определить сложность времени по этому ( Это код возврата - код проблемы коммивояжера):

Ссылка: https://www.geeksforgeeks.org/travelling-salesman-problem-implementation-using-backtracking/

public class GFG{ 

// Function to find the minimum weight  
// Hamiltonian Cycle 
static int tsp(int[][] graph, boolean[] v,  
               int currPos, int n,  
               int count, int cost, int ans)  
{ 

    // If last node is reached and it has a link 
    // to the starting node i.e the source then 
    // keep the minimum value out of the total cost 
    // of traversal and "ans" 
    // Finally return to check for more possible values 
    if (count == n && graph[currPos][0] > 0)  
    { 
        ans = Math.min(ans, cost + graph[currPos][0]); 
        return ans; 
    } 

    // BACKTRACKING STEP 
    // Loop to traverse the adjacency list 
    // of currPos node and increasing the count 
    // by 1 and cost by graph[currPos,i] value 
    for (int i = 0; i < n; i++)  
    { 
        if (v[i] == false && graph[currPos][i] > 0)  
        { 

            // Mark as visited 
            v[i] = true; 
            ans = tsp(graph, v, i, n, count + 1, 
                      cost + graph[currPos][i], ans); 

            // Mark ith node as unvisited 
            v[i] = false; 
        } 
    } 
    return ans; 
} 

// Driver code 
public static void main(String[] args) 
{ 

    // n is the number of nodes i.e. V 
    int n = 4; 

    int[][] graph = {{0, 10, 15, 20}, 
                     {10, 0, 35, 25}, 
                     {15, 35, 0, 30}, 
                     {20, 25, 30, 0}}; 

    // Boolean array to check if a node 
    // has been visited or not 
    boolean[] v = new boolean[n]; 

    // Mark 0th node as visited 
    v[0] = true; 
    int ans = Integer.MAX_VALUE; 

    // Find the minimum weight Hamiltonian Cycle 
    ans = tsp(graph, v, 0, n, 1, 0, ans); 

    // ans is the minimum weight Hamiltonian Cycle 
    System.out.println(ans); 
} 
} 

// This code is contributed by Rajput-Ji
...