Travelling Salesman Problem

Definition

Definition

The Travelling Salesman Problem (TSP) is a classic problem in computer science and operations research where the objective is to find the shortest possible route that visits a given set of cities and returns to the original city. It's an NP-hard problem, meaning there is no known polynomial-time solution for large inputs. However, there are several approaches and algorithms to approximate the solution

Explanation

Works by exhaustively evaluating all possible routes or by using heuristics to find an approximate solution. One common approach is the brute-force method, where all possible permutations of city visits are generated and the shortest route is selected. Another popular approach is the nearest neighbor algorithm, where the salesman starts at a random city and repeatedly visits the nearest unvisited city until all cities are visited

Guidance

• Start at any city
  • choose the nearest unvisited city to the current city
  • add the selected city to the route
  • repeat steps until all cities are visited
• Once all cities are visited, return to the starting city to complete the route

Tips

• implementing memoization techniques can significantly improve the performance of the brute-force approach by avoiding redundant calculations
• using dynamic programming, particularly in cases where subproblems overlap, can help optimize the solution
• experiment with different heuristics, such as the nearest insertion or farthest insertion algorithms, to find a good balance between accuracy and efficiency

Practice

Practice

tsp_brute_force(graph, current_city, visited_cities):
  if all cities visited:
    return distance from current_city to starting_city
  else:
    min_distance = INFINITY
    for each city in graph:
      if city not in visited_cities:
        distance = tsp_brute_force(graph, city, visited_cities + [city])
        min_distance = min(min_distance, distance + distance from current_city to city)
    return min_distance

Solution

package main

import (
    "math"
)

func tsp(graph [][]int, visited []bool, current, n, count, cost, ans int) int {
    if count == n && graph[current][0] > 0 {
        ans = int(math.Min(float64(ans), float64(cost+graph[current][0])))
        return ans
    }

    for i := 0; i < n; i++ {
        if !visited[i] && graph[current][i] > 0 {
            visited[i] = true
            ans = tsp(graph, visited, i, n, count+1, cost+graph[current][i], ans)
            visited[i] = false
        }
    }
    return ans
}

import java.util.Arrays;

public class TSP {

  static int tsp(int[][] graph, boolean[] visited, int current, int n, int count, int cost, int ans) {
    if (count == n && graph[current][0] > 0) {
      ans = Math.min(ans, cost + graph[current][0]);
      return ans;
    }

    for (int i = 0; i < n; i++) {
      if (!visited[i] && graph[current][i] > 0) {
        visited[i] = true;
        ans = tsp(graph, visited, i, n, count + 1, cost + graph[current][i], ans);
        visited[i] = false;
      }
    }
    return ans;
  }
}

function tsp(graph, visited, current, n, count, cost, ans) {
  if (count === n && graph[current][0] > 0) {
    ans = Math.min(ans, cost + graph[current][0]);
    return ans;
  }

  for (let i = 0; i < n; i++) {
    if (!visited[i] && graph[current][i] > 0) {
      visited[i] = true;
      ans = tsp(graph, visited, i, n, count + 1, cost + graph[current][i], ans);
      visited[i] = false;
    }
  }
  return ans;
}

fun tsp(graph: Array<IntArray>, visited: BooleanArray, current: Int, n: Int, count: Int, cost: Int, ans: Int): Int {
    if (count == n && graph[current][0] > 0) {
        return minOf(ans, cost + graph[current][0])
    }

    var newAns = ans
    for (i in 0 until n) {
        if (!visited[i] && graph[current][i] > 0) {
            visited[i] = true
            newAns = tsp(graph, visited, i, n, count + 1, cost + graph[current][i], newAns)
            visited[i] = false
        }
    }
    return newAns
}

def tsp(graph, visited, current, n, count, cost, ans):
    if count == n and graph[current][0] > 0:
        return min(ans, cost + graph[current][0])

    for i in range(n):
        if not visited[i] and graph[current][i] > 0:
            visited[i] = True
            ans = tsp(graph, visited, i, n, count + 1, cost + graph[current][i], ans)
            visited[i] = False
    return ans

use std::cmp;

fn tsp(graph: &Vec<Vec<i32>>, visited: &mut Vec<bool>, current: usize, n: usize, count: usize, cost: i32, ans: i32) -> i32 {
    if count == n && graph[current][0] > 0 {
        return cmp::min(ans, cost + graph[current][0]);
    }

    let mut new_ans = ans;
    for i in 0..n {
        if !visited[i] && graph[current][i] > 0 {
            visited[i] = true;
            new_ans = tsp(graph, visited, i, n, count + 1, cost + graph[current][i], new_ans);
            visited[i] = false;
        }
    }
    new_ans
}

function tsp(
  graph: number[][],
  visited: boolean[],
  current: number,
  n: number,
  count: number,
  cost: number,
  ans: number,
): number {
  if (count === n && graph[current][0] > 0) {
    return Math.min(ans, cost + graph[current][0]);
  }

  let newAns = ans;
  for (let i = 0; i < n; i++) {
    if (!visited[i] && graph[current][i] > 0) {
      visited[i] = true;
      newAns = tsp(
        graph,
        visited,
        i,
        n,
        count + 1,
        cost + graph[current][i],
        newAns,
      );
      visited[i] = false;
    }
  }
  return newAns;
}