Я настроил прекрасный решатель для «какого маршрута лучше всего посетить 1000 узлов» на моем графике.
Но я хотел бы решить вопрос «каким кратчайшим путем можно посетить любые 500 из 1000 заданных узлов в моем графе».
Думаю, мне нужно добавить дизъюнктивные ограничения как-то на мой питон 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.'
