0

首先，错误：

Traceback (most recent call last):
  File "tsp_solver.py", line 57, in <module>
    solvetTSP(inputData)
NameError: name 'solvetTSP' is not defined
new-host:tsp Jonathan$ python tsp_solver.py data/tsp_51_1
Traceback (most recent call last):
  File "tsp_solver.py", line 57, in <module>
    solveTSP(inputData)
  File "tsp_solver.py", line 36, in solveTSP
    r = p.solve('sa')
  File "/opt/local/Library/Frameworks/Python.framework/Versions/2.7/lib/python2.7/site-    packages/openopt-0.506-py2.7.egg/openopt/kernel/TSP.py", line 150, in solve
    EdgesCoords.append((node, Out_nodes[i]))
IndexError: index 1 is out of bounds for axis 0 with size 1

我真的不知道为什么我会收到这个错误。我在这里有一个非常基本的 OpenOpt TSP 求解器实例，但它完全不起作用。我将networkx用于图表，并且只使用权重=距离逐条添加边。当我将 TSP 实例传递给求解器时会发生错误，但我显然不知道为什么。这是我的代码，任何帮助将不胜感激。

from openopt import *
import networkx as nx
import math

def length(point1, point2):
    return math.sqrt((point1[0] - point2[0])**2 + (point1[1] - point2[1])**2)

def solveTSP(inputData):
    inputData = inputData.split('\n')
    inputData.pop(len(inputData) - 1)

    N = int(inputData.pop(0))
    points = []


    for i in inputData:
        point = i.split(" ")
        point = [float(x) for x in point]
        point = tuple(point)
        points.append(point)


    G = nx.Graph()
    prev_point = None

    for cur_point in points:
        assert(len(cur_point) == 2)
        if prev_point != None:
            a = length(cur_point, prev_point)
            G.add_edge(cur_point, prev_point, weight = a)
        else:
            G.add_node(cur_point)
        prev_point = cur_point

    p = TSP(G, objective = 'weight', start = 0)
    r = p.solve('sa')
    r.nodes.pop(len(r.nodes)-1)

    distance = r.ff
    path = r.nodes

    print distance
    print path

import sys

if __name__ == '__main__':
    if len(sys.argv) > 1:
        fileLocation = sys.argv[1].strip()
        inputDataFile = open(fileLocation, 'r')
        inputData = ''.join(inputDataFile.readlines())
        inputDataFile.close()
        solveTSP(inputData)
4

1 回答 1

0

您有带有 n 个节点和 n-1 条边的图，而对于 TSP 图必须至少有 n 条边。我提出的解决方案从最后一点到起点有额外的优势：

points = ((1, 2), (3, 4), (5, 6), (9, 10))
G = nx.Graph()
prev_point = None

for i, cur_point in enumerate(points):
    assert(len(cur_point) == 2)
    if i != 0:
        a = length(cur_point, prev_point)
        G.add_edge(i, i-1, weight = a)
    prev_point = cur_point
G.add_edge(0, len(points)-1, weight = length(points[0], points[-1]))

p = TSP(G, objective = 'weight', start = 0)
r = p.solve('sa')
r.nodes.pop(len(r.nodes)-1)

distance = r.ff
path = r.nodes

print distance # 22.627416998
print path # [0, 3, 2, 1]
于 2013-08-08T05:44:19.697 回答