#проблема_коммивояжера — Public Fediverse posts

[Перевод] Исследователи приблизились к новому пределу скорости решения задачи коммивояжера

Целочисленное линейное программирование может помочь найти ответ на множество реальных проблем. Теперь исследователи нашли гораздо более быстрый способ это сделать. Задача коммивояжера — одна из старейших известных вычислительных задач. Она заключается в поиске кратчайшего маршрута через определённый список городов. Несмотря на кажущуюся простоту, проблема, как известно, сложна. И хотя вы можете использовать перебор, чтобы проверить все возможные маршруты, пока не найдете кратчайший путь, такая стратегия становится несостоятельной, уже когда в списке всего лишь несколько городов.

https://habr.com/ru/companies/first/articles/805233/

#проблема_коммивояжера #алгоритмы #вычислительная_сложность #линейная_алгебра #ILP