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 に答える