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

12.04.18

Разработка - Математика и алгоритмы

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

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

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

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

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

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

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

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

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

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

См. также

Метод Дугласа-Пойкера для эффективного хранения метрик

Математика и алгоритмы Платформа 1C v8.2 Конфигурации 1cv8 Россия Абонемент ($m)

На написание данной работы меня вдохновила работа @glassman «Переход на ClickHouse для анализа метрик». Автор анализирует большой объем данных, много миллионов строк, и убедительно доказывает, что ClickHouse справляется лучше PostgreSQL. Я же покажу как можно сократить объем данных в 49.9 раз при этом: 1. Сохранить значения локальных экстремумов 2. Отклонения от реальных значений имеют наперед заданную допустимую погрешность.

1 стартмани

30.01.2024    1754    stopa85    12    

33

Алгоритм симплекс-метода для решения задачи раскроя

Математика и алгоритмы Бесплатно (free)

Разработка алгоритма, построенного на модели симплекс-метода, для нахождения оптимального раскроя.

19.10.2023    4417    user1959478    50    

34

Регулярные выражения на 1С

Математика и алгоритмы Инструментарий разработчика Платформа 1С v8.3 Мобильная платформа Россия Абонемент ($m)

Что ж... лучше поздно, чем никогда. Подсистема 1С для работы с регулярными выражениями: разбор выражения, проверка на соответствие шаблону, поиск вхождений в тексте.

1 стартмани

09.06.2023    7462    4    SpaceOfMyHead    17    

56

Модель распределения суммы по базе

Математика и алгоритмы Платформа 1С v8.3 Россия Абонемент ($m)

Обычно под распределением понимают определение сумм пропорционально коэффициентам. Предлагаю включить сюда также распределение по порядку (FIFO, LIFO) и повысить уровень размерности до 2-х. 1-ое означает, что распределение может быть не только пропорциональным, но и по порядку, а 2-ое - это вариант реализации матричного распределения: по строкам и столбцам. Возможно вас заинтересует также необычное решение этой задачи через создание DSL на базе реализации текучего интерфейса

1 стартмани

21.03.2022    7855    7    kalyaka    11    

44

Изменения формата файлов конфигурации (CF) в 8.3.16

Математика и алгоритмы Платформа 1С v8.3 Бесплатно (free)

Дополнение по формату файлов конфигурации (*.cf) в версии 8.3.16.

16.12.2021    4445    fishca    13    

36

Интересная задача на Yandex cup 2021

Математика и алгоритмы Бесплатно (free)

Мое решение задачи на Yandex cup 2021 (frontend). Лабиринт. JavaScript.

12.10.2021    8838    John_d    73    

46

Механизм анализа данных. Кластеризация.

Математика и алгоритмы Анализ учета Платформа 1С v8.3 Анализ и прогнозирование Бесплатно (free)

Подробный разбор, с примером использования, встроенного механизма кластеризации 1С.

31.08.2021    7804    dusha0020    8    

70
Комментарии
В избранное Подписаться на ответы Сортировка: Древо развёрнутое
Свернуть все
1. пользователь 15.04.18 05:20
Сообщение было скрыто модератором.
...
2. RustIG 1351 16.04.18 08:32 Сейчас в теме
(0) добрый день. а как задача коммивояжера связана с задачей оптимального расхода краски?
4. van_za 243 16.04.18 15:19 Сейчас в теме
Добрый день!
В качестве расстояния между двумя макетами (заданиями) выступает количество печатных секций которое нужно переналадитить,, это очень влияет на затраты краски.
wowik; unduty; RustIG; +3 Ответить
6. protexprotex 113 16.04.18 15:52 Сейчас в теме
(4) Можно поподробней описать задачу?
7. RustIG 1351 16.04.18 17:33 Сейчас в теме
(4) откуда программа знает количество печатных секций между заданиями, которое нужно переналадить?
8. RustIG 1351 16.04.18 17:34 Сейчас в теме
(4) как составляется матрица вариантов? программой или оператором?
10. van_za 243 17.04.18 09:50 Сейчас в теме
(8)
В системе есть специальная сущность описывающая рецептуру печати, у нас называется макет, ниже картинка.
является значением свойства характеристики номенклатуры.
матрица формируется запросом по заданиям которые ждут исполнения.
Прикрепленные файлы:
14. RustIG 1351 17.04.18 14:01 Сейчас в теме
(10) по картинке значится, что аппарат имеет 8 картриджей (8 секций).
А как узнать сколько надо изменить секций для следующего задания? вот главный вопрос
15. van_za 243 17.04.18 15:23 Сейчас в теме
(14)
запросом, каждый с каждым (макет)
если в секции цвет не совпадает и в начальном макете секция не пустая тогда 1 по секции
wowik; RustIG; +2 Ответить
3. protexprotex 113 16.04.18 08:39 Сейчас в теме
(0) Добрый день. А не проверяли - метод имитации отжига (генетический алгоритм) не будет более оптимален по скорости? - это не прицепка - просто интересно. Метод имитации отжига, в принципе, по идее очень похож по движению по плоскости оптимизации на алгоритм Литтла.
5. van_za 243 16.04.18 15:21 Сейчас в теме
(3)
проверяли - метод имитации от

Добрый день!
буду тестировать.
9. zaoproxy 36 17.04.18 07:29 Сейчас в теме
Скачал, посмотрел. Фигня какая-то получается в решении:
на каждом шаге должны быть начальная и конечная точки, а встречаются варианты у которых нет или одного или другого(
и ещё вопрос: зачем замыкаете периметр? в задаче коммивояжера нет условия вернуться в начальную точку
11. van_za 243 17.04.18 09:55 Сейчас в теме
(9)
Пустое значение соответствует значению 0
Прикрепленные файлы:
13. zaoproxy 36 17.04.18 13:31 Сейчас в теме
(11) про пустое значение согласен, но по таблице есть вопросы:
в скриншоте из вашего ответа начальные и конечные точки перепутаны. Обратите внимание на выделенную вами строку таблицы. Объясните как после третьего шага мы смогли оказаться в точке 13 или 5 если ни одна из них не соседствует ни с 6й не с 11й?
с сами по точкам из примера попробуйте встать в первую точку и визуально пройти весь путь
16. van_za 243 17.04.18 17:22 Сейчас в теме
(13)
задача алгоритма построить замкнуты контур минимальной длины.
не имеет значение начальная и конечная точка в конкретном ребре, главное что все ребра найдены, задача именно в этом.
если я ошибаюсь поправьте меня с ссылкой на источник.
12. van_za 243 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 Ответить
17. Yuri1C 3 24.04.19 13:15 Сейчас в теме
Задача коммивояжера решена в классическом варианте, в замкнутом цикле?
Точка начала = Точка окончания?
18. ValeriVP 1303 19.02.20 16:45 Сейчас в теме
Как изменить алгоритм, чтобы добавить условие:
Нельзя ехать в город Б, не заехав в город А
?
20. SuperJur 2 16.04.20 00:05 Сейчас в теме
(18) логика подсказывает, что необходимо оставить только расстояние из А в Б, а остальные установить =-1.
19. SuperJur 2 15.04.20 23:55 Сейчас в теме
Добрый день!
Что-то для 21 точки программа виснет.
21. van_za 243 16.04.20 19:36 Сейчас в теме
Здравствуйте!
в худшем случае сложность алгоритма соответствует полному перебору
20! = 2 432 902 008 176 640 000
Оставьте свое сообщение