How can we solve "Travelling Salesman Problem" without returning to first point in the end?

Viewed 58

This is Traveling Salesman Problem. I need help because I don't understand how to make us start and end at different points. Below I have given the code for solving the problem in the usual way. Here we start and end at the same point.

def Min(lst,myindex):
    return min(x for idx, x in enumerate(lst) if idx != myindex)

def Delete(matrix,index1,index2):
    del matrix[index1]
    for i in matrix:
        del i[index2]
    return matrix

def PrintMatrix(matrix):
    print("---------------")
    for i in range(len(matrix)):
        print(matrix[i])
    print("---------------")

n=int(input())
matrix=[]
H=0
PathLenght=0
Str=[]
Stb=[]
res=[]
result=[]
StartMatrix=[]

for i in range(n):
    Str.append(i)
    Stb.append(i)

for i in range(n): matrix.append(list(map(int, input().split())))
    
for i in range(n):StartMatrix.append(matrix[i].copy())

float(inf)
for i in range(n): matrix[i][i]=float('inf')

while True:
    for i in range(len(matrix)):
        temp=min(matrix[i])
        H+=temp
        for j in range(len(matrix)):
            matrix[i][j]-=temp
 
    for i in range(len(matrix)):
        temp = min(row[i] for row in matrix)
        H+=temp
        for j in range(len(matrix)):
            matrix[j][i]-=temp
    
    NullMax=0
    index1=0
    index2=0
    tmp=0
    for i in range(len(matrix)):
        for j in range(len(matrix)):
            if matrix[i][j]==0:
                tmp=Min(matrix[i],j)+Min((row[j] for row in matrix),i)
                if tmp>=NullMax:
                    NullMax=tmp
                    index1=i
                    index2=j

    res.append(Str[index1]+1)
    res.append(Stb[index2]+1)
    
    oldIndex1=Str[index1]
    oldIndex2=Stb[index2]
    if oldIndex2 in Str and oldIndex1 in Stb:
        NewIndex1=Str.index(oldIndex2)
        NewIndex2=Stb.index(oldIndex1)
        matrix[NewIndex1][NewIndex2]=float('inf')
    del Str[index1]
    del Stb[index2]
    matrix=Delete(matrix,index1,index2)
    if len(matrix)==1:break
    
for i in range(0,len(res)-1,2):
    if res.count(res[i])<2:
        result.append(res[i])
        result.append(res[i+1])
for i in range(0,len(res)-1,2):
    for j in range(0,len(res)-1,2):
        if result[len(result)-1]==res[j]:
            result.append(res[j])
            result.append(res[j+1])
print("----------------------------------")
print(result)

for i in range(0,len(result)-1,2):
    if i==len(result)-2:
        PathLenght+=StartMatrix[result[i]-1][result[i+1]-1]
        PathLenght+=StartMatrix[result[i+1]-1][result[0]-1]
    else: PathLenght+=StartMatrix[result[i]-1][result[i+1]-1]
print(PathLenght)
print("----------------------------------")
input()

This code works like this:

  1. input 4
  2. input 4x4 matrix like this:
0 10 1 1
10 0 1 5
1 1 0 10
1 5 10 0
  1. result: 1->4 4->2 2->3 3->1 (8)

I done this question like this on JS:

let towns = [
  [0, 28, 58, 13, 24, 25, 31, 64],
  [28, 0, 82, 15, 52, 27, 33, 54],
  [58, 82, 0, 67, 82, 64, 49, 97],
  [13, 15, 67, 0, 37, 12, 18, 69],
  [24, 52, 82, 37, 0, 49, 53, 40],
  [25, 27, 64, 12, 49, 0, 15, 81],
  [31, 33, 49, 18, 53, 15, 0, 70],
  [64, 54, 97, 69, 40, 81, 70, 0],
];

let path = [];
let counter = 0;
let minPath = 10000;
let minCounter;

for (let i1 = 0; i1 <= 7; i1++) {
  for (let i2 = 0; i2 <= 7; i2++) {
    for (let i3 = 0; i3 <= 7; i3++) {
      for (let i4 = 0; i4 <= 7; i4++) {
        for (let i5 = 0; i5 <= 7; i5++) {
          for (let i6 = 0; i6 <= 7; i6++) {
            for (let i7 = 0; i7 <= 7; i7++) {
              for (let i8 = 0; i8 <= 7; i8++) {
                if (
                  i1 != i2 &&
                  i1 != i3 &&
                  i1 != i4 &&
                  i1 != i5 &&
                  i1 != i6 &&
                  i1 != i7 &&
                  i1 != i8 &&
                  i2 != i3 &&
                  i2 != i4 &&
                  i2 != i5 &&
                  i2 != i6 &&
                  i2 != i7 &&
                  i2 != i8 &&
                  i3 != i4 &&
                  i3 != i5 &&
                  i3 != i6 &&
                  i3 != i7 &&
                  i3 != i8 &&
                  i4 != i5 &&
                  i4 != i6 &&
                  i4 != i7 &&
                  i4 != i8 &&
                  i5 != i6 &&
                  i5 != i7 &&
                  i5 != i8 &&
                  i6 != i7 &&
                  i6 != i8 &&
                  i7 != i8
                ) {
                  path[counter] =
                    i1 +
                    1 +
                    " → " +
                    (i2 + 1) +
                    " → " +
                    (i3 + 1) +
                    " → " +
                    (i4 + 1) +
                    " → " +
                    (i5 + 1) +
                    " → " +
                    (i6 + 1) +
                    " → " +
                    (i7 + 1) +
                    " → " +
                    (i8 + 1);
                  console.log(path[counter]);
                  if (
                    towns[i1][i2] +
                      towns[i2][i3] +
                      towns[i3][i4] +
                      towns[i4][i5] +
                      towns[i5][i6] +
                      towns[i6][i7] +
                      towns[i7][i8] <
                    minPath
                  ) {
                    minPath =
                      towns[i1][i2] +
                      towns[i2][i3] +
                      towns[i3][i4] +
                      towns[i4][i5] +
                      towns[i5][i6] +
                      towns[i6][i7] +
                      towns[i7][i8];
                    console.log(minPath);
                    minCounter = counter;
                  }
                  counter += 1;
                }
              }
            }
          }
        }
      }
    }
  }
}

console.log(
  "Shortest Way: " +
    path[minCounter] +
    "(" +
    minPath +
    " KM.)"
);
1 Answers

Add an extra node to be your starting point, with a zero-cost edge to every other node and solve the regular TSP, then throw out the added node.

Related