Nearest Insertion python 实现 解决tsp
时间: 2024-05-03 17:17:52 浏览: 11
最近插入算法是解决TSP问题的有效算法之一。下面是一个基于Python的最近插入算法实现:
```python
import math
def nearest_insertion(points):
# 计算任意两点之间的距离
distances = [[math.sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2) for x2, y2 in points] for x1, y1 in points]
# 选择起点
start_node = 0
unvisited_nodes = set(range(1, len(points)))
# 选择与起点距离最近的点
current_node = min(unvisited_nodes, key=lambda x: distances[start_node][x])
unvisited_nodes.remove(current_node)
# 将起点和当前节点加入路径
path = [start_node, current_node, start_node]
# 直到所有节点都被访问
while unvisited_nodes:
# 找到距离当前路径最近的未访问节点
current_distance = float('inf')
for i in unvisited_nodes:
for j in range(len(path) - 1):
distance = distances[path[j]][i] + distances[i][path[j+1]] - distances[path[j]][path[j+1]]
if distance < current_distance:
current_distance = distance
node_to_insert = i
insert_position = j+1
# 将节点插入到路径中
path.insert(insert_position, node_to_insert)
unvisited_nodes.remove(node_to_insert)
return path, sum(distances[path[i]][path[i+1]] for i in range(len(points)))
# 示例
points = [(0, 0), (1, 0), (2, 0), (0, 1), (1, 1), (2, 1)]
print(nearest_insertion(points)) # ([0, 1, 4, 3, 5, 2, 0], 5.656854249492381)
```
该算法的时间复杂度为 $O(n^2)$,因此对于较大的TSP问题可能不太适用。