u/Humble_Homework_3894

Start from any city and go to the next city with the shortest distance, from there go to the next city with the shortest distance, repeat; until a loop is formed intersecting all cities—this is the base loop.

​Now, starting again from the initial city, go to the next city using the second shortest distance [if, before traversing a distance, you realize it will make the path longer than the base loop, then go to the next city using the next shortest distance; if you run out of paths, go back to the previous city and repeat; and if it is shorter, treat it as the new base loop and proceed], from there go to the next city using the second shortest distance, repeat; until another loop is formed intersecting all cities.

​Repeat this process until you find the shortest base loop, and then output that as the result.

------------------------------------------------------------------------------------------

Code:

import sys

def solve_tsp_custom_logic(distance_matrix):

n = len(distance_matrix)

if n <= 1:

return 0, [0]

# Step 1: Start from any city and go to the next city with the shortest distance...

# This forms the "base loop"

visited_init = set([0])

curr = 0

base_loop_cost = 0

base_loop_path = [0]

for _ in range(n - 1):

# Find the next unvisited city with the shortest distance

next_city = min([(distance_matrix[curr][j], j) for j in range(n) if j not in visited_init])[1]

base_loop_cost += distance_matrix[curr][next_city]

visited_init.add(next_city)

base_loop_path.append(next_city)

curr = next_city

# Complete the loop back to the initial city

base_loop_cost += distance_matrix[curr][0]

base_loop_path.append(0)

best_cost = base_loop_cost

best_path = base_loop_path

# Step 2 & 3: Now, starting again from the initial city... explore other paths

def explore_paths(curr_city, visited_count, current_cost, path):

nonlocal best_cost, best_path

# PRUNING: if you realize it will make the path longer than the base loop, go back and repeat

if current_cost >= best_cost:

return

# If a complete loop is formed

if visited_count == n:

total_cost = current_cost + distance_matrix[curr_city][0]

# ...and if it is shorter, treat it as the new base loop

if total_cost < best_cost:

best_cost = total_cost

best_path = path + [0]

return

# Go to the next city using the next shortest available distances

# (Sorting unvisited cities by distance to check the shortest ones first)

unvisited_cities = [c for c in range(n) if c not in path]

unvisited_cities.sort(key=lambda c: distance_matrix[curr_city][c])

for next_city in unvisited_cities:

explore_paths(

next_city, 

visited_count + 1, 

current_cost + distance_matrix[curr_city][next_city], 

path + [next_city]

)

# Start the deep exploration from city 0

explore_paths(0, 1, 0, [0])

return best_cost, best_path

# ==========================================

# User Testing Section (No Hardcoded Data)

# ==========================================

if __name__ == "__main__":

print("=== Custom TSP Logic Tester ===")

try:

num_cities = int(input("Enter the number of cities: ").strip())

print(f"\nEnter the distance matrix ({num_cities}x{num_cities}), row by row.")

print("Use space-separated numbers (e.g., 0 10 15 20):")

matrix = []

for i in range(num_cities):

row = list(map(int, input(f"Row {i+1}: ").strip().split()))

if len(row) != num_cities:

print("Error: Number of columns does not match the number of cities.")

sys.exit()

matrix.append(row)

print("\nCalculating using the custom logic...")

cost, path = solve_tsp_custom_logic(matrix)

print("\n--- Result ---")

print(f"Shortest Loop Cost: {cost}")

print(f"Path taken: {' -> '.join(map(str, path))}")

except ValueError:

print("Invalid input! Please enter numbers only.")

reddit.com
u/Humble_Homework_3894 — 19 days ago