旅行商问题不回到原点python代码
时间: 2024-06-17 15:07:55 浏览: 12
旅行商问题是一个著名的NP难问题,目的是在给定的一系列城市之间找到最短的路径,使得每个城市只被访问一次,且最后回到起始城市。这个问题很难找到最优解,因为随着城市数量的增加,计算量会指数级增加。通常使用启发式算法来近似解决问题。
以下是一个使用遗传算法求解旅行商问题的Python代码示例:
``` python
import numpy as np
class TravelingSalesmanProblem:
def __init__(self, distances):
self.distances = distances
def fitness(self, permutation):
distance = 0
for i in range(len(permutation)):
distance += self.distances[permutation[i-1], permutation[i]]
return 1/distance
def genetic_algorithm(problem, population_size=50, generations=5000, mutation_rate=0.1):
population = np.random.permutation(len(problem.distances))[:population_size]
for i in range(generations):
fitness_scores = np.array([problem.fitness(p) for p in population])
elite_index = np.argmax(fitness_scores)
elite = population[elite_index]
parents = population[np.random.choice(len(population), size=population_size-1, replace=True)]
children = np.array([mutate(crossover(parents)) for _ in range(population_size-1)])
population = np.concatenate(([elite], children))
return elite
def crossover(parents):
child = [-1] * len(parents)
start = np.random.randint(0, len(parents))
end = np.random.randint(0, len(parents))
if end < start:
start, end = end, start
for i in range(start, end+1):
child[i] = parents[i]
j = 0
for i in range(len(child)):
if child[i] == -1:
while parents[j] in child:
j += 1
child[i] = parents[j]
j += 1
return child
def mutate(child, mutation_rate=0.1):
if np.random.random() < mutation_rate:
i = np.random.randint(0, len(child))
j = np.random.randint(0, len(child))
child[i], child[j] = child[j], child[i]
return child
if __name__ == '__main__':
distances = np.array([[0, 10, 15, 20],
[10, 0, 35, 25],
[15, 35, 0, 30],
[20, 25, 30, 0]])
problem = TravelingSalesmanProblem(distances)
solution = genetic_algorithm(problem)
print("Shortest path found:", solution)
```
该代码使用遗传算法解决了一个由4个城市组成的旅行商问题。这个问题中,每个城市之间的距离由一个4x4的矩阵表示。运行该代码可以得到最短路径及其距离。注意,该代码并未要求回到起始城市。如果需要回到起始城市,可以将遗传算法的结果首尾相接,并加上起始城市到第一个城市的距离和最后一个城市到起始城市的距离。