Что вы знаете о графах?
Что вы знаете о графах?
Не о тех, которые вельможи, а о тех, которые фигуры из вершин и рёбер.
Наверное, самый часто встречаемый в быту граф – это карта движения общественного транспорта. Например, карта метро (рис 1). С ее помощью можно легко построить маршрут от одной вершины (станции) до другой. И чем больше кольцевых линий, дополнительных диаметров, пересадочных станций – тем больше вариантов маршрута можно найти.
Очевидно, что чтобы добраться от станции А до станции Б нам нужно, чтобы они были связаны между собой ребрами (перегонами) – непосредственно или через другие вершины. Доехать от Невского проспекта до Охотного ряда на метро пока, к сожалению, не получается. Граф, в котором можно найти путь от любой вершины к любой другой называется «связным».
Но как мы выбираем маршрут, по которому поедем?
Одна из задач теории графов – это поиск кратчайшего, или оптимального, пути.
Что лучше: проехать 7 остановок, сделать пересадку, проехать одну, сделать еще одну пересадку, и проехать еще 5? Или проехать 9, сделать одну пересадку и проехать еще 7?
Под словом «кратчайший» можно понимать разные характеристики в зависимости от условий конкретной задачи. Маршрут, оптимальный для одного пассажира, может оказаться неприемлемым для другого.
Для человека, панически боящегося замкнутых пространств, предпочтительным будет маршрут с наименьшим временем нахождения непосредственно в поезде (в случае метро, возможно, это будет маршрут с наименьшим суммарным количеством перегонов). Для опаздывающего – с наименьшим временем, затрачиваемым на поездку в целом. Для того, кому сложно ходить – маршрут с наименьшим количеством пересадочных стаций с длинными переходами.
Для формализации этих условий вводится такое понятие, как вес ребра и вершины – то есть, условно, ресурсы, затрачиваемые на прохождение этого участка маршрута по графу (или получаемые, если мы играем в пакмана и собираем точки – но тогда и задача становится обратной и нам нужно найти маршрут с наибольшим суммарным весом). В случае с метро весом ребра можно принять длительность перегона между станциями. Для человека с клаустрофобией может быть введен, например, понижающий коэффициент для перегонов по открытым веткам.
А в случае со станциями ситуация чуть сложнее. Кроме непосредственно времени, затрачиваемого на остановку поезда для посадки и высадки пассажиров, в разных ситуациях могут применяться и другие параметры.
Например, при проезде станции нам не важно, является она пересадочной или нет. Но если мы хотим пересесть на другую ветку, то при выборе оптимального пути нам нужно учесть сам факт перехода (оторвать попу от сидения – задача не из легких), длительность этого перехода (включая как непосредственно расстояние, которое необходимо пройти, так и интенсивность пассажиропотока и риск оказаться в толпе пингвинов), а также наличие лестниц или эскалаторов.
Таким образом, у каждой станции-вершины появляется набор весов, применимых при прохождении через эту вершину в разных условиях (пример показан на рис. 2). Чтобы избавиться от этого усложнения, мы можем вместо одной вершины-пересадочной станции изобразить на графе количество вершин, соответствующее физически существующим станциям разных веток, и провести между ними дополнительные ребра, вес которых соответствует затратам на совершение конкретного перехода (это показано на рис. 3).
Но что, если при пересадке со станцию А на станцию Б надо подняться по лестнице, а при пересадке с Б на А – спуститься? Если вы тащите с собой чемодан без ручки, подъем по лестнице будет сложнее, зато на спуске прекрасно поможет гравитация. Получается, что вес ребра-пересадки будет зависеть еще и от направления движения. В таком случае пересадочные станции нам придется соединять не одним ребром, а двумя, с указанием направления движения на конкретном ребре (см рис. 4 со стрелочками), которое мы теперь можем гордо именовать дугой.
Граф, в котором все ребра имеют направления (являются дугами), называется ориентированным, в котором нет ни одной дуги – неориентированным, а тот, в котором есть и ребра, и дуги – смешанным.
Когда мы назначаем всем ребрам и вершинам графа веса, наш граф получает название «взвешенный». Если бы все станции были связаны между собой прямыми перегонами без промежуточных станций и пересадок, метро представляло бы собой полный граф (надеюсь, до этого амбициозные планы по строительству метро не дойдут).
И вот, представив схему метро в виде связного смешанного взвешенного графа, мы наконец можем выбрать маршрут поездки.
Для решения этой задачи разработаны различные алгоритмы, отличающиеся методами поиска пути, затрачиваемыми ресурсами (временем, вычислительными мощностями, сложностью реализации), требованиями к исходным данным и их предварительной обработке (например, исключение заведомо непригодных вариантов или ввод эвристических предположений о весе различных путей), а также критериями выбора результата.
Понятно, что для нахождения самого-самого оптимального пути нужно перебрать все существующие варианты, затем сравнить их веса и выбрать наименьший. Но на это может уйти неприемлемо много времени, за которое исходные данные изменятся и результат потеряет актуальность (метро быстро строят, да). Можно оптимизировать процесс, прекращая поиск пути, если в процессе расчета его длина оказывается больше, чем длина кратчайшего из уже найденных путей.
Кроме того, сами пути можно искать, следуя разным принципам: двигаясь по ребрам с наименьшим весом (предполагая, что чем меньше каждое из слагаемых, тем меньше будет итоговая сумма), перебирая как можно больше вариантов ответвлений (поиск «в ширину») или последовательно идущих ребер (поиск «в глубину»).
Критерии остановки и принятия решения о приемлемости результата также различаются в зависимости от алгоритма, конкретной задачи и организационных и технических возможностей и ограничений. Это может быть и просто факт обнаружения маршрута, и получение маршрута с весом, меньшим веса ранее используемого или эмпрически предложенного маршрута или заданных максимальных допустимых затрат, и временнЫе ограничения на выполнение алгоритма с выбором лучшего варианта из тех, которые удалось найти.
