Задача о maxmin пути.

Пусть G=(V,E,c) — сеть, s,v V и р: s=v₀,v₁,…,v_k⁼v — s-v-путь в G. Весом пути р назовем число

m(p) = min{c(v_i-1, v_i): i=l,2,...,k}.

Задача о maxmin пути формулируется следующим образом: среди всех s-v-путей в сети G найти путь максимального веса.

Иногда эту задачу называют задачей об узких местах. Для ил­люстрации разберем следующий пример.

Рассмотрим дорожную сеть, включающую мосты. Будем счи­тать, что превышение грузоподъемности некоторого моста при перевозке груза приводит к разрушению данного моста. Допус­тим, что мы хотим определить максимальный вес груза, который может быть транспортирован в рассматриваемой дорожной сети из пункта s в пункт v без превышения грузоподъемности находя­щихся на пути движения транспорта мостов.

Для решения этой задачи построим сеть G=(V,E,c), множест­вом узлов которой объявим пункты s и v, а также все перекрестки дорожной сети. Будем говорить, что дорога х, соединяющая пе­рекрестки w и u, непосредственно их соединяет, если х не прохо­дит через другие перекрестки. Для дороги х положим с(х) рав­ным минимальной из грузоподъемностей мостов, находящихся на дороге х; если дорога х мостов не содержит, то считаем, что с(х)=+∞. Будем считать, что два какие-нибудь узла w и и сети G соединены дугами (w,u) и (u,w), если есть хоть одна дорога х, непосредственно соединяющая перекрестки w и u. Положим c(u,w)=c(w,u)=max{c(x) : х непосредственно соединяет w и u}. Аналогично определяются дуги, инцидентные пунктам s и v. правда будем считать, что из s дуги только исходят (то есть ис­ключим дуги вида (w,s), w V), а в v дуги только входят.

На рис.6.8.а дан пример дорожной сети, соединяющей пункты s и v: цифрами обозначены перекрестки, буквами — мосты, а числа в скобках означают грузоподъемность соответствующего моста. Соответствующая сетевая модель приведена на рис.6.8.б, где каждое неориентированное ребро вида {i,j} соответствует двум дугам (i,j) и (j,i). Обращаем внимание читателя на вес дуги (3,v), который равен 80, ибо пункты 3 и v соединяют две дороги х и х' для которых с(х)=80, и с(х')=60. Поэтому c(3,v)=80.

Рис.6.9. Пример интерпретации задачи о maxmin пути.

Для решения задачи о maxmin пути в произвольной сети G=(V,E,c) с необязательно неотрицательными весами мы лишь немного модифицируем изложенный ранее в параграфе 6.2 алго­ритм Дейкстры. Принцип «жадности» в вычислении maxmin рас­стояний выглядит здесь следующим образом: вычисляем после­довательно каждый раз maxmin расстояние до наиболее далекого узла от s среди всех тех узлов, до которых maxmin расстояние еще не вычислено.

Более точно наши рассуждения здесь таковы. Обозначим че­рез dm(v) максимальный вес среди всех s-v-путей, то есть maxmin расстояние от s до v.

Положим S={s} и dm(s)=+∞.

Будем теперь добавлять к S по одному узлу так, что множест­во S состоит на каждом шаге из тех узлов v, для которых dm(v) вычислено, и для всех v S и w V\S справедливы неравенства dm(v) ≥ dm(w). Для каждого w V\S положим

D(w)= max{min{dm(v), c(v,w)} : v S}.

Понятно, что в этой формуле появляется максимум вместо мини­мума в аналогичной формуле (1) из параграфа 6.2, ибо нас инте­ресует путь максимального веса.

Очередной узел w*, который следует добавить к S, выбирается под условием:

D(w*)=max{D(w): w V\S}.

Обоснование корректности такой модификации алгоритма Дейкстры проводится аналогично доказательству корректности самого алгоритма Дейкстры.

Формально можно сказать, что вся модификация заключается в том, что все знаки суммы заменяются на минимумы, а все ми­нимумы в алгоритме Дейкстры — на максимумы. Поэтому мы не будем приводить здесь исправленный указанным способом алго­ритм 6.3.

Рис 6.9. Работа модифицированного алгоритма Дейкстры

На рисунке 6.9 каждое неориентированное ребро {v,w} пред­ставляет собой две ориентированные дуги (v,w) и (w,v). Читателя не должен смущать тот факт, что веса дуг (1,2) и (2,3) равны +∞. Это обстоятельство следует понимать как то, что, во-первых, дуги (1,2) и (2,3) имеются в сети, и, во-вторых, они имеют беско­нечно большой вес. Бесконечно большой вес некоторых дуг мо­делирует ситуацию, встречающуюся в задаче о самом надежном пути перевозки груза по дорожной сети. Естественно считать, что дорога, по которой может быть транспортирован груз любого веса, соответствует дуге бесконечно большого веса.

При рассмотрении maxmin задачи веса несуществующих дуг естественно считать равными -∞.

Сами пути легко строятся с помощью меток ОТЕЦ. Отметим только, что такая модификация алгоритма Дейкстры не гаранти­рует построения минимального по числу дуг наилучшего в смыс­ле maxmin-расстояния пути. Например, в сети из рис 6.9 до узла 5 будет найден путь 1-2-3-5, в то время как путь 1-3-5 имеет тот же вес.

Отметим, что задача о minmax пути может быть сформулиро­вана и решена аналогично задаче о maxmin пути.