[Из песочницы] Решение задачи коммивояжера алгоритмом Литтла с визуализацией на плоскости

Известная как минимум с 19 века задача коммивояжера имеет множество способов решения и неоднократно описана. Ее оптимизационная версия является NP-трудной, поэтому оптимальное решение можно получить либо полным перебором, либо оптимизированным полным перебором — методом ветвей и границ.

Пытаясь запрограммировать алгоритм Литтла (частный случай метода ветвей и границ), я понял, что в рунете крайне трудно найти его правильное описание понятным языком и разобранную программную реализацию. Однако имеющиеся в изобилии описания обманчиво правдоподобны на данных малого размера и с трудом проверяются без визуализации.

animation

Читать дальше →
[Из песочницы] Решение задачи коммивояжера алгоритмом Литтла с визуализацией на плоскости
Source: habrahabr

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *