Рубрика «задача коммивояжёра»
Эдсгер Дейкстра. Человек, который придумал параллельные вычисления
2026-05-04 в 9:01, admin, рубрики: ruvds_статьи, алгоритм кратчайшего пути, задача коммивояжёра, задача об обедающих философах, каллиграфия, параллельный алгоритм, проблема взаимной блокировки, семафоры, Эдсгер Дейкстра
Д-р наук, профессор Эдсгер ДейкстраЧитать полностью »
Глубокое Q-обучение (DQN)
2025-05-03 в 16:11, admin, рубрики: DQN, TSP, задача коммивояжёра, искусственный интеллект, обучение с подкреплением
Немного контекста
Подходит к завершению серия моих заметок про использование идей искусственного интеллекта для решения задачи коммивояжера (TSP). Я последовательно разобрал некоторые классические решения TSP и далее рассказалЧитать полностью »
Внимание — это все, что нужно коммивояжеру
2025-01-17 в 8:45, admin, рубрики: Pointer Network, TSP, задача коммивояжёра, искусственный интеллект, механизм внимания, обучение с подкреплением
Где начинается ИИ в задаче коммивояжера?
Заголовок отсылает к знаменитой работе Attention Is All You NeedЧитать полностью »
Когда ИИ может в оптимизацию…
2024-12-09 в 6:16, admin, рубрики: mip, TSP, задача коммивояжёра, искусственный интеллект, оптимизация, точное решение
Всем привет!
Меня зовут Дмитрий и по месту своей последней работы я дата консультант и владелец продукта, но сейчас мне больше подходит роль энтузиаста-исследователя.
Про ИИ
Алгоритм генетической колонии пчел для задачи коммивояжера
2024-11-04 в 15:16, admin, рубрики: генетический алгоритм, задача коммивояжёра, Искусственная Пчелиная Колония, оптимизационные задачи, Оптимизационные методыI. Введение
Выбор наилучшего элемента из нескольких существующих альтернатив называется задачей оптимизации. Во большинстве таких задачах исчерпывающий поиск нецелесообразен. Это имеет важные приложения в нескольких областях, включая искусственный интеллект, машинное обучение, математику и программную инженерию. Большинство таких задач считаются NP-трудными, то есть их нельзя решить оптимально за полиномиальное время вычислений. Некоторые общие задачи, связанные с оптимизацией, включают задачу коммивояжера, задачу о минимальном остовном дереве и другие.
Задача коммивояжёра в общем виде. Наибыстрейшее точное решение
2024-09-04 в 16:19, admin, рубрики: задача коммивояжёра, Линейное программирование
К величию есть только один путь, и этот путь проходит через страдания.
- Альберт Эйнштейн
Эта работа является заключением пятилетнего марафона по поиску самого быстрого способа нахождения минимального точного решения для задачи коммивояжёра в общем виде.
Задача коммивояжера (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 и при этом предусмотреть возможность выбора начального пункта по критерию минимальной длины марщрута.
Читать полностью »