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

12.04.18

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

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

Скачать файл

ВНИМАНИЕ: Файлы из Базы знаний - это исходный код разработки. Это примеры решения задач, шаблоны, заготовки, "строительные материалы" для учетной системы. Файлы ориентированы на специалистов 1С, которые могут разобраться в коде и оптимизировать программу для запуска в базе данных. Гарантии работоспособности нет. Возврата нет. Технической поддержки нет.

Наименование По подписке [?] Купить один файл
Решение задачи коммивояжера алгоритмом Литтла
.epf 16,91Kb
43
43 Скачать (1 SM) Купить за 1 850 руб.

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

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

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

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

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

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

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

+52 –

См. также

Метод Дугласа-Пойкера

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

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

1 стартмани

30.01.2024    4999    stopa85    12    

39
Алгоритм симплекс-метода

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

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

19.10.2023    10017    user1959478    54    

37
Математический тренажер созданный для тестирования Вашего ребенка на предмет: умножения, деления, сложения и вычитания.

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

Расширение (+ обработка) представляют собою математический тренажер. Ваш ребенок сможет проверить свои знание на математические вычисление до 100.

2 стартмани

29.09.2023    4841    maksa2005    8    

26
Регулярки на 1С

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

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

1 стартмани

09.06.2023    12567    8    SpaceOfMyHead    20    

62
Мини-обзор разных решений задач

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

Три задачи - три идеи - три решения. Мало кода, много смысла. Мини-статья.

03.04.2023    6094    RustIG    9    

25
Тестирование средств 1С для решения СЛАУ

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

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

23.11.2022    5208    gzharkoj    14    

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

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

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

1 стартмани

21.03.2022    9418    7    kalyaka    11    

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

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

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

16.12.2021    7372    fishca    12    

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

Добрый день!
буду тестировать.
+ – Ответить
9. zaoproxy 37 17.04.18 07:29 Сейчас в теме
Скачал, посмотрел. Фигня какая-то получается в решении:
на каждом шаге должны быть начальная и конечная точки, а встречаются варианты у которых нет или одного или другого(
и ещё вопрос: зачем замыкаете периметр? в задаче коммивояжера нет условия вернуться в начальную точку
+ – Ответить
11. van_za 270 17.04.18 09:55 Сейчас в теме
(9)
Пустое значение соответствует значению 0
Прикрепленные файлы:
+ – Ответить
13. zaoproxy 37 17.04.18 13:31 Сейчас в теме
(11) про пустое значение согласен, но по таблице есть вопросы:
в скриншоте из вашего ответа начальные и конечные точки перепутаны. Обратите внимание на выделенную вами строку таблицы. Объясните как после третьего шага мы смогли оказаться в точке 13 или 5 если ни одна из них не соседствует ни с 6й не с 11й?
с сами по точкам из примера попробуйте встать в первую точку и визуально пройти весь путь
+ – Ответить
16. van_za 270 17.04.18 17:22 Сейчас в теме
(13)
задача алгоритма построить замкнуты контур минимальной длины.
не имеет значение начальная и конечная точка в конкретном ребре, главное что все ребра найдены, задача именно в этом.
если я ошибаюсь поправьте меня с ссылкой на источник.
+ – Ответить
12. van_za 270 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 Сейчас в теме
Задача коммивояжера решена в классическом варианте, в замкнутом цикле?
Точка начала = Точка окончания?
acanta; +1 – Ответить
18. ValeriVP 1342 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 270 16.04.20 19:36 Сейчас в теме
Здравствуйте!
в худшем случае сложность алгоритма соответствует полному перебору
20! = 2 432 902 008 176 640 000
+ – Ответить
Оставьте свое сообщение