Существует ли алгоритм поиска кратчайшего пути в графе с указанием нескольких точек?

Question

[Хайбулла Мусаев]

Здравствуйте, уважаемые it-специалисты.

Суть задачи. Есть несколько многоэтажных зданий. В каждом из них, на каждом этаже расположены комнаты.

Задача.
На входе пользователь указывает комнаты (как правило от 2 до 10, где-то), в которые ему нужно попасть за один обход в рамках всех этажей всех зданий.
А на выходе должен получать кратчайший маршрут обхода этих точек.

И что-то поискав в интернете на подобное не наткнулся.
Есть ли опыт решения подобных задач?.. Или может представление, куда копать?

P.S. Пишем на php с базой данных mysql. Проект не высоконагруженный. Есть возможность задействовать шустрый сервер.

Comments

[Хайбулла Мусаев]

Зданий у нас то ли 2, то ли три. Этажей не помню сколько, комнат всего около 40-50.

Answer 1

[cjey]

С вашими ограничениями подойдет решение полным перебором.

Сначала алгоритмом Флойда ищем все кратчайшие расстояния между выбранными вершинами.

Потом перебираем все последовательности обхода и считаем минимум. Таких последовательность будет 10! = 3,6 * 10^6 даже на самом простом компьютере должно перебираться не более секунды.

Comments

[Хайбулла Мусаев]

Ваш алгоритм реализовал, все отлично работает. Спасибо за совет!

Answer 2

[SeptiM]

Это задача коммивояжера. Для 10-20 комнат решается через динамическое программирование. Для большего нужно смотреть конкретные данные. Если я правильно понимаю, можно решить задачу для каждого здания отдельно, потом совместить.

Comments

[Хайбулла Мусаев]

В-общем, да, можно решать для каждого здания отдельно. Но разве задача коммивояжера - это не проход каждой вершины в графе по одному разу?.. У меня в задаче таких условий нет. И нужно входной узел задается строго (вход в здание)

[SeptiM]

Повторение -- не проблема. Считаете расстояние между каждой парой комнат и на этом ищете коммивояжера. Начальную точку можно задать аккуратными начальными условиями динамики.

Answer 3

[Night]

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

Comments

[Хайбулла Мусаев]

В-принципе, так и хотел. Но ведь в рамках одного этажа тоже нужен алгоритм прохода. И в рамках этажа может быть до 10 комнат, и во все может быть придется зайти.

Answer 4

[_ _]

С таким количеством точек можно простейшим волновым алгоритмом.
https://www.youtube.com/watch?v=9ev9Y-hJhj4
Само собой, при подсчете волны надо учитывать веса ребер, в видео по-моему про это нет.