
Где начинается ИИ в задаче коммивояжера?
Заголовок отсылает к знаменитой работе Attention Is All You NeedЧитать полностью »
Заголовок отсылает к знаменитой работе Attention Is All You NeedЧитать полностью »
Всем привет!
Меня зовут Дмитрий и по месту своей последней работы я дата консультант и владелец продукта, но сейчас мне больше подходит роль энтузиаста-исследователя.
Выбор наилучшего элемента из нескольких существующих альтернатив называется задачей оптимизации. Во большинстве таких задачах исчерпывающий поиск нецелесообразен. Это имеет важные приложения в нескольких областях, включая искусственный интеллект, машинное обучение, математику и программную инженерию. Большинство таких задач считаются NP-трудными, то есть их нельзя решить оптимально за полиномиальное время вычислений. Некоторые общие задачи, связанные с оптимизацией, включают задачу коммивояжера, задачу о минимальном остовном дереве и другие.
К величию есть только один путь, и этот путь проходит через страдания.
- Альберт Эйнштейн
Эта работа является заключением пятилетнего марафона по поиску самого быстрого способа нахождения минимального точного решения для задачи коммивояжёра в общем виде.
Все пути одинаковы: они ведут в никуда. Но у одних есть сердце, а у других — нет. Один путь дает тебе силы, другой — уничтожает тебя.
- Карлос Кастанеда
Решения задачи коммивояжера, полученные вычислительной системой на основе амёбы. Примеры туров коммивояжёра по четырём, пяти, шести, семи и восьми городам, полученные в экспериментах, где каждый тур окрашен в красный цвет на соответствующих каналах с правого рисунка. Левые панели показывают переданные светлые изображения начальных состояний (
Группа японских исследователей из Университета Кейо в Токио продемонстрировала, что амёбы способна генерировать приближённые решения удивительно сложной математической задачи, известной как задача коммивояжера.
Читать полностью »
Среди методов решения задачи коммивояжёра метод ближайшего соседа привлекает простотой алгоритма. Метод ближайшего соседа в исходной формулировке заключается в нахождении замкнутой кривой минимальной длины, соединяющей заданный набор точек на плоскости [1]. Моё внимание привлекла наиболее распространённая реализация данного алгоритма в пакете Mathcad, размещённая в сети на ресурсе [2]. Сама реализация не совсем удобна, например, нельзя вывести матрицу расстояний между пунктами или проанализировать альтернативные маршруты.
На ресурсе [2] приведена следующая вполне справедливая критика данного метода. «Маршрут не оптимальный (не самый короткий) и сильно зависит от выбора первого города. Фактически не решена задача коммивояжера, а найдена одна гамильтонова цепь графа». Там же предложен путь некоторого усовершенствования метода ближайшего соседа. «Следующий возможный шаг оптимизации — «развязывание петель» (ликвидация перекрестий). Другое решение — перебор всех городов (вершин графа) в качестве начала маршрута и выбор наикратчайшего из всех маршрутов». Однако реализация последнего предложения не приведена. Учитывая все перечисленные обстоятельства, я решил реализовать приведенный алгоритм на Python и при этом предусмотреть возможность выбора начального пункта по критерию минимальной длины марщрута.
Читать полностью »
Не так давно команда исследователей из Стэнфорда и Университета Макгилла побили 35-летний рекорд по информатике на невообразимо малую величину – на четыре сотых триллионной триллионной триллионной доли процента. Прорыв – сделанный в классической для информатики задаче коммивояжёра – был слишком малым для какого бы то ни было практического значения, но он вдохнул новую жизнь в поиски улучшенных приближённых решений.
Задача формируется так: для набора городов, соединённых дорогами, необходимо найти кратчайший путь посещения каждого города с возвратом в точку старта. У решений задачи есть практические применения от сверления отверстий в печатных платах до управления расписанием задач на компьютере и упорядочивания свойств генома.
Читать полностью »
Приветствую всех читателей. Сегодня попробую продолжить серию достаточно редких статей, посвящённым естественным алгоритмам. В частности, эта статья будет посвящена модификации муравьиного алгоритма, известной как Max-Min Ant System (MMAS). Я расскажу об отличиях от классического муравьиного алгоритма и о причинах внесения таких модификаций. Подробности под катом.
Читать полностью »
В этом небольшом посте я продолжу тему, которую поднимал в своих старых двух постах
Часть 1
Часть 2
А именно, расскажу о небольшой идее, которая недавно пришла мне в голову, и которая помогает решить поставленную задачу немного лучше.
Так что добро пожаловать под хабракат
Читать полностью »