Существует ли алгоритм поиска кратчайшего пути в графе с указанием нескольких точек?
Здравствуйте, уважаемые it-специалисты.
Суть задачи. Есть несколько многоэтажных зданий. В каждом из них, на каждом этаже расположены комнаты.
Задача.
На входе пользователь указывает комнаты (как правило от 2 до 10, где-то), в которые ему нужно попасть за один обход в рамках всех этажей всех зданий.
А на выходе должен получать кратчайший маршрут обхода этих точек.
И что-то поискав в интернете на подобное не наткнулся.
Есть ли опыт решения подобных задач?.. Или может представление, куда копать?
P.S. Пишем на php с базой данных mysql. Проект не высоконагруженный. Есть возможность задействовать шустрый сервер.
С вашими ограничениями подойдет решение полным перебором.
Сначала алгоритмом Флойда ищем все кратчайшие расстояния между выбранными вершинами.
Потом перебираем все последовательности обхода и считаем минимум. Таких последовательность будет 10! = 3,6 * 10^6 даже на самом простом компьютере должно перебираться не более секунды.
Это задача коммивояжера. Для 10-20 комнат решается через динамическое программирование. Для большего нужно смотреть конкретные данные. Если я правильно понимаю, можно решить задачу для каждого здания отдельно, потом совместить.
В-общем, да, можно решать для каждого здания отдельно. Но разве задача коммивояжера - это не проход каждой вершины в графе по одному разу?.. У меня в задаче таких условий нет. И нужно входной узел задается строго (вход в здание)
Повторение -- не проблема. Считаете расстояние между каждой парой комнат и на этом ищете коммивояжера. Начальную точку можно задать аккуратными начальными условиями динамики.
Либо вы не указали все условия, либо задача очень простая.
Ответ: строить проход по все комнатам в контексте одно этажа, далее следующий этаж (куда нужно зайти)
В-принципе, так и хотел. Но ведь в рамках одного этажа тоже нужен алгоритм прохода. И в рамках этажа может быть до 10 комнат, и во все может быть придется зайти.
С таким количеством точек можно простейшим волновым алгоритмом. https://www.youtube.com/watch?v=9ev9Y-hJhj4
Само собой, при подсчете волны надо учитывать веса ребер, в видео по-моему про это нет.
