Travelling Salesman Problem

30 Dec 2024 | 29 分钟阅读

在本教程中，我们将讨论旅行商问题及其在不同编程语言中使用不同方法的解决方案和实现。

那么，让我们开始吧。

理解旅行商问题

旅行商问题（也称为旅行推销员问题或 TSP）是一个 NP-hard 图计算问题，其中推销员必须访问集合中给出的所有城市（在图中用顶点表示）一次。所有这些城市之间的距离（在图中用边表示）是已知的。我们被要求找到推销员访问所有城市并返回原点城市的最短可能路线。

注意：汉密尔顿回路和 TSP 之间存在差异。汉密尔顿回路问题是找出是否存在一个恰好访问每个城市一次的回路。然而，在这个问题中，我们已经知道汉密尔顿回路存在，因为图是完整的，而且实际上存在许多这样的回路。因此，问题是找出最小权重的汉密尔顿回路。

让我们看一些演示该问题的例子

旅行商问题示例 1

输入

输出

旅行商问题示例 2

输入

输出

Minimum Weight Hamiltonian Cycle: EACBDE = 32

旅行商问题的解决方案

在下一节中，我们将讨论用于解决问题以及在 C、C++、Java 和 Python 等不同编程语言中的实现的各种方法。

以下是我们即将使用的一些方法

简单或朴素方法
动态规划方法
贪心法

现在让我们详细讨论上述方法

使用简单方法解决旅行商问题

在以下方法中，我们将使用下面提到的步骤来解决问题

步骤 1：首先，我们将城市 1 作为起点和终点。由于路线是循环的，任何一点都可以作为起点。

步骤 2：作为第二步，我们将生成所有可能的城市排列，即 (n-1)!

步骤 3：之后，我们将计算每个排列的成本，并记录最小成本排列。

步骤 4：最后，我们将返回成本最低的排列。

用不同编程语言实现简单方法来解决旅行商问题

既然我们已经成功理解了用简单方法解决旅行商问题的步骤，现在是时候看看它在 C++、Java 和 Python 等不同编程语言中的实现了。

C++ 中的代码实现

以下是旅行商问题算法在 C++ 编程语言中的实现

文件：TSP.cpp

// Travelling Salesman Problem - Simple Approach Implementation in C++ 

// including the required header file
#include <bits/stdc++.h>

// using the standard namespace
using namespace std;

// defining the constant number of nodes
#define V 4

// defining the function to return the minimum weight Hamiltonian cycle
int travelling_salesman_problem(int graph[][V], int n)
{
    // creating a vector to store the nodes
    vector<int> nodes;
    // iterating through defined number of nodes and pushing elements into the vector from the back if the current value is not equal to source node
    for (int i = 0; i < V; i++)
        if (i != n)
            nodes.push_back(i);

    // setting an initial value for minimum path as Integer's maximum value
    int minimumPath = INT_MAX;

    // do-while loop
    do {
        // setting an initial value of current path weight as 0
        int currentPathWeight = 0;
        int k = n;
        // iterating through the vector and incrementing the current path weight 
        for (int i = 0; i < nodes.size(); i++) {
            currentPathWeight += graph[k][nodes[i]];
            k = nodes[i];
        }
        currentPathWeight += graph[k][n];
 
        // updating the minimum path weight
        minimumPath = min(minimumPath, currentPathWeight);
    } while (
        next_permutation(nodes.begin(), nodes.end())
        );
    
    // returning the minimum path weight
    return minimumPath;
}

// main function
int main()
{   
    // defining the nodes of the graph
    int graph[][V] = {
        { 0, 12, 18, 24 },
        { 12, 0, 36, 28 },
        { 18, 36, 0, 32 },
        { 24, 28, 32, 0 }
        };

    // starting node
    int n = 0;

    // calling the travelling_salesman_problem() function
    int minimumPathWeight = travelling_salesman_problem(graph, n);

    // printing the result for the users
    cout << "Minimum Cost : " << minimumPathWeight << endl;
    return 0;
}

输出

Minimum Cost : 90

说明

在上面的代码片段中，我们包含了 'bits/stdc++.h' 头文件，使用了标准命名空间，并定义了一个常量 V = 4，表示图中节点的数量。然后我们定义了一个函数来查找最小权重汉密尔顿回路成本，名为 travelling_salesman_problem()，它接受一个二维数组表示图和一个表示起始节点的整数。在此函数内部，我们创建了一个向量来存储图中的节点。然后我们使用 for 循环遍历定义的顶点数，并使用向量的 push_back() 方法将每个元素推送到向量中（如果它不是源节点）。然后我们将最小路径权重的初始值设置为 INT_MAX（最大整数值）。

然后我们使用 do-while 循环来更新所有可能排列的最小路径权重。在此循环中，我们将当前路径权重的初始值设置为 0，然后遍历向量，根据图的边增加当前路径权重。然后我们通过比较当前路径权重和存储的值来更新最小路径权重。然后我们返回结果路径权重并定义了一个 main 函数。我们在 main 函数中使用邻接矩阵定义了图，并设置了起始节点。然后我们调用 travelling_salesman_problem() 函数来查找最小权重汉密尔顿回路成本，并将返回值存储在一个变量中。最后，我们为用户打印了这个变量。

结果，最小权重汉密尔顿回路成本，即 90，被打印给用户。

Java 代码实现

以下是旅行商问题算法在 Java 编程语言中的实现

文件：TSP.java

// Travelling Salesman Problem - Simple Approach Implementation in Java

// importing the required library
import java.util.*;

// defining the class to solve Travelling Salesman Problem
class TSP{

    // initializing a constant value for number of nodes
    static int V = 4;

    // defining the method to find the minimum weight Hamiltonian Cycle
    static int travelling_salesman_problem(int graph[][], int n)
    {
        // creating an array to store the number of numbers
        ArrayList<Integer> nodes = new ArrayList<Integer>();

        // iterating through the number of nodes and adding elements into the array if the current value is not equal to source node
        for (int i = 0; i < V; i++)
            if (i != n)
                nodes.add(i);

        // setting an initial value for minimum path as Integer's maximum value 
        int minimumPath = Integer.MAX_VALUE;
        
        // do-while loop
        do
        {
            // setting an initial value of current path weight as 0
            int currentPathWeight = 0;
            int k = n;
            // iterating through the array and incrementing the current path weight
            for (int i = 0; i < nodes.size(); i++)
            {
                currentPathWeight += graph[k][nodes.get(i)];
                k = nodes.get(i);
            }
            currentPathWeight += graph[k][n];
            
            // updating the minimum path weight
            minimumPath = Math.min(minimumPath, currentPathWeight);

        } while (next_permutation(nodes));

        return minimumPath;
    }

    // defining the method to swap the elements of the array list
    public static ArrayList<Integer> swap(ArrayList<Integer> data, int leftElement, int rightElement){
        int temp = data.get(leftElement);
        data.set(leftElement, data.get(rightElement));
        data.set(rightElement, temp);
        return data;
    }

    // defining the method to reverse the data elements of the array list
    public static ArrayList<Integer> reverse(ArrayList<Integer> data, int leftElement, int rightElement)
    {
        while (leftElement < rightElement)
        {
            int temp = data.get(leftElement);
            data.set(leftElement++, data.get(rightElement));
            data.set(rightElement--, temp);
        }
        return data;
    }

    // defining the method to return the next permutation in the array list
    public static boolean next_permutation(ArrayList<Integer> data)
    {
        if (data.size() <= 1)
            return false;

        int last = data.size() - 2;
        while (last >= 0)   
        {
            if (data.get(last) < data.get(last + 1))
            {
                break;
            }
            last--;
        }
        if (last < 0)
            return false;

        int next_greater = data.size() - 1;
        for (int i = data.size() - 1; i > last; i--) {
            if (data.get(i) > data.get(last))
            {
                next_greater = i;
                break;
            }
        }
        data = swap(data, next_greater, last);
        data = reverse(data, last + 1, data.size() - 1);
        return true;
    }

    // main function
    public static void main(String args[])
    {
        // defining the nodes of the graph
        int graph[][] = {
            { 0, 12, 18, 24 },
            { 12, 0, 36, 28 },
            { 18, 36, 0, 32 },
            { 24, 28, 32, 0 }
            };

        // starting node
        int n = 0;

        // calling the travelling_salesman_problem() method
        int minimumPathWeight = travelling_salesman_problem(graph, n);
        
        // printing the result for the users
        System.out.print("Minimum Cost : ");
        System.out.print(minimumPathWeight);
        }
    }

输出

Minimum Cost : 90

说明

在上面的代码片段中，我们从 'java.util' 库导入了所有内容，并将主类定义为 TSP 来解决旅行商问题。在此类中，我们初始化了一个常量 V = 4，它表示图中节点的总数。然后我们定义了一个函数来查找最小权重汉密尔顿回路成本，名为 travelling_salesman_problem()，它接受一个二维数组表示图和一个表示起始节点的整数。在此函数内部，我们使用 ArrayList 创建了一个整数数组来存储图中的节点。然后我们使用 for 循环遍历定义的顶点数，并使用 add() 方法将每个元素添加到向量中（如果它不是源节点）。然后我们将最小路径权重的初始值设置为 Integer.MAX_VALUE（最大整数值）。

然后我们使用 do-while 循环来更新所有可能排列的最小路径权重。在此循环中，我们将当前路径权重的初始值设置为 0，然后遍历数组，根据图的边增加当前路径权重。然后我们通过比较当前路径权重和存储的值来更新最小路径权重。然后我们返回结果路径权重。之后，我们定义了几个额外的函数来帮助我们交换数组元素、反转它们以及进行排列。然后我们定义了 main 函数，使用邻接矩阵创建图并设置起始节点。然后，我们调用 travelling_salesman_problem() 函数来查找最小权重汉密尔顿回路成本，并将返回值存储在一个变量中。最后，我们为用户打印了这个变量。

结果，最小权重汉密尔顿回路成本，即 90，被打印给用户。

Python中的代码实现

以下是旅行商问题算法在 Python 编程语言中的实现

文件：TSP.py

# Travelling Salesman Problem - Simple Approach Implementation in Python

# importing the required modules
from itertools import permutations
from sys import maxsize

# defining a constant value for the number of nodes
V = 4

# defining the method to find the minimum weight Hamiltonian Cycle
def travelling_salesman_problem(graph, n):
    
    # creating an empty list to store the number of numbers
    nodes = []
    
    # iterating through the number of nodes and adding elements into the array if the current value is not equal to source node
    for i in range(V):
        if i != n:
            nodes.append(i)

    # setting an initial value for minimum path as Integer's maximum value
    minimumPath = maxsize
    
    # instantiating the permutations() class
    nextPermutation = permutations(nodes)
    
    # iterating through each permutation and updating the minimum path weight
    for i in nextPermutation:
        
        # initializing the current path weight as 0
        currentPathWeight = 0
        k = n
        
        # iterating through the list and incrementing the current path weight
        for j in i:
            currentPathWeight += graph[k][j]
            k = j
        currentPathWeight += graph[k][n]
        
        # updating the minimum path weight
        minimumPath = min(minimumPath, currentPathWeight)
        
    return minimumPath

# main function
if __name__ == "__main__":
    
    # defining the nodes of the graph
    graph = [
        [ 0, 12, 18, 24 ],
        [ 12, 0, 36, 28 ],
        [ 18, 36, 0, 32 ],
        [ 24, 28, 32, 0 ]
    ]
    
    # starting node
    n = 0
    
    # calling the travelling_salesman_problem() function
    minimumPathWeight = travelling_salesman_problem(graph, n)
    
    # printing the result for the users
    print("Minimum Cost :", minimumPathWeight)

输出

Minimum Cost : 90

说明

在上面的代码片段中，我们从 itertools 模块导入了 permutations 类，从 sys 模块导入了 maxsize 变量。然后我们初始化了一个常量 V = 4，表示图中节点的总数。然后我们定义了一个函数来查找最小权重汉密尔顿回路成本，名为 travelling_salesman_problem()，它接受一个列表表示图和一个表示起始节点的整数。在此函数内部，我们创建了一个空列表来存储图中的节点。然后我们使用 for 循环遍历定义的顶点数，并使用 append() 方法将每个元素添加到向量中（如果它不是源节点）。然后我们将最小路径权重的初始值设置为 maxsize（最大整数值）。

然后我们为节点数实例化了 permutations() 类，并使用 for 循环遍历每个排列并相应地更新最小路径权重。在此循环中，我们将当前路径权重的初始值设置为 0，然后遍历列表，根据图的边增加当前路径权重。然后我们通过比较当前路径权重和存储的值来更新最小路径权重。然后我们返回结果路径权重。然后我们定义了 main 函数，创建图并设置起始节点。然后，我们调用 travelling_salesman_problem() 函数来查找最小权重汉密尔顿回路成本，并将返回值存储在一个变量中。最后，我们为用户打印了这个变量。

结果，最小权重汉密尔顿回路成本，即 90，被打印给用户。

旅行商问题使用简单方法的时空复杂度

旅行商问题使用简单或朴素方法的时间复杂度为 O(N!)，其中 N 是城市的数量。
旅行商问题使用简单或朴素方法的空间复杂度为 O(1)。

使用动态规划方法解决旅行商问题

在以下方法中，我们将使用下面提到的步骤来解决问题

步骤 1：在旅行商问题算法中，我们将接受需要访问的城市子集 N、城市之间的距离以及起始城市 S 作为输入。每个城市都由一个唯一的城市 ID 表示（例如 1, 2, 3, 4, 5, ..., n）。

步骤 2：让我们将 1 作为问题的起点和终点。对于每个其他节点 V（除了 1），我们将计算以 1 为起点、V 为终点、所有节点恰好出现一次的最小成本路径。

步骤 3：设该路径的成本为 cost(i)，相应回路的成本将是 cost(i) + distance(i, 1)，其中 distance(i, 1) 是从 V 到 1 的距离。最后，我们将返回所有 [cost(i) + distance(i, 1)] 值中的最小值。

上述过程看起来很简单。但是，主要问题是如何计算 cost(i)？为了借助动态规划计算 cost(i)，我们需要一些关于子问题的递归关系。

我们定义一个术语 C(S, i) 为访问集合 S 中的每个节点一次的最小成本路径的成本，从 1 开始并在 i 结束。我们将从所有大小为 2 的子集开始，并计算所有大小为 S 的子集的 C(S, i)，依此类推。

注意：节点 1 必须存在于每个子集中。

用不同编程语言实现动态规划方法来解决旅行商问题

现在我们将看到使用自顶向下递归 + 记忆化方法在 C++、Java 和 Python 等不同编程语言中实现动态规划解决方案。

为了维护子集，我们可以利用位掩码来表示子集中剩余的节点。由于使用位进行操作更快，而且图中只有少量节点，所以位掩码更适合使用。

例如

10100 表示节点 2 和 4 仍在集合中待处理。
010010 表示节点 1 和 4 仍在子集中。

注意：忽略第零位，因为图是基于 1 的。

C++ 中的代码实现

以下是旅行商问题算法在 C++ 编程语言中的实现

文件：TSP.cpp

// importing the 'iostream' header file
#include "iostream"

// using the standard namespace
using namespace std;

// defining the number of the nodes in the graph
const int V = 4;

// defining the maximum size to avoid overflow issue
const int MAX = 999999;

// graph[i][j] signifies the shortest distance to go from index i to index j
// we can calculate this matrix for any given graph using all-pair shortest path algorithms
int graph[V + 1][V + 1] = {
    { 0, 0, 0, 0, 0 },
    { 0, 0, 12, 18, 24 },
    { 0, 12, 0, 36, 28 },
    { 0, 18, 36, 0, 32 },
    { 0, 24, 28, 32, 0 }
    };

// memoization for top-down recursion
int memoize[V + 1][1 << (V + 1)];

// defining the recursive function to find the minimum weight Hamiltonian Cycle cost
int travelling_salesman_problem(int i, int mask)
{	
    // defining the base case
    // if only ith bit and first bit is set in the mask,
    // it means we have visited all other nodes already
    if (mask == ((1 << i) | 3))
        return graph[1][i];
    // performing memoization
    if (memoize[i][mask] != 0)
        return memoize[i][mask];

    // initializing the minimum cost as the Maximum integer value
    int minimumCost = MAX;

    // we have to travel all nodes j in mask and end the path at ith node so for every node j
    // in mask, recursively estimate the cost of travelling all nodes in mask except i and
    // then travel back from node j to node i taking the shortest path take the minimum of
    // all possible j nodes
    for (int j = 1; j <= V; j++)
        if ((mask & (1 << j)) && j != i && j != 1)
            minimumCost = std::min(minimumCost, travelling_salesman_problem(j, mask & (~(1 << i))) + graph[j][i]);
    return memoize[i][mask] = minimumCost;
}

// main function
int main()
{
    // defining and initializing the resultant cost as maximum Integer value
    int cost = MAX;

    // using the for-loop to iterate through the nodes
    for (int i = 1; i <= V; i++)
        // try to go from node 1 visiting all nodes in
        // between to i then return from i taking the
        // shortest route to 1
        cost = std::min(cost, travelling_salesman_problem(i, (1 << (V + 1)) - 1) + graph[i][1]);

    // printing the total cost for the users
    cout << "Minimum Cost : " << cost;

    return 0;
}

输出

Minimum Cost : 90

说明

在上面的代码片段中，我们包含了 iostream 头文件并使用了标准命名空间。然后我们定义了一个常量来表示顶点总数，最大整数大小以避免溢出问题，一个图，以及一个用于自顶向下递归方法的记忆化矩阵。然后我们定义了一个名为 travelling_salesman_problem() 的函数，它接受两个参数 - 第一个参数是可迭代对象，第二个参数是位掩码。在此函数中，我们定义了一个递归的基本情况，该情况仅在掩码中设置了当前位和第一位时执行，这意味着所有其他节点都已访问。

之后，我们进行了记忆化，并将最小成本初始化为最大整数值。然后我们使用 for 循环遍历掩码中的所有节点。我们递归地计算遍历掩码中除选定节点外的节点的成本，然后通过采取最短可能路径返回起始节点。对于 main 函数，我们已将结果成本初始化为最大整数值，并使用 for 循环遍历图的节点，通过为该特定节点调用 travelling_salesman_problem() 函数来计算新的最小成本，并将最小成本值设置为结果成本。最后，我们为用户打印了结果。

结果，最小权重汉密尔顿回路成本，即 90，被打印给用户。

Java 代码实现

以下是旅行商问题算法在 Java 编程语言中的实现

文件：TSP.java

// Travelling Salesman Problem - Dynamic Programming Approach Implementation in Java

// defining the class to solve Travelling Salesman Problem
public class TSP {
    // defining the number of the nodes in the graph
    static int V = 4;

    // defining the maximum size to avoid overflow issue
    static int MAX_INT = 999999;

    // graph[i][j] signifies the shortest distance to go from index i to index j
    // we can calculate this matrix for any given graph using all-pair shortest path algorithms
    static int[][] graph = {
        { 0, 0, 0, 0, 0 },
        { 0, 0, 12, 18, 24 },
        { 0, 12, 0, 36, 28 },
        { 0, 18, 36, 0, 32 },
        { 0, 24, 28, 32, 0 }
    };

    // memoization for top-down recursion
    static int[][] memoize = new int[V + 1][1 << (V + 1)];

    // defining the recursive function to find the minimum weight Hamiltonian Cycle cost
    static int travelling_salesman_problem(int i, int mask)
    {
        // defining the base case
        // if only ith bit and first bit is set in the mask,
        // it means we have visited all other nodes already
        if (mask == ((1 << i) | 3))
            return graph[1][i];
        // performing memoization
        if (memoize[i][mask] != 0)
            return memoize[i][mask];

        // initializing the minimum cost as the Maximum integer value
        int minimumCost = MAX_INT;

        // we have to travel all nodes j in mask and end the path at ith node so for every node j
        // in mask, recursively estimate the cost of travelling all nodes in mask except i and
        // then travel back from node j to node i taking the shortest path take the minimum of
        // all possible j nodes
        for (int j = 1; j <= V; j++)
            if ((mask & (1 << j)) != 0 && j != i && j != 1)
                minimumCost = Math.min(minimumCost, travelling_salesman_problem(j, mask & (~(1 << i))) + graph[j][i]);
        return memoize[i][mask] = minimumCost;
    }

    // main function
    public static void main(String[] args)
    {
        // defining and initializing the resultant cost as maximum Integer value
        int cost = MAX_INT;

        // using the for-loop to iterate through the nodes
        for (int i = 1; i <= V; i++)
            // try to go from node 1 visiting all nodes in
            // between to i then return from i taking the
            // shortest route to 1
            cost = Math.min(cost, travelling_salesman_problem(i, (1 << (V + 1)) - 1) + graph[i][1]);

        // printing the total cost for the users
        System.out.println( "Minimum Cost : " + cost );
    }
}

输出

Minimum Cost : 90

说明

在上面的代码片段中，我们将一个类定义为 TSP。在此类中，我们定义了一个常量来表示顶点总数，最大整数大小以避免溢出问题，一个图，以及一个用于自顶向下递归方法的记忆化矩阵。然后我们定义了一个名为 travelling_salesman_problem() 的函数，它接受两个参数 - 第一个参数是可迭代对象，第二个参数是位掩码。在此函数中，我们定义了一个递归的基本情况，该情况仅在掩码中设置了当前位和第一位时执行，这意味着所有其他节点都已访问。之后，我们进行了记忆化，并将最小成本初始化为最大整数值。

然后我们使用 for 循环遍历掩码中的所有节点。我们递归地计算遍历掩码中除选定节点外的节点的成本，然后通过采取最短可能路径返回起始节点。对于 main 函数，我们已将结果成本初始化为最大整数值，并使用 for 循环遍历图的节点，通过为该特定节点调用 travelling_salesman_problem() 函数来计算新的最小成本，并将最小成本值设置为结果成本。最后，我们为用户打印了结果。

结果，最小权重汉密尔顿回路成本，即 90，被打印给用户。

Python中的代码实现

以下是旅行商问题算法在 Python 编程语言中的实现

文件：TSP.py

# Travelling Salesman Problem - Dynamic Programming Approach Implementation in Python

# defining the number of the nodes in the graph
V = 4

# graph[i][j] signifies the shortest distance to go from index i to index j
# we can calculate this matrix for any given graph using all-pair shortest path algorithms
graph = [
    [0, 0, 0, 0, 0],
    [0, 0, 12, 18, 24],
    [0, 12, 0, 36, 28],
    [0, 18, 36, 0, 32],
    [0, 24, 28, 32, 0]
    ]

# memoization for top-down recursion
memoize = [[-1] * (1 << (V + 1)) for _ in range(V + 1)]

# defining the recursive function to find the minimum weight Hamiltonian Cycle cost
def travelling_salesman_problem(i, mask):
    # defining the base case
    # if only ith bit and first bit is set in the mask,
    # it means we have visited all other nodes already
    if mask == ((1 << i) | 3):
        return graph[1][i]

    # performing memoization
    if memoize[i][mask] != -1:
        return memoize[i][mask]

    # initializing the minimum cost as the Maximum integer value
    minimumCost = 10 ** 9

    # we have to travel all nodes j in mask and end the path at ith node so for every node j
    # in mask, recursively estimate the cost of travelling all nodes in mask except i and
    # then travel back from node j to node i taking the shortest path take the minimum of
    # all possible j nodes
    for j in range(1, V + 1):       
        if (mask & (1 << j)) != 0 and j != i and j != 1:
            minimumCost = min(minimumCost, travelling_salesman_problem(j, mask & (~(1 << i))) + graph[j][i])
    memoize[i][mask] = minimumCost # storing the minimum value
    return minimumCost

# main function
if __name__ == "__main__":
    #  defining and initializing the resultant cost as maximum Integer value
    cost = 10 ** 9
    
    # using the for-loop to iterate through the nodes
    for i in range(1, V + 1):
        # try to go from node 1 visiting all nodes in
        # between to i then return from i taking the
        # shortest route to 1
        cost = min(cost, travelling_salesman_problem(i, (1 << (V + 1)) -1) + graph[i][1])

    # printing the total cost for the users
    print( "Minimum Cost : " + str(cost) )

输出

Minimum Cost : 90

说明

在上面的代码片段中，我们定义了一个常量来表示顶点总数，一个图，以及一个用于自顶向下递归方法的记忆化矩阵。然后我们定义了一个名为 travelling_salesman_problem() 的函数，它接受两个参数 - 第一个参数是可迭代对象，第二个参数是位掩码。在此函数中，我们定义了一个递归的基本情况，该情况仅在掩码中设置了当前位和第一位时执行，这意味着所有其他节点都已访问。之后，我们进行了记忆化，并将最小成本初始化为最大整数值。

结果，最小权重汉密尔顿回路成本，即 90，被打印给用户。

旅行商问题使用动态规划方法的时空复杂度

旅行商问题使用动态规划方法的时间复杂度为 O(N²* 2^N)，其中 O(N * 2^N) 是递归中唯一子问题的最大数量，而 O(N) 是每个节点中的转换（通过 for 循环）。
旅行商问题使用动态规划方法的空间复杂度为 O(N * 2^N)，其中 N 是节点的数量。

使用贪心方法解决旅行商问题

在以下方法中，我们将使用下面提到的步骤来解决问题

步骤 1：首先，我们将创建两个主要的数据持有者 - 第一个数据持有者将是列表，用于存储城市索引（根据城市之间距离的输入矩阵），第二个将是用于存储结果的数组。

步骤 2：在第二步中，我们将遍历给定的邻接矩阵中的所有城市，并通过检查从当前城市到达任何城市的成本是否低于当前成本来更新成本。

步骤 3：最后，我们将通过上述步骤生成最小路径回路并返回其最小成本。

用不同编程语言实现贪心方法来解决旅行商问题

既然我们已经成功理解了使用贪心方法解决旅行商问题的上述过程，现在是时候看看它在 C++、Java 和 Python 等不同编程语言中的实现了。

C++ 中的代码实现

以下是旅行商问题算法在 C++ 编程语言中的实现

文件：TSP.cpp

// Travelling Salesman Problem - Greedy Approach Implementation in C++

// including the required library
#include "bits/stdc++.h"

// using the standard namespace
using namespace std;

// defining the function to find the minimum weight Hamiltonian Cycle cost
void travelling_salesman_problem(vector<vector<int>> graph)
{
    // initializing some variables
    int cost = 0;
    int count = 0;
    int j = 0, i = 0;
    int minimumCost = INT_MAX;
    map<int, int> visitedRoutes;
    visitedRoutes[0] = 1;
    int route[graph.size()];

    // using the while loop to iterate through the elements of the given graph
    while (i < graph.size() && j < graph[i].size())
    {   
        // breaking if the count value exceeds the size of the graph
        if (count >= graph[i].size() - 1)
        {
            break;
        }
        // if the index j is not equals to index i and the selected element at index j is 0
        if (j != i && (visitedRoutes[j] == 0))
        {
            // if the value is lower than the current minimum cost
            if (graph[i][j] < minimumCost)
            {
                // updating the minimum cost and incrementing the route count
                minimumCost = graph[i][j];
                route[count] = j + 1;
            }
        }
	  // incrementing the index j value by 1
        j++;
        
        // if the index j is equal to the size of the graph
        if (j == graph[i].size())
        {
            // updating the cost by adding the minimum cost to the current cost 
            cost += minimumCost;
            // setting the minimum cost as maximum integer value
            minimumCost = INT_MAX;
            // updating the route as 1 in the visitedRoutes[] array
            visitedRoutes[route[count] - 1] = 1;
            // initializing the index j equals to 0
            j = 0;
            // initializing the index i as the route[count] - 1
            i = route[count] - 1;
            // incrementing the count value by 1
            count++;
        }
    }
    // setting the index i as route[count -1] - 1
    i = route[count - 1] - 1;

    // using the for-loop to iterate through the graph
    for (j = 0; j < graph.size(); j++)
    {
        // if the index i is not equals to j and the value of the current element of the graph is less than the minimum cost
        if ((i != j) && graph[i][j] < minimumCost)
        {
            // updating the minimum cost and selected route value
            minimumCost = graph[i][j];
            route[count] = j + 1;
        }
    }

    // adding the final evaluated minimum cost to the total cost
    cost += minimumCost;

    // printing the total cost for the users
    cout << "Minimum Cost : " << (cost);
}

// main function
int main()
{
    // defining the graph
    vector<vector<int>> graph = {
        { -1, 12, 18, 24 },
        { 12, -1, 36, 28 },
        { 18, 36, -1, 32 },
        { 24, 28, 32, -1 }
        };

    // calling the travelling_salesman_problem() function to find the minimum weight Hamiltonian Cycle cost
    travelling_salesman_problem(graph);
    return 0;
}

输出

Minimum Cost : 90

说明

在上面的代码片段中，我们包含了 'bits/stdc++.h' 头文件并使用了标准命名空间。然后我们定义了一个名为 travelling_salesman_problem() 的函数，它接受一个二维数组作为其参数。在此函数中，我们定义了一些变量并用初始值进行了初始化。然后我们使用 while 循环遍历图并计算最小成本。如果计数超过图的大小，我们还包含了一个 break 语句。我们更新了最小成本值以及路线（如果图中的选定值低于当前最小成本）。

我们还通过添加最终最小成本并重置变量来更新总成本。然后我们使用 for 循环通过评估总最小成本来生成最小路径回路，并为用户打印结果。在 main 函数中，我们使用二维向量定义了图，并调用 travelling_salesman_problem() 函数来查找最小权重汉密尔顿回路成本。

结果，最小权重汉密尔顿回路成本，即 90，被打印给用户。

Java 代码实现

以下是旅行商问题算法在 Java 编程语言中的实现

文件：TSP.java

// Travelling Salesman Problem - Greedy Approach Implementation in Java

// importing the required library
import java.util.*;

// defining the class to solve Travelling Salesman Problem
public class TSP {

    // defining the method to find the minimum weight Hamiltonian Cycle
    static void travelling_salesman_problem(int[][] graph)
    {
        // initializing some variables
        int cost = 0;
        int count = 0;
        int j = 0, i = 0;
        int minimumCost = Integer.MAX_VALUE;
        List<Integer> visitedRoutes = new ArrayList<>();
        visitedRoutes.add(0);
        int[] route = new int[graph.length];

        // using the while loop to iterate through the elements of the given graph
        while (i < graph.length && j < graph[i].length)
        {
            // breaking if the count value exceeds the size of the graph
            if (count >= graph[i].length - 1)
            {
                break;
            }
            // if the index j is not equals to index i and the selected element at index j is 0
            if (j != i && !(visitedRoutes.contains(j)))
            {
                // if the value is lower than the current minimum cost
                if (graph[i][j] < minimumCost) {
                    // updating the minimum cost and incrementing the route count
                    minimumCost = graph[i][j];
                    route[count] = j + 1;
                }
            }
            // incrementing the index j value by 1
            j++;
            
            // if the index j is equal to the size of the graph
            if (j == graph[i].length)
            {
                // updating the cost by adding the minimum cost to the current cost
                cost += minimumCost;
                // setting the minimum cost as maximum integer value
                minimumCost = Integer.MAX_VALUE;
                // updating the route as 1 in the visitedRoutes[] array
                visitedRoutes.add(route[count] - 1);
                // initializing the index j equals to 0
                j = 0;
                // initializing the index i as the route[count] - 1
                i = route[count] - 1;
                // incrementing the count value by 1
                count++;
            }
        }
        // setting the index i as route[count -1] - 1
        i = route[count - 1] - 1;
        
        // using the for-loop to iterate through the graph
        for (j = 0; j < graph.length; j++)
        {
            // if the index i is not equals to j and the value of the current element of the graph is less than the minimum cost
            if ((i != j) && graph[i][j] < minimumCost)
            {
                // updating the minimum cost and selected route value
                minimumCost = graph[i][j];
                route[count] = j + 1;
            }
        }

        // adding the final evaluated minimum cost to the total cost
        cost += minimumCost;

        // printing the result for the users
        System.out.print("Minimum Cost : ");
        System.out.println(cost);
    }

    // main function
    public static void main(String[] args)
    {
        // defining the graph
        int[][] graph = {
            { -1, 12, 18, 24 },
            { 12, -1, 36, 28 },
            { 18, 36, -1, 32 },
            { 24, 28, 32, -1 }
        };

        // calling the travelling_salesman_problem() function to find the minimum weight Hamiltonian Cycle cost
        travelling_salesman_problem(graph);
    }
}

输出

Minimum Cost : 90

说明

在上面的代码片段中，我们从 'java.util' 库导入了所有内容，并将主类定义为 TSP 来解决旅行商问题。在此类中，我们定义了一个名为 travelling_salesman_problem() 的函数，它接受一个二维数组作为其参数。在此函数中，我们定义了一些变量并用初始值进行了初始化。然后我们使用 while 循环遍历图并计算最小成本。如果计数超过图的大小，我们还包含了一个 break 语句。

如果图中的选定值低于当前最小成本，我们更新了最小成本值以及路线。我们还通过添加最终最小成本并重置变量来更新总成本。然后我们使用 for 循环通过评估总最小成本来生成最小路径回路，并为用户打印结果。在 main 函数中，我们定义了图并调用 travelling_salesman_problem() 函数来查找最小权重汉密尔顿回路成本。

结果，最小权重汉密尔顿回路成本，即 90，被打印给用户。

Python中的代码实现

以下是旅行商问题算法在 Python 编程语言中的实现

文件：TSP.py

# Travelling Salesman Problem - Greedy Approach Implementation in Python

# defining the function to find the minimum weight Hamiltonian Cycle cost
def travelling_salesman_problem(graph):

    # defining and initializing some variables
    cost = 0
    count = 0
    i = 0
    j = 0
    minimumCost = 999999999
    visitedRoutes = {}
    visitedRoutes[0] = 1
    route = [0] * len(graph)

    # using the while loop to iterate through the elements of the graph
    while i < len(graph) and j < len(graph[i]):
        
        # breaking if the count value exceeds the size of the graph
        if count >= len(graph[i]) - 1:
            break
        
        # if the index j is not equals to index i and the selected element at index j is not in visitedRoutes[] list
        if j != i and j not in visitedRoutes:
            # if the value is lower than the current minimum cost
            if graph[i][j] < minimumCost:
                # updating the minimum cost and incrementing the route count
                minimumCost = graph[i][j]
                route[count] = j + 1
        # incrementing the index j value by 1
        j += 1
        
        # if the index j is equal to the size of the graph
        if j == len(graph[i]):
            # updating the cost by adding the minimum cost to the current cost
            cost += minimumCost 
            # setting the minimum cost as a higher integer value
            minimumCost = 999999999 
            # updating the route as 1 in the visitedRoutes[] list
            visitedRoutes[route[count] - 1] = 1 
            # initializing the index j equals to 0
            j = 0
            # initializing the index i as the route[count] - 1
            i = route[count] - 1 
            # incrementing the count value by 1
            count += 1
    
    # setting the index i as route[count -1] - 1
    i = route[count - 1] - 1 

    # using the for-loop to iterate through the graph
    for  j in range(0, len(graph)):
        # if the index i is not equals to j and the value of the current element of the graph is less than the minimum cost
        if i != j and graph[i][j] < minimumCost:
            # updating the minimum cost and selected route value
            minimumCost = graph[i][j]
            route[count] = j + 1 
    
    # adding the final evaluated minimum cost to the total cost
    cost += minimumCost 
    print("Minimum Cost :", cost)

# main function 
if __name__ == '__main__':
    
    # defining the graph
    graph =  [
        [-1, 12, 18, 24],
        [12, -1, 36, 28],
        [18, 36, -1, 32],
        [24, 28, 32, -1]
        ]
    
    # calling the travelling_salesman_problem() function to find the minimum weight Hamiltonian Cycle cost
    travelling_salesman_problem(graph)

输出

Minimum Cost : 90

说明

在上面的代码片段中，我们将主类定义为 TSP 来解决旅行商问题。在此类中，我们定义了一个名为 travelling_salesman_problem() 的函数，它接受一个二维列表作为其参数。在此函数中，我们定义了一些变量并用初始值进行了初始化。然后我们使用 while 循环遍历图并计算最小成本。如果计数超过图的大小，我们还包含了一个 break 语句。

结果，最小权重汉密尔顿回路成本，即 90，被打印给用户。

旅行商问题使用贪心方法的时空复杂度

旅行商问题使用贪心方法的时间复杂度为 O(N² * log N)，其中 N 是城市的数量。
旅行商问题使用贪心方法的空间复杂度为 O(N)。

下一个主题Kosaraju 算法

Travelling Salesman Problem

理解旅行商问题

旅行商问题示例 1

旅行商问题示例 2

旅行商问题的解决方案

使用简单方法解决旅行商问题

用不同编程语言实现简单方法来解决旅行商问题

C++ 中的代码实现

Java 代码实现

Python中的代码实现

旅行商问题使用简单方法的时空复杂度

使用动态规划方法解决旅行商问题

注意：节点 1 必须存在于每个子集中。

用不同编程语言实现动态规划方法来解决旅行商问题

注意：忽略第零位，因为图是基于 1 的。

C++ 中的代码实现

Java 代码实现

Python中的代码实现

旅行商问题使用动态规划方法的时空复杂度

使用贪心方法解决旅行商问题

用不同编程语言实现贪心方法来解决旅行商问题

C++ 中的代码实现

Java 代码实现

Python中的代码实现

旅行商问题使用贪心方法的时空复杂度

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

DAA 教程

渐进分析

复发

排序分析

分而治之

排序

下界理论

线性时间排序

哈希

二叉搜索树

红黑树

动态规划

贪婪算法

回溯

最小生成树

最短路径

所有对最短路径

最大流

排序网络

复杂度理论

近似算法

字符串匹配

面试题

其他

Travelling Salesman Problem

理解旅行商问题

旅行商问题示例 1

旅行商问题示例 2

旅行商问题的解决方案

使用简单方法解决旅行商问题

用不同编程语言实现简单方法来解决旅行商问题

C++ 中的代码实现

Java 代码实现

Python中的代码实现

旅行商问题使用简单方法的时空复杂度

使用动态规划方法解决旅行商问题

注意：节点 1 必须存在于每个子集中。

用不同编程语言实现动态规划方法来解决旅行商问题

注意：忽略第零位，因为图是基于 1 的。

C++ 中的代码实现

Java 代码实现

Python中的代码实现

旅行商问题使用动态规划方法的时空复杂度

使用贪心方法解决旅行商问题

用不同编程语言实现贪心方法来解决旅行商问题

C++ 中的代码实现

Java 代码实现

Python中的代码实现

旅行商问题使用贪心方法的时空复杂度

相关帖子

如何编写算法

Ford Fulkerson 算法

Dijkstra 算法

Kruskals 算法的时间复杂度

二分搜索算法

Floyd-Warshall 算法

欧几里德算法

排序算法：最慢到最快

Kosaraju 算法

算法示例