QTSP and TSP Nearest Neighbor Method in Python

QTSP (Quadratic Traveling Salesman Problem) and TSP (Traveling Salesman Problem) are optimization problems used in pathfinding and logistics. To solve them using the Nearest Neighbor Method, you can implement the following Python code to find the shortest path efficiently. Here's a simple Python solution for the TSP using the nearest neighbor approach:

import numpy as np

def nearest_neighbor_tsp(matrix):
    n = len(matrix)
    unvisited = list(range(n))
    tour = [0]  # Start at the first city (index 0)
    unvisited.remove(0)
    while unvisited:
        last = tour[-1]
        next_city = min(unvisited, key=lambda x: matrix[last][x])
        tour.append(next_city)
        unvisited.remove(next_city)
    return tour + [tour[0]]  # Return to start

# Example adjacency matrix
matrix = [
    [0, 29, 20, 21],
    [29, 0, 15, 17],
    [20, 15, 0, 28],
    [21, 17, 28, 0]
]

result = nearest_neighbor_tsp(matrix)
print("Tour:", result)

This code solves the TSP using the nearest neighbor method by starting at the first city and repeatedly visiting the nearest unvisited city until all cities are visited, returning to the starting point.