#точное_решение — Public Fediverse posts

Когда ИИ может в оптимизацию…

Способны ли имеющиеся архитекутры нейронных сетей составить конкуренцию классическим методам оптимизации в решении хорошо изученных задач таких как проблема коммивояжера? Я решил попробовать ответить на этот вопрос и опубликовать свои наработки.

https://habr.com/ru/articles/864924/

#задача_коммивояжера #TSP #MIP #искусственный_интеллект #оптимизация #точное_решение

Планируем путешествие — задача коммивояжера (TSP) для построения оптимального маршрута

С вами Алексей Ложкинс, эксперт по анализу данных и машинному обучению в ПГК Диджитал. Мы разрабатываем цифровые продукты для логистической отрасли, в первую очередь, для ж/д перевозок. В кулуарах московского офиса ПГК мы обсуждаем и нерабочие темы. Топовую строчку в темах неформального общения занимает отпуск. Мы решили рассмотреть задачу планирования отпуска, как задачу оптимизации маршрута по выбранным достопримечательностям. Для этого воспользовались классической постановкой задачи коммивояжера. Моделирование маршрута в виде задачи коммивояжера позволит построить маршрут по всем запланированным локациям без повторений с заданным критерием качества (время, стоимость). Рассмотрим несколько подходов к решению оптимизационной задачи (TSP) с использованием пакета ORTools.

https://habr.com/ru/companies/pgk/articles/778782/

#задача_коммивояжера #ortools #целочисленное_программирование #tsp #линейное_программирование #точное_решение

Коммивояжёр за полином*

Если вам нужно решить задачу коммивояжёра, то нет ничего проще. Нужно просто взять квантовый компьютер с числом кубитов не меньшим числа вершин рассчитываемого графа… Нет под рукой квантового компьютера? Не беда, читайте дальше и узнаете, как можно решать данную задачу на классическом компьютере за полиномиальное время* от числа вершин.

https://habr.com/ru/articles/774754/

#задача_коммивояжера #целочисленное_программирование #tsp #линейное_программирование #точное_решение #opensource