1

グラフ内の「1000 個のノードを訪問するための最適なルートは何か」の優れたソルバーをセットアップしました。

しかし、「グラフ内の 1000 個のノードのうち 500 個を訪問するための最短ルートは何か」という質問を解決したいと思います。

どうにかして分離制約を pythonに追加する必要があると思いますRoutingModelが、どうやって？

これは、現在のソルバーの大まかなスケッチです。

from ortools.constraint_solver import pywrapcp

nodes = readNodes()      # graph nodes
matrix = readMatrix()    # costs between edges, distances
assert len(nodes) == len(matrix)
# Create routing model
routing = pywrapcp.RoutingModel(len(nodes), 1)
parameters = ...
# Setting the cost function.
distance = lambda p,q: matrix[p][q]
routing.SetArcCostEvaluatorOfAllVehicles(distance)
# --> here is probably more setup needed <--
# Solve, returns a solution if any.
assignment = routing.SolveWithParameters(parameters, None)
if assignment:
  # Solution cost.
  print assignment.ObjectiveValue()
  # Inspect solution
  path = ...
  printSolution(nodes, table, path)
else:
  print 'No solution found.'
4

0 に答える 0