- PVSM.RU - https://www.pvsm.ru -
Для облегчения понимания, будем считать, что граф связанный, а именно, что из любой вершины графа всегда можно попасть в любую другую.
Представим такую ситуацию, из города А в город Б ведёт две пустые дороги с одинаковым покрытием, какую выбрать лучше? Правильный ответ: которая короче.
Значит граф взвешенный, так как каждому ребру можно поставить в соответствие число, например, являющееся длиной соответственной дороги. Такая система будет выглядеть примерно вот так…
Вместо того, чтобы над рёбрами писать кучу характеристик, обычно пишут функцию, а именно зависимость времени прохождения участка дороги от количества автомобилей.
На данной схеме — это количество машин, проезжающих через выбранное поперечное сечение за единицу времени на промежутке между городами 1-2
Пусть ёмкость ребра — это максимальная интенсивность потока, проходящая через ребро.
А насыщенное ребро — это ребро, по которому проходит максимальный поток.
Присвоим каждому участку пару чисел (,). — достигнутый до сих пор поток по ребру, вначале он равен нулю, затем это число будет только увеличиваться, пока не достигнет , ёмкости ребра.
Пока хотя бы на одном маршруте из все рёбра — ненасыщенные (то есть на всех рёбрах < ), цикл продолжается.
1. Ищем любой участок трассы, содержащий только ненасыщенные рёбра из в . Если подобный участок мы найти не можем, то цикл прекращается, максимальный поток, который мы пытаемся найти — это сумма потоков рёбер, приходящих в .
2. Мы нашли дополняющий маршрут. Определяем значение максимального потока , который мы можем пропустить по данному маршруту. Он определяется как минимальная из всех возможных разностей ёмкости и существующего потока c по всем рёбрам маршрута.
3. Каждое на ребре складываем с , таким образом хотя бы одно ребро преобразуется в насыщенное.
4. Возвращаемся к (1.)
На рисунках указаны скорости потока в час пик и схема работы перекрёстка.
Какая длительность фаз светофора оптимальная (чтобы количество машин на перекрёстке было минимальным)?
Автор: Alex_Microsoft
Источник [1]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/matematika/263414
Ссылки в тексте:
[1] Источник: https://habrahabr.ru/post/337310/
Нажмите здесь для печати.