Линейное программирование для нахождения схемы графа

Question

Сам вопрос довольно прост ... Это проблема маршрутизации автомобилей. У меня есть ориентированный граф

Мне нужно получить модель линейного программирования, которая каким-то образом скажет мне кратчайший контур, который посещает все узлы, и начинается и заканчивается в звезде. Вам разрешено проходить через край более одного раза. Узел - это любое пересечение на изображении. У нас было около 4 часов этого в классе, я понятия не имею, с чего начать ... Я не жду, когда кто-нибудь даст мне полную модель, но я надеялся, что кто-нибудь расскажет стратегию, чтобы я мог это сделать. Заранее спасибо.

Answer 1

Ответ здесь кажется очень простым. (То есть очень легко в теории, очень тяжело и много работы для написания кода на практике).

Это похоже на прямую TSP (Задача коммивояжера). Читайте о некоторой общей литературе по TSP. Вам нужно настроить и решить TSP, где ваши узлы являются «городами» в TSP. Вы также должны включить свою звезду в качестве города в TSP.

Алгоритм Дейкстры не даст вам решение. Алгоритм Дейкстры используется для поиска самых быстрых / самых коротких путей между узлом и другими узлами в (обычно дорожной) сети. Однако с точки зрения расстояния ваша проблема очень проста: получение самой дешевой стоимости проезда (и пути) от одного узла к другому узлу в вашей проблеме (почти) тривиально.

Если вы хотите решить эту проблему «по-настоящему» (а не просто обсудить ее), вам необходимо приобрести решатель TSP, способный принимать вашу сеть (как ребра, так и узлы) в качестве входных данных. Ваш ввод должен указать, какие ребра направлены, а какие однонаправлены. Практическая работа: даже если вы используете инструмент, вам все равно нужно ознакомиться с ним.

Answer 2

Я бы начал с алгоритма Дейкстры для неориентированных графов. Есть несколько вариантов с похожей или лучшей производительностью. Взгляните на https://en.wikipedia.org/wiki/Shortest_path_problem#Undirected_graphs,, выберите выбор и держите нас в курсе ...:)