Решение задачи коммивояжера алгоритмом Литтла

Программирование - Практика программирования

коммивояжер Литтла ветвей и границ

43
Задачи дискретной оптимизации на моей практике встречаются не часто, но решение именно таких задач делает бизнес более эффективным в явном виде (уменьшаются потери материалов и времени и т.д.). В моем случае мы оптимизируем расход краски, упорядочивая очередь производственных заданий оптимальным образом. Поиск оптимального решения привел меня к задаче коммивояжера и его решению посредством частного случая метода Границ и ветвей - алгоритму Литтла. Возможно, кому-то из разработчиков придется решать подобную задачу, и мои наработки пригодятся.

Результатом моей работы явилась обработка  на управляемых формах, запустить которую можно в любой конфигурации. Посредством этой обработки можно демонстрировать результат работы алгоритма Литтла. 

По кнопке "Заполнить начальными данными"в форме случайным образом генерируются точки.

По кнопке "Найти решения"  программа формирует ребра таким образом, чтобы путь, пролегающий через каждую точку, был минимальным.

Для осознания алгоритма использовал следующие источники.

https://habrahabr.ru/post/332208/

https://habrahabr.ru/post/246437/

43

Скачать файлы

Наименование Файл Версия Размер
Решение задачи коммивояжера алгоритмом Литтла
.epf 16,91Kb
12.04.18
18
.epf 16,91Kb 18 Скачать

См. также

Специальные предложения

Комментарии
Избранное Подписка Сортировка: Древо
2. Rustig 1031 16.04.18 08:32 Сейчас в теме
(0) добрый день. а как задача коммивояжера связана с задачей оптимального расхода краски?
4. van_za 95 16.04.18 15:19 Сейчас в теме
Добрый день!
В качестве расстояния между двумя макетами (заданиями) выступает количество печатных секций которое нужно переналадитить,, это очень влияет на затраты краски.
6. protexprotex 156 16.04.18 15:52 Сейчас в теме
(4) Можно поподробней описать задачу?
7. Rustig 1031 16.04.18 17:33 Сейчас в теме
(4) откуда программа знает количество печатных секций между заданиями, которое нужно переналадить?
8. Rustig 1031 16.04.18 17:34 Сейчас в теме
(4) как составляется матрица вариантов? программой или оператором?
10. van_za 95 17.04.18 09:50 Сейчас в теме
(8)
В системе есть специальная сущность описывающая рецептуру печати, у нас называется макет, ниже картинка.
является значением свойства характеристики номенклатуры.
матрица формируется запросом по заданиям которые ждут исполнения.
Прикрепленные файлы:
14. Rustig 1031 17.04.18 14:01 Сейчас в теме
(10) по картинке значится, что аппарат имеет 8 картриджей (8 секций).
А как узнать сколько надо изменить секций для следующего задания? вот главный вопрос
15. van_za 95 17.04.18 15:23 Сейчас в теме
(14)
запросом, каждый с каждым (макет)
если в секции цвет не совпадает и в начальном макете секция не пустая тогда 1 по секции
3. protexprotex 156 16.04.18 08:39 Сейчас в теме
(0) Добрый день. А не проверяли - метод имитации отжига (генетический алгоритм) не будет более оптимален по скорости? - это не прицепка - просто интересно. Метод имитации отжига, в принципе, по идее очень похож по движению по плоскости оптимизации на алгоритм Литтла.
5. van_za 95 16.04.18 15:21 Сейчас в теме
(3)
проверяли - метод имитации от

Добрый день!
буду тестировать.
9. zaoproxy 35 17.04.18 07:29 Сейчас в теме
Скачал, посмотрел. Фигня какая-то получается в решении:
на каждом шаге должны быть начальная и конечная точки, а встречаются варианты у которых нет или одного или другого(
и ещё вопрос: зачем замыкаете периметр? в задаче коммивояжера нет условия вернуться в начальную точку
11. van_za 95 17.04.18 09:55 Сейчас в теме
(9)
Пустое значение соответствует значению 0
Прикрепленные файлы:
13. zaoproxy 35 17.04.18 13:31 Сейчас в теме
(11) про пустое значение согласен, но по таблице есть вопросы:
в скриншоте из вашего ответа начальные и конечные точки перепутаны. Обратите внимание на выделенную вами строку таблицы. Объясните как после третьего шага мы смогли оказаться в точке 13 или 5 если ни одна из них не соседствует ни с 6й не с 11й?
с сами по точкам из примера попробуйте встать в первую точку и визуально пройти весь путь
16. van_za 95 17.04.18 17:22 Сейчас в теме
(13)
задача алгоритма построить замкнуты контур минимальной длины.
не имеет значение начальная и конечная точка в конкретном ребре, главное что все ребра найдены, задача именно в этом.
если я ошибаюсь поправьте меня с ссылкой на источник.
12. van_za 95 17.04.18 09:57 Сейчас в теме
(9)

ссылка в википедии
https://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BA%D0%BE%D­0%BC%D0%BC%D0%B8%D0%B2%D0%BE%D1%8F%D0%B6%D1%91%D1%80%D0%B0

Задача коммивояжёра (англ. Travelling salesman problem, сокращённо TSP) — одна из самых известных задач комбинаторной оптимизации, заключающаяся в поиске самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу с последующим возвратом в исходный город.
jONES1979; +1 Ответить
Оставьте свое сообщение