|
||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[193] Рис. 27.10 27.12 Задача о выходе. Начальные точки чёрные, остальные - белые, (а) Выход есть (выделены пути, его обеспечивающие). (Ь) Выхода нет. Задачи 27-1 Задача о выходе Имеется, граф вершины которого образуют решётку из га строк и га столбцов (рис. 27.12). Обозначим черезвершину на пере- сечении г-го столбца и j-ой строки. Все вершины такой решётки (га X га grid), не считая граничных [г = 1, г = га, j = 1 или j = га) имеют четырёх соседей. В задаче о выходе (escape problem) требуется выяснить, существуют ли т попарно непересекающихся (не имеющих общих вершин) путей от данных т га2 начальных точек решётки (х\, у\), (х2, у2),..., (хт, ут) к т различным граничным точкам. Например, для задачи о выходе рис. 27.12(a) ответ положителен, а для рис. 27.12 (Ь) - отрицателен. (a)Рассмотрим сеть, в которой пропускные способности имеют не только рёбра, но и вершины. Это означает, что поток, входящий в данную вершину, не может превосходить некоторого числа (пропускной способности вершины). Покажите, что задача о максимальном потоке в такой сети сводится к обычной задаче о максимальном потоке для сети несколько большего размера. (b)Укажите алгоритм, решающий задачу о выходе. Чему равно время его работы? 27-2 Минимальное покрытие путями Покрытием путями (path cover) ориентированного графа G = (V, Е) назовём множество путей Р с таким свойством: каждая вершина из V принадлежит ровно одному пути из Р. Пути могут начинаться и заканчиваться где угодно, и иметь любую длину, в том числе нулевую. Покрытие наименьшим возможным числом путей назовём минимальным покрытием путями (minimum path cover). (a)Постройте эффективный алгоритм, находящий минимальное покрытие путями графа G = (V,E). (Указание. Пусть V = {1, 2,..., га}. Построим граф G = (V, Е), где V = {х0, xi,..., хп} U {у0, у!,..., уп}, Е= {{x0,xl)\iev}\j{{yl,y0)\i е V}u{(Xl,yj}\(i,j) е Е}, и решим для этого графа задачу о максимальном потоке.) (b)Правильно ли работает этот алгоритм, если у графа есть циклы? Ответ объясните. 27-3 Эксперименты в космосе Институт космических исследований планирует серию Е = {Е\, Е2, , Ет} экспериментов в космосе. За результат эксперимента Е{ спонсоры выплачивают рг- долларов. Для этих экспериментов требуются приборы из множества / = {1\, 12, , 1п}] Для проведения эксперимента Ej необходимо множество Rj С / прибо- ров. Стоимость доставки прибора 1к составляет ск долларов. Требуется выяснить, какие эксперименты следует проводить, чтобы прибыль (доход от экспериментов минус стоимость доставки нужных приборов) была максимальной. Для решения этой задачи рассмотрим сеть G с истоком s, стоком t, вершинами 1\, 12, , 1п и Е\, Е2, , Ет. Сеть имеет также рёбра (s, 1) пропускной способности Ck (для всех к = 1,2,... , га); (Ej, t) пропускной способности pj] (для всех j = 1, 2,... , то); (Ik, Ej) бесконечной пропускной способности, если 1к £ Ej (для к = 1, 2,... , га и j = 1,2,... ,то). (a)Рассмотрим разрез (S, Т) с конечной пропускной способностью для построенной сети. Пусть Ej £ Т. Покажите, что 1к £ Т для всех Ik £ Rj. (b)Как, зная все pj и пропускную способность минимального разреза сети G, найти максимальную прибыль от экспериментов? (c)Постройте алгоритм, определяющий, какие эксперименты следует проводить [для получения наибольшей прибыли] и какие для этого нужны приборы. Оцените время его работы как функ- 27-4 Максимальный поток в изменённой сети Предположим, нам известен максимальный поток в сети G = (V,E), в которой все пропускные способности рёбер - целые числа. (a)Пусть пропускная способность некоторого ребра (и,v) £ Е увеличилась на единицу. Приведите алгоритм, находящий максимальный поток (для изменённой сети) за время 0(V + Е). (b)Пусть пропускная способность некоторого ребра (и,v) £ Е уменьшилась на единицу. Приведите алгоритм, находящий максимальный поток (для изменённой сети) за время 0(V + Е). 27-5 Масштабирование Рассмотрим сеть G = (V, Е) с истоком s и стоком t. Пусть пропускная способность с(и, v) любого ребра (и, v) £ Е - целое число. Положим С = max с(и, v). (a)Докажите, что пропускная способность минимального разреза сети G не превосходит С£. (b)Докажите, что при любом заданном К можно за время 0(E) найти дополняющий путь с пропускной способностью не меньше К или установить, что такого пути нет. Алгоритм Max-Flow-By-Scaling вычисляет максимальный поток в сети G с помощью масштабирования. Это одна из реализаций метода Форда-Фалкерсона. \textsc{Max-Flow-By-Scaling}($G,s,t$) 1$C\leftarrow\max\limits {(u,v)\in E}{c(u,v)}$ 2сделать поток $f$ нулевым m цию от то, га и г = 2 \Rj 3 = 1 (u,v)eE 3$K\leftarrow 2~{\lfloor\log C\rfloor>$ 4while $K\ge 1$ 5do while существует дополняющий путь $p$ пропускной способности не менз 6do дополнить $f$ вдоль $р$ 7$K\leftarrow К/2$ 8return $f$ (c)Докажите, что программа Max-Flow-By-Scaling вычисляет максимальный поток. (d)Докажите, что в момент проверки условия цикла в строке 4 пропускная способность минимального разреза остаточной сети не превосходит 2К\Е\. (e)Докажите, что цикл в строках 5-6 выполняется О(Е) раз для любого значения К. (f)Докажите, что время работы алгоритма Max-Flow-By-Scaling равно О(Е2 log С). 27-6 Двусторонние границы Рассмотрим сеть G = (V,E). Предположим, что ограничения на поток в этой сети двусторонние. Именно, для потока / и для каждого ребра (и, v) мы требуем, чтобы b(u, v) f(u, v) с(и, v), где с и Ь - заданные функции на рёбрах. (Возможно, что эти ограничения противоречивы - тогда потока не существует.) (a)Пусть / - поток в сети G. Докажите, что / c(S,T) - b(T,S) для любого разреза (S,T). (b)Пусть в сети G максимальный поток существует. Докажите, что его значение равно минимальной (по всем разрезам (S,T)) разности c(S, Т) - b(T, S). Рассмотрим сеть G = (V, Е) с двусторонними границами с истоком s и стоком t. Обозначим верхнюю и нижнюю границы cub соответственно. Построим обычную сеть G = (V, Е) с верхней границей (пропускной способностью) с, истоком s и стоком t, положив V = V U {s,t} Е = Е U {(s, v)\v £ V} U {(и, t)\u £ V} U {(s, t), (t, s)}. Для рёбер (u,v) G E положим c(u,v) = c(u,v) - b(u,v); для всех вершин и G V положим c(s,u) = b(V,u), а также c(u,t) = b(u,V). Кроме того, положим c(s,t) = c(t,s) = оо. (c)Докажите, что поток в сети G существует тогда и только тогда, когда для максимального потока в сети G все рёбра, входящие в t, насыщены. (d)Постройте алгоритм, который выясняет, существует ли поток в данной сети с двусторонними границами, и если да, то находит этот поток. Оцените время работы этого алгоритма. Замечания |
Среды: Smalltalk80 MicroCap Local bus Bios Pci 12С ML Микроконтроллеры: Atmel Intel Holtek AVR MSP430 Microchip Книги: Емкостный датчик 500 схем для радиолюбителей часть 2 (4) Структура компьютерных программ Автоматическая коммутация Кондиционирование и вентиляция Ошибки при монтаже Схемы звуковоспроизведения Дроссели для питания Блоки питания Детекторы перемещения Теория электропривода Адаптивное управление Измерение параметров Печатная плата pcad pcb Физика цвета Управлении софтверными проектами Математический аппарат Битовые строки Микроконтроллер nios Команды управления выполнением программы Перехода от ahdl к vhdl Холодный спай Усилители hi-fi Электронные часы Сердечники из распылённого железа Анализ алгоритмов 8-разрядные КМОП Классификация МПК История Устройства автоматики Системы и сети Частотность Справочник микросхем Вторичного электропитания Типы видеомониторов Радиобиблиотека Электронные системы Бесконтекстный язык Управление техническими системами Монтаж печатных плат Работа с коммуникациями Создание библиотечного компонента Нейрокомпьютерная техника Parser Пи-регулятор ч.1 ПИ-регулятор ч.2 Обработка списков Интегральные схемы Шина ISAВ Шина PCI Прикладная криптография Нетематическое: Взрывной автогидролиз Нечеткая логика Бытовые установки (укр) Автоматизация проектирования Сбор и защита Дискретная математика Kb радиостанция Энергетика Ретро: Прием в автомобиле Управление шаговым двигателем Магнитная запись Ремонт микроволновки Дискретные системы часть 2 | ||