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

Начнем с построения потоковой сети, предоставляющей эффективный алгоритм для проверки факта выбывания команды z. Затем, анализируя минимальный раз- рез в сети, мы докажем (7.59).

Очевидно, если для команды z существует вариант, приводящий ее к первому месту, следует рассмотреть вариант, в котором z выигрывает все оставшиеся игры.

Допустим, при этом команда выходит с m победами. Теперь нужно тщательно распределить победы во всех остальных играх, чтобы ни одна команда не набрала более m побед. Такое распределение может быть получено посредством вычисления максимального потока на базе следующей идеи: имеется источник s, который гене- рирует все победы. Победа i может пройти через одну из двух команд, участвующих в i-й игре. Затем устанавливается ограничение пропускной способности, которое говорит, что через команду х могут проходить не более m - wx.

Конкретнее строится потоковая сеть G, изображенная на рис. 7.21. Пусть S* — S — |г| и g* =∑,x уеs'З*у ~ °бщee количество игр, оставшихся между всеми

парами команд в S'. В сеть включаются узлы s и t, узел vx для каждой команды х ^ S', и узел и для каждой пары команд x,y ^ S' с ненулевым количеством игр, ко- торые им осталось сыграть друг с другом. Ребра делятся на следующие категории:

♦ ребра (5, uxy) (победы выходят из 5);

♦ ребра (uxy, vx) и (uxy, vy) (только x или y может победить в игре, в которой они играют друг с другом);

♦ ребра (vx, t) (победы поглощаются в t).

Какие же пропускные способности следует назначить этим ребрам? От 5 к uxy должны передаваться gxy побед с насыщением, поэтому ребру (5, uxy) назначается пропускная способность gxy.

Команда x не должна выиграть более m-wx игр, поэтому ребру (vx, t) назначается пропускная способность m-wx. Наконец, ребро в форме (u, vy) должно иметь как минимум gxy единиц пропускной способности, чтобы оно могло передать все победы от uy к vx; на самом деле самое «чистое» решение — на- значить ребру бесконечную пропускную способность. (Построение будет работать даже в том случае, если ребру назначить только gxy единиц пропускной способно- сти, но доказательство (7.59) при этом усложнится.)

Рис. 7.21. Множество Т={Нью-Йорк, Торонто} доказывает, что Балтимор выбывает


Если существует поток с величиной g”, то результаты всех оставшихся игр могут создать ситуацию, при которой ни одна команда не имеет более m побед; а следовательно, если команда z выиграет все свои оставшиеся игры, она все равно может добиться хотя бы ничьей за первое место. И наоборот, если для оставшихся игр существуют результаты, с которыми z получает по крайней мере ничью, эти результаты могут использоваться для определения потока с величиной g*. Напри- мер, на рис. 7.21, основанном на втором примере, обозначенный разрез показывает, что максимальный поток имеет величину не более 7, тогда как g* = 6 + 1 + 1 = 8.

Итак, мы показали следующий результат:

(7.60) Команда z выбывает из борьбы за первое место в том и только в том слу- чае, если величина максимального потока в G строго меньше g*. Следовательно, проверка выбывания z может быть выполнена за полиномиальное время.

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Разработка и анализ алгоритма:

  1. Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science, 2016
  2. § 2. АЛГОРИТМ АНАЛИЗА ПСИХОЛОГО-ПЕДАГОГИЧЕСКИХ СИТУАЦИЙ
  3. § 2.ФУНКЦИИ МЕТОДОЛОГИИ В РАЗРАБОТКЕ МЕТОДИК АНАЛИЗА СОЦИАЛЬНЫХ ФАКТОВ
  4. Sшrvig Morten. Базовые алгоритмы Qt 4 (Qt 4's Generic Algorithms), 2000
  5. АЛГОРИТМ
  6. АЛГОРИТМ УДАЧИ
  7. Алгоритм исцеления:
  8. Алгоритм избавления от боли
  9. 2. Специфика и алгоритмы работы с источниками.
  10. Алгоритм обработки результатов.