Problem komiwojażera (ang. Traveling Salesman Problem, TSP) jest jednym z klasycznych problemów optymalizacyjnych w teorii grafów i badaniach operacyjnych. Polega on na znalezieniu najkrótszej (najtańszej, najszybszej) możliwej trasy, którą porusza się komiwojażer odwiedzając każde z zadanych miast dokładnie jeden raz, po czym powraca do miasta początkowego. Problem ten jest znany ze swojej złożoności obliczeniowej i jest przykładem problemu NP-trudnego.
Opis problemu komiwojażera
Danymi wejściowymi są zbiór miast i odległości między każdą parą miast.
Rozwiązaniem jest najkrótsza możliwą trasa.
Metoda siłowa (Brute Force) - rozwiązanie dokładne
Metoda siłowa polega na przetestowaniu wszystkich możliwych permutacji miast i wybraniu tej, która daje najkrótszą trasę. Choć jest to rozwiązanie najprostsze do zrozumienia, jest ono praktyczne tylko dla bardzo małych zbiorów miast, ponieważ liczba permutacji rośnie wykładniczo. Złożoność czasowa dla tej metody to O(n!).
Implementacja metody w programie Python
import itertools
def calculate_total_distance(permutation, distance_matrix):
total_distance = 0
for i in range(len(permutation) - 1):
total_distance += distance_matrix[permutation[i]][permutation[i + 1]]
total_distance += distance_matrix[permutation[-1]][permutation[0]] # powrót do miasta początkowego
return total_distance
def tsp_brute_force(distance_matrix):
n = len(distance_matrix)
cities = list(range(n))
shortest_distance = float('inf')
best_permutation = None
for permutation in itertools.permutations(cities):
current_distance = calculate_total_distance(permutation, distance_matrix)
if current_distance < shortest_distance:
shortest_distance = current_distance
best_permutation = permutation
return best_permutation, shortest_distance
# Przykład użycia
distance_matrix = [
[0, 10, 15, 20],
[10, 0, 35, 25],
[15, 35, 0, 30],
[20, 25, 30, 0]
]
best_route, best_distance = tsp_brute_force(distance_matrix)
print(f"Najlepsza trasa: {best_route}")
print(f"Najkrótsza odległość: {best_distance}")
Algorytm Helda-Karpa - programowanie dynamiczne
Algorytm Helda-Karpa wykorzystuje programowanie dynamiczne do rozwiązania problemu komiwojażera w czasie O(n22n), co jest znacznie bardziej efektywne niż metoda siłowa dla większych zbiorów miast, ale wciąż niepraktyczne dla bardzo dużych danych wejściowych.
Implementacja algorytmu w programie Python
def tsp_dynamic_programming(distance_matrix):
n = len(distance_matrix)
all_sets = 1 << n
dp = [[float('inf')] * n for _ in range(all_sets)]
dp[1][0] = 0
for mask in range(1, all_sets):
for i in range(n):
if mask & (1 << i):
for j in range(n):
if mask & (1 << j) and i != j:
dp[mask][i] = min(dp[mask][i], dp[mask ^ (1 << i)][j] + distance_matrix[j][i])
final_min_distance = float('inf')
for i in range(1, n):
final_min_distance = min(final_min_distance, dp[all_sets - 1][i] + distance_matrix[i][0])
return final_min_distance
# Przykład użycia
distance_matrix = [
[0, 10, 15, 20],
[10, 0, 35, 25],
[15, 35, 0, 30],
[20, 25, 30, 0]
]
shortest_distance = tsp_dynamic_programming(distance_matrix)
print(f"Najkrótsza odległość: {shortest_distance}")
Dla dużych instancji problemu komiwojażera, rozwiązania dokładne stają się niepraktyczne. W takich przypadkach stosuje się algorytmy przybliżone, które znajdują bliskie optymalnemu rozwiązanie w akceptowalnym czasie.
Rozwiązanie przybliżone algorytm najbliższego sąsiada (Nearest Neighbor)
Algorytm najbliższego sąsiada jest prostą heurystyką, która zaczyna w jednym mieście i zawsze przechodzi do najbliższego nieodwiedzonego miasta. Algorytm nie jest dokładny, ale ma złożoność czasową O(n2).
Implementacja algorytmu w programie Python
def tsp_nearest_neighbor(distance_matrix):
n = len(distance_matrix)
start_city = 0
visited = [False] * n
tour = [start_city]
visited[start_city] = True
current_city = start_city
while len(tour) < n:
next_city = None
shortest_distance = float('inf')
for city in range(n):
if not visited[city] and distance_matrix[current_city][city] < shortest_distance:
next_city = city
shortest_distance = distance_matrix[current_city][city]
tour.append(next_city)
visited[next_city] = True
current_city = next_city
tour.append(start_city) # powrót do miasta początkowego
return tour
# Przykład użycia
distance_matrix = [
[0, 10, 15, 20],
[10, 0, 35, 25],
[15, 35, 0, 30],
[20, 25, 30, 0]
]
tour = tsp_nearest_neighbor(distance_matrix)
print(f"Trasa według najbliższego sąsiada: {tour}")
Inne algorytmy przybliżone
- Algorytm symulowanego wyżarzania (Simulated Annealing)
- Algorytm mrówkowy (Ant Colony Optimization)
- Algorytm genetyczny (Genetic Algorithm)
Złożoność czasowa ww. algorytmów przybliżonych jest trudna do jednoznacznego określenia, ponieważ zależy od wielu czynników, w tym od liczby iteracji, parametrów specyficznych dla danego algorytmu oraz konkretnej implementacji. Niemniej jednak można podać pewne ogólne szacunkowe oszacowania:
- Symulowane wyżarzanie - często O(n3) lub O(n4)
- Algorytm mrówkowy - często O(n3) lub O(n4)
- Algorytm genetyczny - często O(n3)
Każdy z tych algorytmów ma swoje własne zalety i wady i może być stosowany w zależności od specyfiki problemu oraz dostępnych zasobów obliczeniowych.
Komentarze