Проблемы, связанные с алгоритмом сетевого потока - PullRequest
0 голосов
/ 26 ноября 2018

Я пытаюсь решить вопрос ниже от tardos.Будем благодарны за любые предложения или помощь.

Вы были вызваны, чтобы помочь некоторым сетевым администраторам диагностировать степень сбоя в их сети.Сеть предназначена для передачи трафика от назначенного исходного узла s к назначенному целевому узлу t, поэтому мы будем моделировать его как ориентированный граф G = (V, E), в котором емкость каждого ребра равна 1, и в которомкаждый узел лежит хотя бы на одном пути от s до t.

Теперь, когда в сети все работает гладко, максимальный st-поток в G имеет значение k.Однако текущая ситуация - и причина, по которой вы здесь - состоит в том, что злоумышленник уничтожил некоторые ребра в сети, так что теперь нет пути от s до t с использованием оставшихся (выживших) ребер.По причинам, которые мы не будем здесь вдаваться, они считают, что атакующий уничтожил только k ребер, минимальное количество, необходимое для отделения s от t (т. Е. Размер минимального st-разреза);и мы будем считать, что они верят в это.Сетевые администраторы запускают пул мониторинга на узле s, который имеет следующее поведение: если вы введете команду ping (v) для данного узла v, он сообщит вам, существует ли в настоящее время путь от s до v. (Таким образом, pint (t) сообщает, что в настоящее время пути не существует, с другой стороны, ping (s) всегда сообщает путь от s к себе.) Поскольку не практично выходить на улицу и проверять каждый край сети, они хотели быопределить степень сбоя с помощью этого инструмента мониторинга с помощью разумного использования команды ping.Итак, вот проблема, с которой вы столкнулись: дать алгоритм, который выдает последовательность команд ping различным узлам в сети, а затем сообщает полный набор узлов, которые в настоящее время недоступны из s.Конечно, вы могли бы сделать это, пропингуя каждый узел в сети, но вы хотели бы сделать это, используя намного меньше пингов (учитывая предположение, что были удалены только k ребер).Выпуская эту последовательность, ваш алгоритм может решить, какой узел пинговать дальше, на основе результатов предыдущих операций пинга.Приведите алгоритм, который выполняет эту задачу, используя только O (k log n) пингов.

1 Ответ

0 голосов
/ 26 ноября 2018

Используйте Floyd-Fulkerson для всей сети, чтобы вычислить максимальный поток, который будет состоять из k непересекающихся с ребром путей.

Поскольку ровно k ребер было удалено, а весь поток отрезан, ровно одинКрай должен быть удален вдоль каждого из этих путей.

Для каждого пути, который будет содержать не более n ребер, выполните бинарный поиск, чтобы определить положение сломанного ребра, используя O (log n) ping дляузлы на пути.

...