Рубрика «Литтл»

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

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

animation

Читать полностью »

Обучаясь в университете, каждому приходилось делать разного рода задачи. Вот, наступает конец полугодия, сессия на носу, начало выдачи курсовых заданий и мне посчастливилось стать тем, кто должен реализовать метод Литтла для задачи коммивояжера. Итак начнем.

Кто такой коммивояжер? Коммивояжер — это разъездной торговый агент какой-либо фирмы, предлагающий покупателям товары по образцам и каталогам. Его задача объездить все пункты назначения, не побывав ни в одном дважды и вернуться в точку старта.

image

Читать полностью »


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js