Java 中的旅行商问题

2025 年 5 月 6 日 | 阅读 3 分钟

在 Java 中，旅行商问题是指我们需要找到一条经过每个城市恰好一次并返回起点的最短路线。汉密尔顿回路是 Java 中另一个与旅行商问题非常相似的问题。

TSP 和汉密尔顿回路之间的主要区别在于，在汉密尔顿回路中，我们不确定是否存在一条访问每个城市恰好一次的回路，并且我们需要确定它。在旅行商问题中，由于图是完全图，因此始终存在一个汉密尔顿回路，问题在于找到具有最小权重的汉密尔顿回路。

让我们以旅行商问题为例来理解这个问题。

在上图中，a, b, c, d, e, f, 和 g 是城市，我们需要找到具有最小权重的汉密尔顿回路。有几条汉密尔顿回路，其中一些如下：

a -> b -> c -> d -> e -> f-> g -> a
a -> c -> b -> d -> e -> f -> g -> a
a -> g -> c -> e -> f-> d -> b -> a

每个汉密尔顿回路的权重可能不同，现在我们的任务是找到那条距离最短的路线。

实现旅行商问题的步骤

以下是我们在 Java 中实现 TSP 程序的步骤：

我们将一个城市视为起点和终点。由于路线是循环的，我们可以选择任何城市作为起点。
以 DFS 的方式，我们开始从源节点遍历到其相邻节点。
计算每次遍历的成本，并跟踪最小成本，同时不断更新存储的最小成本值。
最后，返回具有最小成本的排列。

让我们通过上述步骤来实现 TSP 的 Java 代码

TSPExample.java

// import required classes and packages
import Java.util.*; 
import java.io.*; 
import java.util.Scanner;

// create TSPExample class to implement TSP code in Java
class TSPExample 
{
	// create findHamiltonianCycle() method to get minimum weighted cycle 
    static int findHamiltonianCycle(int[][] distance, boolean[] visitCity, int currPos, int cities, int count, int cost, int hamiltonianCycle) 
    {
  
        if (count == cities && distance[currPos][0] > 0) 
        {
            hamiltonianCycle = Math.min(hamiltonianCycle, cost + distance[currPos][0]);
            return hamiltonianCycle;
        }
  
        // BACKTRACKING STEP
        for (int i = 0; i < cities; i++) 
        {
            if (visitCity[i] == false && distance[currPos][i] > 0) 
            {
  
                // Mark as visited
                visitCity[i] = true;
                hamiltonianCycle = findHamiltonianCycle(distance, visitCity, i, cities, count + 1, cost + distance[currPos][i], hamiltonianCycle);
  
                // Mark ith node as unvisited
                visitCity[i] = false;
            }
        }
        return hamiltonianCycle;
    }
  
    // main() method start
    public static void main(String[] args)
    {
		int cities;
		
		//create scanner class object to get input from user
		Scanner sc = new Scanner(System.in);
		
        // get total number of cities from the user
		System.out.println("Enter total number of cities ");
		cities = sc.nextInt();
		
		
		//get distance of cities from the user
		int distance[][] = new int[cities][cities];
		for( int i = 0; i < cities; i++){
			for( int j = 0; j < cities; j++){
				System.out.println("Distance from city"+ (i+1) +" to city"+ (j+1) +": ");
				distance[i][j] = sc.nextInt();
			}
		}
  
        // create an array of type boolean to check if a node has been visited or not
        boolean[] visitCity = new boolean[cities];
  
        // by default, we make the first city visited
        visitCity[0] = true;
		
		
        int hamiltonianCycle = Integer.MAX_VALUE;
  
        // call findHamiltonianCycle() method that returns the minimum weight Hamiltonian Cycle
        hamiltonianCycle = findHamiltonianCycle(distance, visitCity, 0, cities, 1, 0, hamiltonianCycle);
  
        // print the minimum weighted Hamiltonian Cycle
        System.out.println(hamiltonianCycle);
    }
}

输出