Programming - Java - Travelling Salesman Problem Solution (Naive Algorithm)

avatar

[Image 1]

Introduction

Hey it's a me again drifter1!

Today we continue with the Java Graph Algorithm series in order to cover the Travelling Salesman Problem (TSP) and one of the Algorithms (Naive) that solve it. Of course, more posts will follow, which will cover other more interesting and more practical algorithms.

Let's also note that the previous part of the series was back in 2018, and still on Steemit, so getting back to this series is very exciting for me!

So, without further ado, let's get straight into it!


GitHub Repository


Requirements - Prerequisites

  • Knowledge of the Programming Language "Java"
  • Familiarity with Graph Theory
  • Previous Articles of the Series

Travelling Salesman Problem

The TSP problem can be described as follows:

"A salesman wants to visit a list of cities. Between each pair of cities there is a specific traveling cost. Each city has to be visited once and the tour starts and ends at the same city. What's the best possible route for minimizing travelling costs?"

This is basically an Hamiltonian cycle problem, where each city is a vertex, and visited exactly once during the tour. The main difference between a plain Hamiltonian cycle problem and TSP is that we have to find the minimum weight Hamiltonian Cycle of the given Graph, and not just any valid Hamiltonian Cycle.

The problem is classified as NP-hard, which means that there is no polynomial-time solution for it, but it's possible to approximate of course!


Naive Algorithm

The simplest algorithmic solution for the problem is the following:

  1. Consider some city (vertex) as the start and end point (for example the 1st one)
  2. Generate all permutations of the n cities (vertices), which are (n-1)!
  3. Calculate the travelling cost of every permutation
  4. Find the minimum cost permutation and return it

This algorithm has a huge factorial complexity, Θ(n!).


Naive Algorithm Implementation

Let's consider only the case of a complete undirected graph for the implementation. A complete graph is a graph where every distinct pair of vertices is connected by one edge.

Let's use a simple adjacency matrix implementation in order to store the weights of the edges.

The Graph implementation is as follows:

import java.util.List;
import java.util.ArrayList;

public class Graph {
    private int vCount;
    private int[][] adj;

    public int getvCount() {
        return vCount;
    }

    public int[][] getAdj() {
        return adj;
    }

    public Graph(int vCount) {
        this.vCount = vCount;
        adj = new int[vCount][vCount];
        for (int i = 0; i < vCount; i++) {
            for (int j = 0; j < vCount; j++) {
                if (i != j) {
                    adj[i][j] = 0;
                }

            }
        }
    }

    public void addEdge(int i, int j, int weight) {
        adj[i][j] = weight;
        adj[j][i] = weight;
    }

    public void removeEdge(int i, int j) {
        adj[i][j] = 0;
        adj[j][i] = 0;
    }

    public boolean hasEdge(int i, int j) {
        if (adj[i][j] != 0) {
            return true;
        }
        return false;
    }

    public List<Integer> neighbours(int vertex) {
        List<Integer> edges = new ArrayList<Integer>();
        for (int i = 0; i < vCount; i++)
            if (hasEdge(vertex, i))
                edges.add(i);
        return edges;
    }

    public void printGraph() {
        for (int i = 0; i < vCount; i++) {
            List<Integer> edges = neighbours(i);
            System.out.print(i + ": ");
            for (int j = 0; j < edges.size(); j++) {
                System.out.print(edges.get(j) + " ");
            }
            System.out.println();
        }
    }
}

Now for the TSP solution. Starting from the first vertex (city) we have to generate all possible permutations, calculate the cost and keep track of the best solution.

The solution / permutation is a integer list which starts and ends with 0:

List<Integer> permutation = new ArrayList<Integer>();
for (int i = 0; i < v; i++){
    permutation.add(i);
}
permutation.add(0);

The travel cost is calculated using a function for that purpose called calcTravelCost(), which simply adds up the weights of the given permutation:

public static int calcTravelCost(Graph g, List<Integer> permutation){
    int[][] adj = g.getAdj();
    int v = g.getvCount();
    int travelCost = 0;
    
    for(int i = 0; i < v; i++){
        int startIndex = permutation.get(i);
        int endIndex = permutation.get(i + 1);
        travelCost += adj[startIndex][endIndex];
    }
    
    return travelCost;
}

As such, the travel cost is always simply:

int travelCost = calcTravelCost(g, permutation);

Swapping two vertices is done using yet another utility function swapVertices(), which is defined as:

public static void swapVertices(List<Integer> permutation, int indexA, int indexB){ 
    int valueA = permutation.get(indexA);
    int valueB = permutation.get(indexB);
    
    permutation.set(indexA, valueB);
    permutation.set(indexB, valueA);
}

Permutations require a recursive function, which in this implementation is called permute() and keeps track of the solution / best permutation by storing it in a global variable.

public static void permute(Graph g, List<Integer> permutation, int l, int r){
    if (l == r){
        int travelCost = calcTravelCost(g, permutation);
        
        System.out.println("\nPermutation: " + travelCost);
        for (int i = 0; i < permutation.size(); i++){
            System.out.print(permutation.get(i) + " ");
        }
        System.out.println();           
        
        if (travelCost < bestTravelCost){
            bestTravelCost = travelCost;
            for (int i = 0; i < solution.size(); i++){
                solution.set(i, permutation.get(i));
            }
        }
    }
    else{
        for (int i = l; i <= r; i++){
            swapVertices(permutation, l, i);
            permute(g, permutation, l+1, r);
            swapVertices(permutation, l, i);
        }
    }
}

It's not too difficult to understand!


Testing out the Algorithm

In the TestGraphs class, we create a simple graph of 5 vertices.

Graph g = new Graph(5);
        
// add Edges
g.addEdge(0, 1, 5);
g.addEdge(0, 2, 2);
g.addEdge(0, 3, 3);
g.addEdge(0, 4, 4);
g.addEdge(1, 2, 3);
g.addEdge(1, 3, 2);
g.addEdge(1, 4, 2);
g.addEdge(2, 3, 2);
g.addEdge(2, 4, 4);
g.addEdge(3, 4, 1);

Calling the TSP Naive Algorithm on it (TSPNaive(g);) yields the following solution:

Solution: 11
0 2 1 4 3 0

And so the best route has a travelling cost of 11.

I suggest you to check out the respective code on GitHub!


RESOURCES:

References

  1. https://www.geeksforgeeks.org/travelling-salesman-problem-set-1/

Images

  1. https://commons.wikimedia.org/wiki/File:GLPK_solution_of_a_travelling_salesman_problem.svg

Previous articles of the series


Final words | Next up

And this is actually it for today's post!

Next time we will get into other algorithmic solutions for the same problem!

See ya!

Keep on drifting!

Posted with STEMGeeks



0
0
0.000
6 comments
avatar

This post has been manually curated by @steemflow from Indiaunited community. Join us on our Discord Server.

Do you know that you can earn a passive income by delegating to @indiaunited. We share 100 % of the curation rewards with the delegators.

Here are some handy links for delegations: 100HP, 250HP, 500HP, 1000HP.

Read our latest announcement post to get more information.

image.png

Please contribute to the community by upvoting this comment and posts made by @indiaunited.

0
0
0.000
avatar

Well this tutorial will be good for somebody that needs to solve this type of problem in Java, I heard that people are starting to run away from Java, but still is valid to learn a bit about it.
!1UP

0
0
0.000
avatar
(Edited)

I don't think that Java is as bad as people make it to be...

There is mostly only a small difference between the programming languages used today, and so we just have to live in a world with lots of different programming languages in our disposal.

I'm not that much into the whole idea of having everything in simpler languages such as Python. Adding too much user-friendliness has a negative effect, as it limits what we can do as programmers...

I like using Python only for prototyping, and switch into C/C++ when I want efficient code.

Also, I don't think that this implementation was too Java-ish, as it can easily be translated into any other object-oriented language...

Anyways, thanks for your comment! Have a nice day!

0
0
0.000