CODEWITHSUNDEEP
pythonarrayslistalgorithm
Sam333
Sam333

Reputation: 341

Dummy node for Traveling Salesman Problem

Recently I have been reading a lot about TSP, and I need to create a variation of TSP where

  1. I don't care about starting point (can be any city) and
  2. The ending city does not need to be the same as starting city

Apparently, this can be achieved using a dummy node - with distance of 0 to every other node: source Does it mean that with input: cityA, cityB, cityC, cityD, cityE the matrix representation should look like:

[
[0,9,6,1,3]
[9,0,4,2,1]
[6,4,0,9,1]
[1,2,9,0,8]
[3,1,1,8,0]
[0,0,0,0,0]
]

Is this the correct way, if not then why? I am still confused about understanding why does the extra dummy node work in order to get the path with my variation. Thank you

Upvotes: 0

Views: 638

Answers (1)

LPR
LPR

Reputation: 390

Per the comment above, here is an example without the dummy node:

import functools
import math

def shortest_path(arr):
    
    n = len(arr)
    bitmask = [1 << i for i in range(n)]
    target = (1 << n) - 1
    
    @functools.lru_cache(None)
    def helper(city, visited):
        nonlocal target, n
        
        if visited == target:
            return 0, [city]
        
        best = math.inf, []
        for neigh in range(n):
            if not (visited & bitmask[neigh]):
                cost, path = helper(neigh, visited | bitmask[neigh])
                cost += arr[city][neigh]
                path = [city] + path
                if cost < best[0]:
                    best = cost, path
        return best
    
    best, best_path = math.inf, []
    for start in range(n):
        total_distance, path = helper(start, bitmask[start])
        if total_distance < best:
            best, best_path = total_distance, path
    
    return best, best_path

def shortest_path_padded(arr):
    n = len(arr)
    bitmask = [1 << i for i in range(n)]
    target = (1 << n) - 1
    
    @functools.lru_cache(None)
    def helper(city, visited):
        nonlocal target, n
        
        if visited == target:
            return 0, [city]
        
        best = math.inf, []
        for neigh in range(n):
            if not (visited & bitmask[neigh]):
                cost, path = helper(neigh, visited | bitmask[neigh])
                cost += arr[city][neigh]
                path = [city] + path
                if cost < best[0]:
                    best = cost, path
        return best
    
    return helper(0, bitmask[0])


if __name__ == "__main__":
    arr = [
            [0,9,6,1,3],
            [9,0,4,2,1],
            [6,4,0,9,1],
            [1,2,9,0,8],
            [3,1,1,8,0]
          ]
    arr2 = [[0]*(len(arr[0])+1)] + [[0] + row for row in arr]
    
    print(shortest_path(arr))
    print(shortest_path_padded(arr2))

Out: (5, [0, 3, 1, 4, 2])
Out: (5, [0, 1, 4, 2, 5, 3]) # city names + 1 because city 0 is dummy city

What's different between using a dummy node versus trying every city as the start city?

Nothing really, if you start at a dummy node 0 distance from any other city, the first choice it has will be to choose the first city to go to.

This solution without the for-loop and a zero-padded array will be the same as the solution with the for-loop and the array as is.

#NO LIBRARIES
def shortest_path_padded_no_libs(arr):
    n = len(arr)
    bitmask = [1 << i for i in range(n)]
    target = (1 << n) - 1
    
    def helper(city, visited):
        nonlocal target, n
        
        h = (city, visited)
        if h in memo:
            return memo[h]
        
        if visited == target:
            return 0, [city]
        
        best = float('inf'), []
        for neigh in range(n):
            if not (visited & bitmask[neigh]):
                cost, path = helper(neigh, visited | bitmask[neigh])
                cost += arr[city][neigh]
                path = [city] + path
                if cost < best[0]:
                    best = cost, path
                    
        memo[h] = best
        return best
    
    memo = {}
    
    return helper(0, bitmask[0])


if __name__ == "__main__":
    arr = [
            [0,9,6,1,3],
            [9,0,4,2,1],
            [6,4,0,9,1],
            [1,2,9,0,8],
            [3,1,1,8,0]
          ]
    arr2 = [[0]*(len(arr[0])+1)] + [[0] + row for row in arr]
    print(shortest_path_padded_no_libs(arr2))

Upvotes: 1

Related Questions