根据tsplib数据集,用N e a r e s t Neighbor算法求解的python实例
时间: 2024-02-21 19:59:26 浏览: 20
以下是使用Nearest Neighbor算法求解tsplib数据集的Python代码示例:
```python
import numpy as np
import math
import matplotlib.pyplot as plt
# 读入数据
def read_input(input_file):
with open(input_file) as f:
lines = f.readlines()[6:-1] # 忽略头部信息和尾部信息
nodes = []
for line in lines:
node_id, x, y = line.strip().split()
nodes.append((int(node_id), float(x), float(y)))
return nodes
# 计算两个节点之间的距离
def distance(node1, node2):
x1, y1 = node1[1], node1[2]
x2, y2 = node2[1], node2[2]
return math.sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2)
# Nearest Neighbor算法
def nearest_neighbor(nodes, start_node):
remaining_nodes = set(nodes)
remaining_nodes.remove(start_node)
current_node = start_node
tour = [start_node]
while remaining_nodes:
nearest_node = min(remaining_nodes, key=lambda x: distance(current_node, x))
remaining_nodes.remove(nearest_node)
tour.append(nearest_node)
current_node = nearest_node
return tour
# 主函数
def main():
input_file = 'dataset.tsp'
nodes = read_input(input_file)
start_node = nodes[0]
tour = nearest_neighbor(nodes, start_node)
tour.append(start_node) # 将起点添加到路径的末尾,形成闭合回路
print('Tour cost:', sum(distance(tour[i], tour[i+1]) for i in range(len(tour)-1)))
# 绘制图形
x = [node[1] for node in tour]
y = [node[2] for node in tour]
plt.plot(x, y, 'o-')
plt.show()
if __name__ == '__main__':
main()
```
其中,`read_input`函数用于读入tsplib数据集,`distance`函数用于计算两个节点之间的距离,`nearest_neighbor`函数是Nearest Neighbor算法的实现,`main`函数调用以上函数并绘制路径图形。请将`dataset.tsp`替换为你要解决的数据集。