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

[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

• https://github.com/drifter1/javagraphalgorithms

---

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

• Introduction → Graph Theory and Implementation
• Traversal Algorithms → BFS and DFS Traversal Algorithms
• Minimum Spanning Tree Algorithms → Prim and Kruskal MST Algorithms
• Shortest Path Algorithm (Dijkstra) → Dijkstra Algorithm
• Shortest Path Algorithm (Bellman-Ford) → Bellman-Ford Algorithm
• All Pair Shortest Path Algorithms (Floyd-Warshall/Johnson) → Floyd-Warshall and Johnson Algorithms
• Maximum Flow Algorithm (Ford-Fulkerson) → Ford-Fulkerson Algorithm
• (Backtracking) Hamiltonian Circuit Algorithm → Backtracking Hamiltonian Cycle Algorithm
• Eulerian Circuit Detection Algorithm → Eulerian Cycle Detection Algorithm
• Minimum Spanning Tree Algorithms 2 → Boruvka and Reverse Delete Algorithms
• Coloring Algorithms (Backtracking and Greedy) → Greedy and Backtracking Graph Coloring Algorithms

---

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