0. van_za 97 12.04.18 12:32 Сейчас в теме

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

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

Перейти к публикации

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

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

Вакансии

Программист 1С
Нижний Новгород
зарплата до 120 000 руб.
Полный день

Программист 1С
Волгоград
зарплата от 45 000 руб. до 90 000 руб.
Полный день

Автор новостных обзоров на тему 1С и бухучета
Санкт-Петербург
По совместительству

Консультант-аналитик 1С
Москва
зарплата от 70 000 руб. до 100 000 руб.
Полный день

Программист 1С
Москва
зарплата от 80 000 руб. до 120 000 руб.
Временный (на проект)