Find the final path of Traveling Salesman Problem

Question

I am trying to implement the Traveling Salesman Problem and I need to return the path that lead to the minimum cost. I have a distance matrix, and this is the code:

static int TSP(int[][] distance, boolean[] visitCity, int currPos, int cities, int count, int cost, int result)
{
    if (count == cities && distance[currPos][0] > 0) {

        result = Math.min(result, cost + distance[currPos][0]);

        return result;
    }
    
    for (int i = 0; i < cities; i++)
    {
        if (visitCity[i] == false && distance[currPos][i] > 0)
        {
            visitCity[i] = true;

            result = TSP(distance, visitCity, i, cities, count + 1, cost + distance[currPos][i], result);

            visitCity[i] = false;
        }
    }
    return result;
}

I call this method like this:

boolean[] visitCity = new boolean[cities];
visitCity[0] = true;
int result = Integer.MAX_VALUE;
result = TSP(distance, visitCity, 0, cities, 1, 0, result);

In the end, the algorithm print the cost of the path, but I also need it to print the path that lead to this. Like "0->1->3->2->etc->0". Is there any posibility to achieve that?

Answer 1

I remodeled your algorithm into ObjectOriented stlye, to prevent passing too many arguments, and ease access to result values.

I could have returned Pair<costs, path>, but the OO style fits better in Java and allows easier access/maintenance.

The test method (main) print the calculated distance matrix first, then uses each city as starting and end place and prints the results for it.

Note that instead of the Stack<Integer> path tracer I am now using indexed arrays, they are faster and easier to rewrite.

package snippet;

import java.awt.Point;
import java.text.DecimalFormat;
import java.util.ArrayList;
import java.util.Arrays;

public class SimpleTSP {



    public static void main(final String[] args) {
        final int cityCount = 5;
        final ArrayList<Point> cities = buildCities(cityCount);
        final SimpleTSP tsp = new SimpleTSP(cities);

        // run multiple times, take each city as a starting point once
        for (int i = 0; i < cities.size(); i++) {
            tsp.runTSP(i);
            tsp.printBestPath();
        }
    }



    static private ArrayList<Point> buildCities(final int pCityCount) {
        final ArrayList<Point> ret = new ArrayList<>(pCityCount);
        ret.add(new Point(4, 2));
        ret.add(new Point(1, 5));
        ret.add(new Point(5, 1));
        ret.add(new Point(0, 0));
        ret.add(new Point(3, 3));
        ret.add(new Point(2, 4));
        return ret;
    }

    static private float[][] buildDistanceMatrix(final ArrayList<Point> pCities) {
        final float[][] ret = new float[pCities.size()][pCities.size()];
        for (int outerIndex = 0; outerIndex < pCities.size(); outerIndex++) {
            final Point oc = pCities.get(outerIndex);

            for (int innerIndex = 0; innerIndex < pCities.size(); innerIndex++) {
                if (outerIndex == innerIndex) continue;

                final Point ic = pCities.get(innerIndex);
                final float dist = (float) Math.sqrt(Math.pow(ic.x - oc.x, 2) + Math.pow(ic.y - oc.y, 2));
                ret[outerIndex][innerIndex] = dist;
                ret[innerIndex][outerIndex] = dist;
            }
        }
        return ret;
    }

    private static void printDistancMatrix(final float[][] pMatrix) {
        final DecimalFormat df = new DecimalFormat("#.##");
        for (int o = 0; o < pMatrix.length; o++) {
            for (int i = 0; i < pMatrix[o].length; i++) {
                System.out.print(df.format(pMatrix[o][i]) + "\t");
            }
            System.out.println();
        }
    }



    /*
     * OBJECT
     */

    private final ArrayList<Point>  mCities;
    private final float[][]         mDistanceMatrix;
    private final boolean[]         mVisitedCities;

    private int         mStartAndEndTownIndex;
    private final int[] mCurrentPath;

    private int[]   mBestPath;
    private float   mBestPathCosts;

    public SimpleTSP(final ArrayList<Point> pCities) {
        mCities = pCities;
        mDistanceMatrix = buildDistanceMatrix(mCities);
        mVisitedCities = new boolean[mCities.size()];
        mCurrentPath = new int[mCities.size()];
        printDistancMatrix(mDistanceMatrix);
    }



    public float runTSP(final int pStartAndEndTownIndex) {
        mStartAndEndTownIndex = pStartAndEndTownIndex;
        for (int i = 0; i < mVisitedCities.length; i++)
            mVisitedCities[i] = false;
        mVisitedCities[pStartAndEndTownIndex] = true;
        mCurrentPath[0] = pStartAndEndTownIndex;
        mBestPathCosts = Float.MAX_VALUE;
        TSP(pStartAndEndTownIndex, 1, 0);
        return mBestPathCosts;
    }


    private float TSP(final int pCurrentCity, final int pCityCounter, final float pCurrentTotalCost) {
        // all cities visited, now return to start city and end with temporary result
        if (pCityCounter >= mVisitedCities.length) {
            final float distanceToStartTown = mDistanceMatrix[pCurrentCity][mStartAndEndTownIndex];
            if (distanceToStartTown > 0) return pCurrentTotalCost + distanceToStartTown;
        }

        float localResult = Float.MAX_VALUE;
        for (int i = 0; i < mVisitedCities.length; i++) {
            if (mVisitedCities[i] == false && pCurrentCity != i) { // do not re-visit visited city or yourself
                mVisitedCities[i] = true;
                mCurrentPath[pCityCounter] = i;
                localResult = TSP(i, pCityCounter + 1, pCurrentTotalCost + mDistanceMatrix[pCurrentCity][i]);
                mVisitedCities[i] = false;
                if (localResult < mBestPathCosts) {
                    mBestPathCosts = localResult;
                    mBestPath = Arrays.copyOf(mCurrentPath, mCurrentPath.length);
                }
            }
        }
        return localResult;
    }



    public void printBestPath() {
        System.out.print("Best path: (" + mBestPathCosts + " costs): ");
        for (final int i : mBestPath) {
            System.out.print(i + " -> ");
        }
        System.out.println(mStartAndEndTownIndex);
    }
    public int[] getBestPath() {
        return mBestPath;
    }
    public float getBestPathCosts() {
        return mBestPathCosts;
    }



}

I ran my test with this sexy piece of map to prevent possible first-choice-errors on local minimums:

Output:

0   4,24    1,41    4,47    1,41    2,83    
4,24    0   5,66    5,1 2,83    1,41    
1,41    5,66    0   5,1 2,83    4,24    
4,47    5,1 5,1 0   4,24    4,47    
1,41    2,83    2,83    4,24    0   1,41    
2,83    1,41    4,24    4,47    1,41    0   
Best path: (15.854893 costs): 0 -> 2 -> 3 -> 1 -> 5 -> 4 -> 0
Best path: (15.854892 costs): 1 -> 3 -> 2 -> 0 -> 4 -> 5 -> 1
Best path: (15.854892 costs): 2 -> 3 -> 1 -> 5 -> 4 -> 0 -> 2
Best path: (15.854893 costs): 3 -> 1 -> 5 -> 4 -> 0 -> 2 -> 3
Best path: (15.854893 costs): 4 -> 0 -> 2 -> 3 -> 1 -> 5 -> 4
Best path: (15.854893 costs): 5 -> 1 -> 3 -> 2 -> 0 -> 4 -> 5

Answer 2

So, before giving a possible solution to your question i want to say, if you don't already know, that the Travelling Salesman Problem is known as an NP-hard problem (here's the first result for the search but there's many research papers about this question: https://en.wikipedia.org/wiki/Travelling_salesman_problem).

Anyway i'll threat the problem reducing it to a more easier and specific one: how to get the path made by the salesman? This problem is solved in many different ways (save path to a data structure as a list, queue or a simple array), a way to do it is this i link down below Java: Efficient way to print shortest path in 2d Matrix You could also use a tree instead of the matrix and mark down the leaves you chose, otherwise you can also create the tree and cut down the nodes that are not part of the solution.