Все пути одинаковы: они ведут в никуда. Но у одних есть сердце, а у других — нет. Один путь дает тебе силы, другой — уничтожает тебя.
- Карлос Кастанеда
Рубрика «задача коммивояжёра»
Задача коммивояжера (TSP) точное решение — метод целочисленного линейного программирования (Integer programming)
2023-01-21 в 7:23, admin, рубрики: python, TSP, алгоритм, Алгоритмы, высокая производительность, задача коммивояжёра, Линейное программирование, Совершенный код, точное решение, целочисленное программированиеНейросеть с амёбой решили задачу коммивояжера для 8 городов
2018-12-24 в 19:10, admin, рубрики: Алгоритмы, амёба, биокомпьютер, Биотехнологии, задача коммивояжёра, математика, машинное обучение, Научно-популярное
Решения задачи коммивояжера, полученные вычислительной системой на основе амёбы. Примеры туров коммивояжёра по четырём, пяти, шести, семи и восьми городам, полученные в экспериментах, где каждый тур окрашен в красный цвет на соответствующих каналах с правого рисунка. Левые панели показывают переданные светлые изображения начальных состояний (
Группа японских исследователей из Университета Кейо в Токио продемонстрировала, что амёбы способна генерировать приближённые решения удивительно сложной математической задачи, известной как задача коммивояжера.
Читать полностью »
Решение задачи коммивояжёра методом ближайшего соседа на Python
2017-05-27 в 14:52, admin, рубрики: python, задача коммивояжёра, метод ближайшего соседаБыстрый и простой алгоритм требующий модификации
Среди методов решения задачи коммивояжёра метод ближайшего соседа привлекает простотой алгоритма. Метод ближайшего соседа в исходной формулировке заключается в нахождении замкнутой кривой минимальной длины, соединяющей заданный набор точек на плоскости [1]. Моё внимание привлекла наиболее распространённая реализация данного алгоритма в пакете Mathcad, размещённая в сети на ресурсе [2]. Сама реализация не совсем удобна, например, нельзя вывести матрицу расстояний между пунктами или проанализировать альтернативные маршруты.
На ресурсе [2] приведена следующая вполне справедливая критика данного метода. «Маршрут не оптимальный (не самый короткий) и сильно зависит от выбора первого города. Фактически не решена задача коммивояжера, а найдена одна гамильтонова цепь графа». Там же предложен путь некоторого усовершенствования метода ближайшего соседа. «Следующий возможный шаг оптимизации — «развязывание петель» (ликвидация перекрестий). Другое решение — перебор всех городов (вершин графа) в качестве начала маршрута и выбор наикратчайшего из всех маршрутов». Однако реализация последнего предложения не приведена. Учитывая все перечисленные обстоятельства, я решил реализовать приведенный алгоритм на Python и при этом предусмотреть возможность выбора начального пункта по критерию минимальной длины марщрута.
Читать полностью »
Специалисты по информатике идут нехожеными дорогами
2016-12-06 в 13:27, admin, рубрики: p=np, Алгоритмы, задача коммивояжёра, кристофидес, математика, Научно-популярное, метки: кристофидесСпустя десятилетия застоя, найдены новые короткие пути для задачи коммивояжёра
Не так давно команда исследователей из Стэнфорда и Университета Макгилла побили 35-летний рекорд по информатике на невообразимо малую величину – на четыре сотых триллионной триллионной триллионной доли процента. Прорыв – сделанный в классической для информатики задаче коммивояжёра – был слишком малым для какого бы то ни было практического значения, но он вдохнул новую жизнь в поиски улучшенных приближённых решений.
Задача формируется так: для набора городов, соединённых дорогами, необходимо найти кратчайший путь посещения каждого города с возвратом в точку старта. У решений задачи есть практические применения от сверления отверстий в печатных платах до управления расписанием задач на компьютере и упорядочивания свойств генома.
Читать полностью »
Муравьиный алгоритм MMAS
2015-04-06 в 8:03, admin, рубрики: Алгоритмы, высокая производительность, задача коммивояжёра, Занимательные задачки, муравьи, муравьиный алгоритм, оптимизация, поиск пути Приветствую всех читателей. Сегодня попробую продолжить серию достаточно редких статей, посвящённым естественным алгоритмам. В частности, эта статья будет посвящена модификации муравьиного алгоритма, известной как Max-Min Ant System (MMAS). Я расскажу об отличиях от классического муравьиного алгоритма и о причинах внесения таких модификаций. Подробности под катом.
Читать полностью »
Поиск гамильтонова цикла в большом графе (задача коммивояжера). Часть 3
2014-07-12 в 10:40, admin, рубрики: Алгоритмы, задача коммивояжёра, ПрограммированиеВсем доброго времени суток!
В этом небольшом посте я продолжу тему, которую поднимал в своих старых двух постах
Часть 1
Часть 2
А именно, расскажу о небольшой идее, которая недавно пришла мне в голову, и которая помогает решить поставленную задачу немного лучше.
Так что добро пожаловать под хабракат
Читать полностью »
Как я изобретал метод имитации отжига
2014-02-01 в 12:14, admin, рубрики: Алгоритмы, для начинающих, задача коммивояжёра, математика, оптимизация, метки: для начинающих, задача коммивояжëра, оптимизация
Доброго времени!
Сподвигло меня на написание этой работы прочтение «Введение в оптимизацию. Имитация отжига». Так уж сложилось, что как раз недавно я столкнулся с задачей коммивояжера и для ее решения придумал алгоритм, суть которого, как оказалось, очень близка к идее алгоритма имитации отжига, описываемого в указанной статье. Более того, там даже есть «отсылка» к моей идее, а еще похожие обсуждения велись в комментариях, потому я решил, что сообществу будет интересно посмотреть на реализацию.
Читать полностью »
У нас было 540 точек, 120 мерчендайзеров, 30 ТП, 2 супервайзера, 5 таблиц в XLS и один пакет на ПО маршрутизации
2014-01-23 в 7:18, admin, рубрики: Блог компании КРОК, Геоинформационные сервисы, задача коммивояжёра, маршрутизация, оптимизация, управление проектами, метки: задача коммивояжëра, маршрутизация, оптимизация
Пример XLS-таблицы, которая используется до внедрения системы – и отлично подходит в качестве источника первичных данных.
Есть такой классный тип математических задач — маршрутизация торговых представителей. Хорошо известный каждому, изучавшему дискретную математику.
На практике дело в том, что ваши любимые шоколадки в супермаркетах, ларьках и кафе появляются не просто так. Сначала выявляются требования потребителей, возможности производителей, а также пожелания конкретной точки и поставщиков в представлении определенной позиции на рынке.. На основании этих выявленных параметров появляется пул задач для обслуживания каждой точки торговым представителем. Он привозит на точку товар для демонстрации, договаривается о расширении ассортимента продаж, оказывает сервис продаж, плюс контролирует документооборот и осуществляет расчеты. А мерчендайзер от раза до нескольких раз в неделю наведывается по месту продаж, чтобы поправить выкладку и убедиться, что всё в порядке.
Фактически, задача сводится к двум:
- Обобщенной задаче коммивояжера (TSP).
- И построению оптимального расписания-плана.
При этом в задачах также учитываются доступные ресурсы (например, наличие машин, их вместимость, проходимость дорог и так далее), параметры точек (время ее работы точки, частота посещения, перечень задач, которые требуется решать в данной точке и так далее), изменения, например, внезапный переезд одного ларька на другой конец города. Ну и финальный штрих — довольно часто эта задача решается супервайзером с высшим гуманитарным образованием. Читать полностью »
Решение задачи коммивояжёра на плоскости рекурсивным жадным алгоритмом
2012-09-21 в 16:26, admin, рубрики: Алгоритмы, задача коммивояжёра, ненормальное программирование, Программирование, рекурсия, метки: задача коммивояжёра, рекурсия В предыдущей публикации был рассмотрен алгоритм решения задачи коммивояжёра на плоскости рекурсивным полным перебором. Результат получился любопытным, но итоговый маршрут содержал очевидные неоптимальные участки. В предлагаемой заметке рассмотрен улучшенный алгоритм, который я назвал «рекурсивным жадным алгоритмом». Признаюсь сразу, итоговый маршрут в сравнении с рекурсивным полным перебором получается лучше, в среднем, на 8%.
Читать полностью »
Решение задачи коммивояжёра рекурсивным полным перебором
2012-09-10 в 9:13, admin, рубрики: задача коммивояжёра, Песочница, полный перебор, рекурсия, метки: задача коммивояжёра, полный перебор, рекурсия Сформулируем задачу.
Дано N узлов, расположенных на плоскости. Задан входной узел (Вх) и выходной узел (Вых). Необходимо обнаружить кратчайший путь, охватывающий все узлы, начинающийся во входном узле, заканчивающийся в выходном узле и проходящий через каждый узел только один раз.
Есть мнения, что задача коммивояжёра может формулироваться ещё двумя способами:
1. Необходимо обнаружить кратчайший гамильтонов цикл.
2. Необходимо обнаружить кратчайший путь, начинающийся в заданном узле.
Однако обе эти формулировки при ближайшем рассмотрении оказываются частными случаями первоначальной формулировки.
Формулировка 1 подразумевает, что входным узлом может быть любой узел, а выходным — один из ближайших к нему. Что требует полного перебора всех ближайших узлов к произвольно выбранному узлу.
Формулировка 2 подразумевает, что входной узел задан, а выходным узлом может быть любой. Что требует полного перебора всех выходных узлов с последующим выбором кратчайшего пути из всех кратчайших.
Поэтому мы остановимся на первоначальной формулировке, и будем решать задачу в общем виде.
Читать полностью »