Максимизация методом назначения цены: задача о непересекающихся путях - Аппроксимирующие алгоритмы

В продолжение темы алгоритмов назначения цены рассмотрим фундаментальную задачу из области сетевой маршрутизации: задачу о непересекающихся путях. Начнем с разработки жадного алгоритма для этой задачи, а затем рассмотрим улучшенный алгоритм, основанный на назначении цены.

Задача

Чтобы сформулировать задачу, полезно вспомнить одно из первых практических применений задачи о максимальном потоке: нахождение непересекающихся путей в графах (обсуждалось в главе 7). Тогда мы искали пути, не пересекающиеся по ребрам, которые начинались в узле 5 и заканчивались в узле t. Насколько критично для разрешимости задачи требование о том, чтобы все пути начинались и заканчивались в одном узле? Используя методы из раздела 7.7, алгоритм можно расширить для поиска непересекающихся путей для расширенной конфигурации: имеется множество начальных узлов S и множество конечных узлов T, а задача заключается в нахождении путей, не пересекающихся по ребрам, причем эти пути могут начинаться с любого узла в S и заканчиваться на любом узле из T.

Однако мы рассмотрим случай, при котором каждый путь имеет собственную пару из начального и конечного узлов. А именно, будет рассмотрена следующая задача о нахождении максимальных непересекающихся путей: имеется направленный граф G с k парами узлов (s₁, t₁), (s₂, t₂), ..., (s_k, t_k) и целочисленная пропускная способность c. Каждая пара (s_i, t_i) рассматривается как запрос на маршрутизацию, то есть запрос на получение пути от s_i к t_i. Решение экземпляра состоит из подмножества удовлетворяемых запросов, I ⊆ {1, ..., k}, вместе с путями, которые удовлетворяют их без перегрузки одного ребра; путь Р_i для i ∈ I, так что P_i проходит из s_i в t_i, и каждое ребро используется не более чем c путями. Задача заключается в том, чтобы найти решение с наибольшим возможным |I|, то есть удовлетворить как можно больше запросов. Обратите вниманиие: пропускная способность c управляет допустимой степенью “повторного использования” ребер; при c = 1 пути должны быть полностью непересекающимися по ребрам, тогда как большие значения c допускают некоторое перекрытие путей.

Мы уже видели в упражнении 39 главы 8, что задача определения возможности удовлетворения всех к заявок маршрутизации для путей, не пересекающихся по узлам, является NР-полной. Нетрудно показать, что версия задачи, не пересекающаяся по ребрам (соответствующая случаю c = 1), также является NР-полной.

Для применения эффективных алгоритмов сетевого потока критично, чтобы конечные точки путей не образовывали явно заданные пары, как в задаче о максимальных непересекающихся путях. Чтобы этот момент стал более понятным, предположим, что мы пытаемся свести задачу максимальных непересекающихся путей к задаче о потоке в сети: определим множество источников S = {s₁, s₂, ..., s_k}, множество стоков T = {t₁, t₂, ..., t_k}, пропускную способность каждого ребра c и попробуем найти максимально возможное число непересекающихся путей, которые начинаются в S и заканчиваются в T. Почему из этого ничего не выйдет? Дело в том, что алгоритму потока невозможно сообщить, что путь, начинающийся в s_i ∈ S, должен заканчиваться в t_i ∈ T; алгоритм гарантирует лишь то, что путь закончится в некотором узле из множества T. В результате пути, сформированные на выходе алгоритма потока, могут не быть решением экземпляра задачи о максимальных непересекающихся путях, потому что они могут не связывать источник s_i с соответствующей конечной точкой t_i.

Задачи о непересекающихся путях, в которых требуется найти пути, соединяющие заданные пары терминальных узлов, очень часто встречаются в сетевых приложениях. Только представьте себе пути в Интернете, по которым передаются мультимедийные потоки или веб-данные, или пути в телефонной сети, по которым передается голосовой трафик¹. Пути с общими ребрами могут мешать работе друг друга, и слишком большое количество путей, проходящих через одно ребро, создаст проблемы. Максимально допустимый уровень совместного использования ребер зависит от конкретного применения. Полный запрет на пересечение путей — самое сильное ограничение, предотвращающее любые помехи между путями. Но, как вы вскоре убедитесь, в тех случаях, в которых допустимо некоторое совместное использование (даже если через ребро проходят всего два пути), возможны более эффективные аппроксимирующие алгоритмы.

Разработка и анализ жадного алгоритма

Сначала мы рассмотрим очень простой алгоритм для пропускной способности c = 1, то есть когда пути не должны пересекаться по ребрам. По сути, это жадный алгоритм, не считая того, что он предпочитает короткие пути. Мы покажем, что этот простой алгоритм является O(√m) -аппроксимирующим алгоритмом, где m = |E| — количество ребер в G. Может показаться, что это довольно большой коэффициент аппроксимации; это действительно так, однако есть довольно веская причина, по которой это фактически лучшее, на что можно рассчитывать. Задача о максимальных непересекающихся путях не только является NР-полной, но и плохо аппроксимируется: доказано (если только не окажется, что Р = NP), что алгоритм с полиномиальным временем не способен достичь границы апрроксимации, существенно лучшей O(√m) для произвольных направленных графов.

После разработки жадного алгоритма будет рассмотрен чуть более сложный алгоритм назначения цены для версии с пропускными способностями. Интересно, что алгоритм назначения цены работает намного эффективнее простого жадного алгоритма, даже если пропускная способность c ненамного выше 1.

Рис. 11.9. В этом случае критично, чтобы жадный алгоритм выбора непересекающихся путей отдавал предпочтение коротким путям перед длинными

Анализ алгоритма

Понятно, что алгоритм выбирает пути, не пересекающиеся по ребрам. Если предположить, что граф G является связным, он должен выбрать хотя бы один путь. Но как количество выбранных путей сравнивается с максимально возможным? Ситуация, в которой могут возникнуть проблемы, изображена на рис. 11.9: один из путей (из s₁ в t₁) очень длинный, и если выбрать его первым, мы потеряем до Ω(m) других путей.

Теперь покажем, что предпочтительность коротких путей в жадном алгоритме не только избегает проблему, представленную в этом примере, но и ограничивает количество других путей, с которыми может взаимодействовать выбранный путь.

(11.16) Алгоритм Greedy-Disjoint-Paths является (2√m + 1)-аппроксимирующим алгоритмом для задачи о максимальных непересекающихся путях.

Доказательство. Рассмотрим оптимальное решение: пусть I* — множество пар, для которых в этом оптимальном решении был выбран путь, а P*_i для i ∈ I* — выбранные пути. Обозначим I множество пар, возвращаемых алгоритмом, а P_i для i ∈ I — соответствующие пути. Требуется ограничить |I*| в отношении |I|. Ключевую роль в этом анализе играет возможность различать короткие и длинные пути, которые рассматриваются по отдельности. Путь будет считаться длинным, если он содержит не менее √m ребер; в противном случае путь считается коротким. Пусть I*_s обозначает множество индексов в I*, для которого соответствующий путь P*_i является коротким, а I_s — множество индексов I, для которого соответствующий путь Р_i является коротким.

Граф G содержит m ребер, и каждый длинный путь использует не менее √m ребер, так что в I* может быть не более √m длинных путей.

Теперь рассмотрим короткие пути в I*. Чтобы множество I* было намного больше I, должно быть большое количество пар, соединенных в I*, но не в I. Рассмотрим пары, соединенные оптимумом с использованием короткого пути, но не соединенные жадным алгоритмом. Так как путь P*_i, соединяющий s_i и t_i в оптимальном решении I*, является коротким, жадный алгоритм выбрал бы этот путь, если бы он был доступен, прежде чем выбирать какие-либо длинные пути. Но жадный алгоритм не соединил s_i и t_i, а следовательно, одно из ребер e на пути P*_i должно входить в путь P_j, выбранный ранее жадным алгоритмом. Мы будем говорить, что ребро e блокирует путь P*_i.

Длины путей, выбранных жадным алгоритмом, монотонно возрастают, так как у каждой итерации остается меньше вариантов выбора путей. Путь Р_j был выбран до рассмотрения P*_i, а следовательно, он должен быть короче: |Р_j| ≤ |Р*_i| ≤ √m. Таким образом, путь P_j является коротким. Так как пути, используемые оптимумом, не пересекаются по ребрам, каждое ребро в пути P_j может блокировать не более одного пути Р*_i. Отсюда следует, что каждый короткий путь Р_j блокирует не более √m путей в оптимальном решении, и мы получаем границу

Эта граница будет использована для получения границы общего размера оптимального решения. Для этого множество I* рассматривается как состоящее из трех типов путей в соответствии с предшествующим анализом:

♦ длинные пути, которых может быть не более √m;

♦ пути, также входящие в I;

♦ короткие пути, не входящие в /, которые только что были ограничены |I_s|√m.

Объединяя все сказанное, мы используем тот факт, что |I| ≥ 1 всюду, где может быть соединен по крайней мере один набор терминальных пар, и получаем заявленную границу:

Итак, мы получили аппроксимирующий алгоритм для случая, в котором выбранные пути должны быть непересекающимися. Как упоминалось ранее, граница аппроксимации O(√m) достаточно слаба, но если не окажется, что Р = NP, по сути, это лучший возможный результат для непересекающихся путей в произвольных направленных графах.

Разработка и анализ алгоритма назначения цены

Запрет на использование одного ребра двумя путями — крайний случай; в большинстве практических применений ребра могут использоваться несколькими путями. Сейчас мы разработаем аналогичный алгоритм, базирующийся на методе назначения цены, для случая, когда любое ребро может использоваться в c > 1 путей. В только что рассмотренном случае без пересечений все ребра рассматривались как равные, а предпочтение отдавалось коротким путям. Эту схему можно представить как простую разновидность алгоритма назначения цены: пути должны “платить” за использование ребер, и у каждого ребра имеется стоимость. Сейчас будет рассмотрена схема назначения цены, в которой ребра считаются более дорогими, если они использовались ранее, а следовательно, у них осталось меньше свободной пропускной способности. При таком подходе алгоритм будет распределять свои пути вместо того, чтобы “сваливать” их на одно ребро. Мы будем называть стоимость ребра е его длиной l, а длина пути определяется как сумма длин содержащихся в нем ребер: Параметр-множитель β используется для увеличения длины ребра при каждом его использовании очередным путем.

Анализ алгоритма

В ходе анализа мы сосредоточимся на простейшем случае, в котором одно ребро может использоваться не более чем двумя путями, то есть c = 2. Будет показано, что в этом случае значение β = m^1/3 обеспечивает лучший результат аппроксимации для алгоритма. В отличие от случая с непересекающимися путями (при c = 1) неизвестно, будут ли границы аппроксимации, полученные здесь для c > 1, близки к лучшим возможным для алгоритмов с полиномиальным временем вообще (при условии, что P ≠ NP).

Анализ случая без пересечения базировался на возможности различать “короткие” и “длинные” пути. Для случая c = 2 путь P_i, выбранный алгоритмом, будет считаться коротким, если его длина менее β². Пусть I_s — множество коротких путей, выбранных алгоритмом.

Затем мы хотим сравнить количество выбранных и максимально возможных путей. Пусть I* — оптимальное решение, а P*_i — множество путей, использованных в решении. Как и прежде, ключевая идея анализа — рассмотрение ребер, блокирующих выбор путей в I*. Длинные пути могут заблокировать многие другие пути, поэтому пока мы сосредоточимся на коротких путях в I_s. Однако пытаясь действовать по той же схеме, что и в непересекающемся случае, мы немедленно сталкиваемся с трудностями. В том случае длина пути в I* определялась количеством содержащихся в нем ребер, а на этот раз длины изменяются в ходе выполнения алгоритма, и теперь неясно, как определить длину пути в I* в целях анализа. Другими словами, когда измерять эту длину в контексте проводимого анализа? (В начале выполнения? В конце?)

Как выясняется, критическим моментом алгоритма для проводимого анализа является первая точка, в которой не остается ни одного короткого пути для выбора. Пусть — функция длины для текущей точки в выполнении алгоритма; мы используем для измерения длины путей в I*. Длина пути Р, будет обозначаться (Р). Путь Р*_i в оптимальном решении I* будет считаться коротким, если и длинным в противном случае. Пусть I*_s обозначает множество коротких путей в I*. Прежде всего нужно показать, что не существует коротких путей, соединяющих пары, которые не были соединены аппроксимирующим алгоритмом.

(11.17) Возьмем пару “источник-сток” i ∈ I*, не соединенную аппроксимирующим алгоритмом; то есть i ≠ I. Для нее выполняется

Доказательство. Пока выбираются короткие пути, нам не придется специально следить за тем, чтобы каждое ребро использовалось не более чем в c = 2 путям; любое ребро е, рассматриваемое для включения в третий путь, уже имеет длину l_е = β², а следовательно, является длинным.

Рассмотрим состояние алгоритма при длине . Как следует из предыдущего абзаца, можно считать, что алгоритм отработал до этой точки, не беспокоясь об ограничении с; он просто выбирал короткий путь тогда, когда мог его найти. Так как точки s_i, t_i из P*_i не соединяются жадным алгоритмом и так как при достижении функцией длины коротких путей не остается, из этого следует, что путь Р*_i имеет длину по крайней мере β² согласно . ■

При анализе случая без пересечений тот факт, что количество ребер не превышает m, использовался для ограничения количества длинных путей. На этот раз в качестве величины, потребляемой путями, будет использоваться длина вместо количества ребер. Следовательно, для дальнейших рассуждений нам понадобится граница общей длины в графе Сумма длин по всем ребрам ∑_el_e начинается с m (длина 1 для каждого ребра). Добавление короткого пути в решение I_s может увеличить длину не более чем на β³, так как длина выбранного пути не превышает β², а длины ребер увеличиваются с множителем β вдоль пути. Это дает нам полезное сравнение между количеством выбранных коротких путей и общей длиной.

(11.18) Множество I_s коротких путей, выбранных аппроксимирующим алгоритмом, и длины находятся в отношении

Итак, граница аппроксимации для этого алгоритма доказана. Оказывается, даже при простом увеличении количества путей, разрешенных для каждого ребра, с 1 до 2 гарантия аппроксимации уменьшается на значительную величину, которая, по сути, встраивает изменение в экспоненту: с O(m^1/2) до O(m^1/3).

(11.19) Алгоритм Greedy-Paths-with-Capacity c β = m^1/3 является (4m^1/3 + 1)-аппроксимирующим алгоритмом в случае пропускной способности с = 2.

Доказательство. Начнем с ограничения |I* - I|. Согласно (11.17), имеем для всех i ∈ I* - I. Суммируя по всем путям в I* - I, получаем

С другой стороны, каждое ребро в решении I* используется не более чем двумя путями, поэтому

Объединяя эти границы с (11.18), получаем

Остается разделить на β², использовать |I| ≥ 1 и присвоить β = m^1/3, и мы получаем |I*| ≤ (4m^1/3 + 1)|I|. ■

Этот алгоритм также применим к задаче о непересекающихся путях с произвольной пропускной способностью c > 0. Если выбрать β = m¹/(c + 1), то алгоритм является (2cm^1/(c+1) + 1)-аппроксимирующим. При расширении анализа пути считаются короткими, если их длина не превышает β^c.

(11.20) Алгоритм Greedy-Paths-with-Capacity с β = m^1/c+1 является (2cm^1/(c+1) + 1)-аппроксимирующим алгоритмом, если пропускные способности ребер равны c.