Алгоритмы, дискретная математика и пр.'s Journal (original) (raw)
2:48a
Метро Решил перепостить сюда мои изыскания в вопросе поиска пути между станциями метро - может кому интересно.
----------
Написал программу для нахождения кратчайшего пути между двумя станциями метро.
Уже давным-давно реализовано, но мне нужна своя версия с блекджеком и шлюхами!
Нужно построить путь - некую последовательность станций, причем первый элемент пути - это начальная станция, и последний элемент - станция, до которой нужно доехать:
В этом примере путь представляет собой следующую последовательность станций:
Путей от одной станции до другой может быть много, поэтому время искомого пути должно быть минимальным среди всех остальных путей.
Процедура НайтиПуть имеет в качестве единственного входного параметра переменную ЧастичноПостроенныйПуть. На разных этапах работы программы в примере это будут пути (Тимирязевская; Дмитровская; Савеловская), или (Тимирязевская; Дмитровская; Савеловская; Менделеевская; Цветной бульвар; Трубная), и так далее, пока не дойдем до Авиамотороной. Естественно, программа может пойти "неверно", т.е. от Тимирязевской наверх по серой ветке:
Но в этом случае она упрется в конечную (Алтуфьево), и дальше идти некуда, разве что обратно, но в пути не может быть повторяющихся станций и зацикливаний - в этом случае он очевидно не будет минимальным по времени.
Ключевой момент для реализации программы - это использование рекурсии (это когда процедура вызывает саму себя).
Процедура НайтиПуть будет получать ЧастичноПостроенныйПуть, смотреть на последнюю добавленную станцию этого пути, и искать следующую станцию, на которую она имеет один перегон или переход. Например, для Тимирязевской это две станции - Петровско-Разумовская и Дмитровская. Для станции Цветной Бульвар это три станции - Менделеевская, Чеховская и еще переход - Трубная. Будем называть такие станции соседними. Для конечных станций существует только одна соседняя станция - для Алтуфьево это станция Бибирево.
Найдя соседнюю станцию (или несколько соседних) для последней станции ЧастичноПостроенногоПути, процедура организует цикл по количеству найденных соседних станций, и в каждой итерации цикла вызывает саму себя, но теперь параметром в этом вызове будет другой ЧастичноПостроенныйПуть, равный прежнему ЧастичноПостроенномуПути плюс СоседняяСтанция. Так происходит до тех пор, пока соседней станцией для последнего элемента одного из ЧастичноПостроенныхПутей не станет Авиамоторная.
Вызова процедуры не происходит в следующих случаях: когда очередная соседняя станция уже есть в ЧастичноПостроенномПути (это случай зацикливания, и он не даст минимального времени), и когда время, необходимое для ЧастичноПостроенногоПути, начинает превышать уже найденное значение минимального времени. С первым случаем все ясно, во втором поясню: допустим мы уже нашли
какой-то
путь от Тимирязевской до Авиамоторной (он записан в глобальную переменную МинимальныйПуть, и совсем необязательно что он самый минимальный - он вообще может обойти полметро, прежде чем дойдет до нужной станции - он минимален на данный момент среди всех найденных), тогда, если время ЧастичноПостроенногоПути начинает превышать время МинимальногоПути, то нет смысла дальше достраивать ЧастичныйПуть - его время заведомо будет больше Минимального.
Если мы нашли новый путь, и его время меньше МинимальногоПути - то записываем этот путь в МинимальныйПуть. И так до тех пор, пока не найдем все пути - таким образом в конце работы программы будет найден самый минимальный путь.
Я реализовал питерское метро - там поменьше рисовать интерфейс.
В работе:
