Разное

Есть схема общественного транспорта города. Для простоты возьмём только автобусы. Как она выглядит, думаю все представляют.

Есть таблица остановок по этой схеме. Вид:

route_id   stop_id

здесь:

route_id - номер маршрута stop_id - id конкретной остановки.

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

Комментарии:

Кратчайший в экономическом смысле. т.е. даже если с пересадкой ехать ближе, но есть прямой вариант, то кратчайшим будет он.

Расстояние замеряются в остановках. Т.е. расстояние между A и B в данной задаче есть количество остановок между ними.

Мои мысли:

1. Ищем прямой маршрут.
SELECT route_id FROM routes WHERE stop_id = 2 OR stop_id =4
потом в цикле проверяем на полное совпадение (может можно обойтись одним запросом?)

2. Если 1 вариант не дал результатов, то ищем маршрут с одной пересадкой. Для этого находим все маршруты проходящие через пункт назначения и начинаем их перебирать в цикле. Внутри этого цикла мы проходим по каждому маршруту от остановки до остановки и смотрим какие маршруты проходят через эти остановки. И ищем на этих маршрутах id пункта назначения.

3. Если нет результатов то смотрим с 2-мя пересадками и т.д.

Доказательство не проводил, но есть интуитивная уверенность что решение задачи существует всегда. Если нет, то можно ограничить поиск 2-мя пересадками.

Как вообще решают такие задачи?

PS. Сразу говорю, времени на вспоминание/изучение теории графов нет :( Пока, по крайней мере.

ну я бы делал так:
[схема в приложенном файле, ищем путь от 10 до 5]
1. выбрать ВСЕ точки пересадок, запрос для этого имеет вид:

select stop_id, count(stop_id) as num from routes group by 1 having num > 1

получаем айдишки 9, 6, 4
2. по найденным остановкам выбираем номера маршрутов, получаем массив вида

$allroutes = array(     route1 => array(9, 4), //остановки пересадок     route2 => array(9, 6),     route3 => array(4, 6) )

3. берем нашу начальную остановку [10] и запускаем рекурсивный алгоритм
- начинаем движение по маршруту
- если встретилась точка пересадки - "форкаемся" - переходим на тот маршрут
- считаем остановки и смотрим, не дошли ли до искомой

в итоге:
- пройдя по маршруту 10-9-8-7-6-5 насчитаем 6 остановок
- пройдя по маршруту 10-9-11-12-4-5 насчитаем тоже 6..

вот как то так, только в БД нифига не указано какая остановка за какой идет.. эт на схеме все хорошо видно, а в БД - никак не узнать. в рекурсивной функции необходимо использовать понятие направления, т.е. когда на 4 остановке форкаемся - указать, что идем в сторону 3-й или 5-й...
так что стоит исправить этот недочет и можно юзать приведенный алгоритм

Спасибо. Особенно в части запроса на выборку всех узлов.
Дальше дело техники:
Мы получили сетку узлов.
Узел - остановка где пересекаются два и более маршрута.
Для каждого узла имеем 2 координаты: номер маршрута и порядковый номер остановки на нём.
Т.е. больше обращений к базе, получается, не понадобится. Работаем целиком с этой сеткой. Нужно построить алгоритм её обхода.
Так получается? Или я что-то упустил?

> Мы получили сетку узлов.
> Узел - остановка где пересекаются два и более маршрута.
думаю понадобится выбирать все остановки, а не только станции пересадок. ведь мы будем их обходить рекурсивно!
получится массив маршрутов, каждый из которых будет представлен своим набором станций
затем строится массив $allroutes как указано выше, и запускается рекурсия
примерно так
сейчас совсем некогда писать код, так что сорри, только теория..

и больше запросов к базе не будет, все итак выбрано в массивы )