如何在TSP最近邻算法的路径数组末尾追加源顶点并计算总距离

我需要程序满足旅行商问题（Travelling Salesman Problem）的规则：访问所有顶点后返回源节点，同时将最后一个节点到源节点的距离计入总距离。目前在主类中新增City对象时，程序会计算最短距离将其直接放在源节点A之后。

当前程序输出路径为[A, D, C, B]，但期望输出为[A,D,C,B,A]，需要返回源节点并按规则统计距离，现有逻辑不会计算最后一段返程距离，当前总距离计算结果为23，期望得到的总距离为28。

NearestNeighbour类 #

import java.util.ArrayList;
import java.util.Arrays;
public class NearestNeighbour {
    public Route findShortestRoute(ArrayList<City> cities) {
        ArrayList<City> shortestRouteCities = new ArrayList<City>(cities.size());
        System.out.println("-----------------------------------------------------------------------------");
        System.out.println("Initial Route           ==> " + Arrays.toString(cities.toArray()));
        System.out.println("w/ total distance: " + new Route(cities).calculateTotalDistance());
        System.out.println("-----------------------------------------------------------------------------");
        City city = cities.get(0);
        updateRoutes(shortestRouteCities, cities, city);
        while (cities.size() >= 1) {
            city = getNextCity(cities, city);
            updateRoutes(shortestRouteCities, cities, city);
        }
        return new Route(shortestRouteCities);
    }
    private void updateRoutes(ArrayList<City> shortestRouteCities, ArrayList<City> cities, City city) {
        shortestRouteCities.add(city);
        cities.remove(city);
        System.out.println("Cities In Shortest Route ==> " + Arrays.toString(shortestRouteCities.toArray()));
        System.out.println("Remaining Cities         ==> " + Arrays.toString(cities.toArray()) + "\n");
    }
    private City getNextCity(ArrayList<City> cities, City city) {
        return cities.stream().min((city1, city2) -> {
            int flag = 0;
            if (city1.measureDistance(city) < city2.measureDistance(city)) flag = -1;
            else if (city1.measureDistance(city) > city2.measureDistance(city)) flag = 1;
            return flag;
        }).get();
    }
}

Driver类 #

import java.util.ArrayList;
import java.util.Arrays;

public class Driver {
    private ArrayList<City> initialCities = new ArrayList<City>(Arrays.asList(
            new City("A", 1.0, 1.0),
            new City("B", 2.0, 9.0),
            new City("C", 6.0, 6.0),
            new City("D", 7.0, 2.0)
  
            //new City("Denver", 39.7392, -104.9903),
            //new City("Los Angeles", 34.0522, -118.2437),
            //new City("Chicago", 41.8781, -87.6298),
            //new City("New York", 40.7128, -74.0059),
            //new City("Dallas", 32.7767, -96.7970),
            //new City("Seattle", 47.6062, -122.3321)
        //new City("Sydney", -33.8675, 151.2070),
        //new City("Tokyo", 35.6895, 139.6917(,
        //new City("Cape Town", -33.9249, 18.4241)
    ));
    

    public static void main(String[] args) {
        Driver driver = new Driver();
        ArrayList<City> cities = new ArrayList<City>();
        cities.addAll(driver.initialCities);
        driver.printShortestRoute(new NearestNeighbour().findShortestRoute(cities));
        
    }
    
    private void printShortestRoute(Route shortestRoute){
        System.out.println("-----------------------------------------------------------------------------");
        System.out.println("Shortest route found so far: " + shortestRoute);
        System.out.println("w/ total distance: " + shortestRoute.calculateTotalDistance());
        System.out.println("-----------------------------------------------------------------------------");
    }
}

问题出在路径生成逻辑没有形成闭环，遍历完所有城市后没有将起点加回路线末尾，只需要修改NearestNeighbour类的findShortestRoute方法即可，不需要改动其他代码：

1. 新增变量保存初始起点
2. 所有城市遍历完成后，将起点添加到路线列表末尾
3. 初始化路线列表时多预留1个位置存放返程起点

修改后的findShortestRoute方法代码如下：

public Route findShortestRoute(ArrayList<City> cities) {
    // 多预留1个位置存放返程的起点
    ArrayList<City> shortestRouteCities = new ArrayList<City>(cities.size() + 1);
    System.out.println("-----------------------------------------------------------------------------");
    System.out.println("Initial Route           ==> " + Arrays.toString(cities.toArray()));
    System.out.println("w/ total distance: " + new Route(cities).calculateTotalDistance());
    System.out.println("-----------------------------------------------------------------------------");
    City city = cities.get(0);
    // 保存初始起点，用于后续返程闭环
    City startCity = city;
    updateRoutes(shortestRouteCities, cities, city);
    while (cities.size() >= 1) {
        city = getNextCity(cities, city);
        updateRoutes(shortestRouteCities, cities, city);
    }
    // 将起点添加到路线末尾，完成TSP闭环
    shortestRouteCities.add(startCity);
    // 打印最终添加完起点的路线信息
    System.out.println("Cities In Shortest Route ==> " + Arrays.toString(shortestRouteCities.toArray()));
    System.out.println("Remaining Cities         ==> " + Arrays.toString(cities.toArray()) + "\n");
    return new Route(shortestRouteCities);
}

修改后路线会自动补充末尾的源节点，Route类的calculateTotalDistance方法会自动计算最后一个节点到源节点的距离，最终得到的路径为[A,D,C,B,A]，总距离为28，符合预期。

内容的提问来源于stack exchange，提问作者Nisar Fakiri