Алгоритм поиска кратчайшего пути через все вершины?

Question

[Alex00qqw]

Мусоровоз должен собрать отходы из всех точек сбора и вернуться в гараж из которого вышел. Нужно найти самый короткий путь через все заданные точки. Подскажите пожалуйста какой алгоритм можно использовать? Возможно ли решить задачу с помощью нейронных сетей? Натравить НС на данные которые у нас есть. У нас есть история посещения точек водителями. Соответственно мы можем предугадать маршрут

Comments

[Lynn «Кофеман»]

Классическая задача коммивояжёра.
Описана в каждом первом учебнике

[Lynn «Кофеман»]

Начните с википедии https://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D...

[Alex00qqw]

Также нужно учесть что в любой момент водитель может сойти с маршрута. И его нужно построить по новому. То есть не нужно возвращать к точке из которой стартует автомобиль. Задача проехать через все точки из точки A в точку B

[Lynn «Кофеман»]

Тогда вам туда https://yandex.ru/dev/routing/

[Сергей П]

Alex00qqw, если задача реальная, а не теоретическая, то вам не нужен оптимальный маршрут. На поиск оптимального и доказательство того, что лучше не найти могут уйти миллиарды лет.

[Alex00qqw]

Да задача сложная но в нашем случае у одного автомобиля может быть максимум 15-25 точек сбора поэтому можно попробовать жадный алгоритм или перебор с возвратом. Если есть у кого нибудь идеи. Может быть напишите пример на java или псевдокод. Спасибо большое за ответы

[Сергей Ильин]

Alex00qqw, вам предложили хороший вариант с Яндексом.

[Alex00qqw]

Сергей Ильин, Это очень дорого

[Сергей Ильин]

Alex00qqw, дешевле, чем вам человек будет это разрабатывать. или вы как себе это представляли? вам отдадут всю логику (в псевдокоде, например, или питоне) и вы потом это закажете за 10 тыр (или напишете сами)?

[Alex00qqw]

Сергей Ильин, Слушайте вам похоже на другой форму нужно, по торговле ))

[Сергей Ильин]

Alex00qqw, видимо, угадал.

[Alex00qqw]

Сергей Ильин, Пусть будет так

Answer 1

[Alex00qqw]

Решение нашел (приближенное) с помощью двух подходов
1) Муравьиный алгоритм, вполне рабочее решение https://www.baeldungtest.com/java-ant-colony-optim...
2) Использовать Google OR-Tools https://developers.google.com/optimization/routing/tsp

Сначала удалось решить задачу способом 1 но сейчас в рабочем коде используем 2

Answer 2

[Сергей П]

Это NP-полная задача. При достаточном количестве мусорных баков эффективно и быстро решить её просто нельзя.
Важно понимать какое вам нужно решение: достаточно хорошее или оптимальное. Возможно, что для поиска оптимального решения вам просто не хватит ресурсов.
Оптимальный маршрут ищется перебором иногда с разными оптимизациями, которые, впрочем, не сильно помогут в произвольном случае.
Субоптимальные ищутся, к примеру, генетическими алгоритмами.

Эта задача называется задачей коммивояжера:

Задача коммивояжёра относится к числу трансвычислительных: уже при относительно небольшом числе городов (66 и более) она не может быть решена методом перебора вариантов никакими теоретически мыслимыми компьютерами за время, меньшее нескольких миллиардов лет.

Comments

[Alex00qqw]

Да задача сложная но в наем случае у одного автомобиля может быть максимум 15-25 точек сбора поэтому можно попробовать жадный алгоритм. Если есть у кого нибудь идеи. Может быть напишите пример на java или псевдокод. Спасибо большое

[ayazer]

Alex00qqw, для 15-25 точек это элементарная задача которая спокойно решается на коленке через 2-opt (https://en.wikipedia.org/wiki/2-opt). Если будет еще актуально - я вечером выковыряю пример для расшарить.

[Сергей П]

Alex00qqw, ну то есть погуглить алгоритм типового решения перебором задачи1 коммивояжера вам самому лень, надо чтобы вам прям написали? Это ж типовая задача.

[Сергей Ильин]

Сергей Паньков, чуваку, скорее всего (из какого-нибудь ЖЭКа) показалось, что "я сейчас схожу на этот сайт, мне тут все расскажут - напишут и потом мы это бесплатно прикрутим у себя / продам своему ЖЭКу"

[Alex00qqw]

Сергей Паньков, Я никого не заставляю писать код и мне не лень. Просто для меня вопрос довольно сложный

[ayazer]

Лентюй, хм... наверно надо было действительно уточнить. Т.к. задача "построить траекторию движения мусоровозов" не звучит как академическая, где нужно оптимальное решение - я исходил из того что был использован неверный термин и на самом деле нужно достаточное решение. И в таком случае 2-opt вполне хватит. А для оптимального решение - да, нужно будет еще решать проблему попадания в локальный экстремум и доказывать оптимальность (хотя это не исключает использование k-opt, но уже как одной с частей алгоритма).

[Alex00qqw]

Могут ли помочь нейронные сети и AI если есть история реальных маршрутов?

[ayazer]

Alex00qqw, ну гвозди и микроскопом можно забивать. Вот только зачем? для вашей задачи есть куча эвристических подходов которые оптимальный результат для 25 точек найдут меньше чем за секунду. Для вашей задачи есть куча специализированых солверов типа https://developers.google.com/optimization/routing/tsp, которым надо просто правильно скормить данные и получить результат.

Answer 3

[freeExec]

Во всех картографических сервисах есть API матрица расстояний, это как раз то что вам нужно.

Comments

[Сергей П]

Ему этого недостаточно. Он хочет строить оптимальный маршрут. матрица расстояний (а в OSRM, например, даже не расстояний, а времён на перемещения) - это первый этап. Фактически это веса графа.
А потом на графе нужно выбрать путь и это NP-полная задача, хотя в размерностях автора она решается без проблем и в лоб.

[freeExec]

Сергей Паньков, А по вашему оптимальное это что? Так же получить значения для рёбер графа тут самое сложное с технической точки зрения. Подобрать с наименьшей характеристикой тут уже дело простое, решается одной программой.

[ayazer]

freeExec, ох. получить значения для ребер графа = сходить в картографическое апи. а вот задачу "найти самый короткий путь который пройдет по всем" решают лет 200 уже. Но да, на размерности в 25 точек подойдет любой TSP солвер

[Сергей П]

freeExec, по-моему, оптимальный маршрут - это самый эффективный экономически. Тут, если задуматься, тоже торчат уши не решаемой однозначно задачи многокритериального выбора.
Но в общих чертах стоимость маршрута складывается из времени перемещения по нему и потраченного топлива.
Можно предположить, что полное покрытие графа с минимальными издержками - это оптимальный маршрут для данной задачи.

Однако, практический аспект не только имеет тенденцию немного упрощать задачу (кол-во точек в день ограничено), но и радикально усложнять её: мусоровозов может понадобиться несколько (ведь один, возможно, тупо не будет успевать всё опустошать), нужно строить график по дням и как-то эффективно зонировать регионы (чтобы меньше выгружать мало заполненные контейнеры)... короче, тут сложность задачи уже превысило все рамки, чтобы говорить о математической оптимальности.

Нечеткие системы спасут мир. Пока мы будем решать задачу оптимального обхода мир погрязнет в мусоре.