|
||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[113] ны. В самом деле, пусть А и В - ацикличные подграфы G, причём \В\ > А. Из теоремы 5.2 следует, что лес с к рёбрами является несвязным объединением \V\ - к деревьев, где \V\ - количество вершин (независимое доказательство: начнём с леса, состоящего из \V\ вершин и не имеющего ребер, и будем по одному добавлять рёбра, не нарушая ацикличности; тогда добавление каждого ребра уменьшает количество связных компонент на единицу). Следовательно, лес А состоит из \V\ - \А\ деревьев, а лес В - из \V\ - \В\ деревьев. Поскольку \V\ - \В\ < \V\ - \А\, лес В содержит такое дерево Г, что две его вершины принадлежат разным связным компонентам леса А. Более того, поскольку Г связно, оно должно содержать такое ребро (и, v), что и и v принадлежат разным связным компонентам леса А. Следовательно, добавление этого ребра к лесу А не может создать цикла, и его можно взять в качестве элемента ж из определения матроида.□ (Графовые матроиды являются частным случаем матричных, если ребро графа рассматривать как формальную сумму его вершин с коэффициентами в поле вычетов по модулю 2, см. задачу 17-26.) Если М = (S,I) - матроид, то элемент х А £ X называется независимым от A (extension of А), если множество A U {ж} независимо. Например, в графовом матроиде ребро е независимо от леса А тогда и только тогда, когда его добавление к А не создаёт цикла. Независимое подмножество в матроиде называется максимальным (maximal), если оно не содержится ни в каком большем независимом подмножестве. Часто бывает полезна следующая Теорема 17.6. Все максимальные независимые подмножества данного матроида состоят из одинакового числа элементов. Доказательство. Пусть А и В - максимальные независимые подмножества. Если, скажем, А < \В\, то из свойства замены вытекает существование такого ж А, что A U {ж} независимо - в противоречие с максимальностью.□ В качестве примера рассмотрим графовый матроид Mq, соответствующий связному графу G. Всякое максимальное независимое подмножество Mq должно быть деревом с \V\ - 1 ребром, соединяющим все вершины G. Такое дерево называется покрывающим (остовным) деревом графа G (по-английски spanning tree). Будем называть матроид М = (S,I) взвешенным (weighted), если на множестве S задана весовая функция w со значениями во множестве положительных чисел. Функция w распространяется по аддитивности на все подмножества множества S; вес подмножества определяется как сумма весов его элементов: w(A) = 2xew(x). Пример: если Mq - графовый матроид, a w(e) - длина ребра е, то w(A) - сумма длин рёбер подграфа А. 17.4.2. Жадные алгоритмы для взвешенного матроида Многие оптимизационные задачи, решаемые жадными алгоритмами, сводятся к задаче о нахождении в данном взвешенном матроиде М = (S,I) независимого подмножества А С М максимального веса. Независимое подмножество максимального веса называется оптимальным (optimal) подмножеством взвешенного матроида. Поскольку веса всех элементов положительны, оптимальное подмножество автоматически будет максимальным независимым подмножеством. Например, задача о наименьшем покрывающем дереве (minimum-spanning-tree problem) состоит в следующем. Дан связный неориентированный граф G = (V, Е) и функция w из множества его рёбер во множество положительных чисел (w(e) будем называть длиной ребра е). Требуется найти множество рёбер, соединяющих все вершины и имеющих наименьшую суммарную длину. Эту задачу можно рассматривать как частный случай задачи об оптимальном подмножестве взвешенного матроида. В самом деле, выберем число wo, строго большее длин всех рёбер, и введем на графовом матроиде Mq веса по правилу w(e) = wq - w(e). Для всякого максимального независимого подмножества (т.е. покрывающего дерева) А имеем w(A) = (\V\ - l)w0-w(A), где V - множество вершин графа. Стало быть, наименьшие покрывающие деревья для графа G - то же самое, что оптимальные подмножества в матроиде Mq с весовой функцией w. Задача о наименьшем покрывающем дереве подробно рассматривается в главе 24; сейчас мы приведём жадный алгоритм, находящий оптимальное подмножество А в любом взвешенном матроиде М. Если М = (S,l), то мы пишем S = S[M] и I = 1[М]; весовая функция обозначается w. Greedy (М, w) 1А([) 2отсортировать S[M] в порядке невозрастания весов 3for х G S[M] (перебираем все х в указанном порядке) 4do if AU {ж} G 1[М] 5then А <- All {ж} 6return А Алгоритм работает следующим образом. Полагаем А = 0 (строка 1; пустое множество, как мы помним, всегда независимо) и перебираем элементы S[M] в порядке убывания веса; если очередной элемент можно, не нарушая независимости, добавить к множеству А, то мы это делаем. Ясно, что полученное в результате множество будет независимым. Ниже мы покажем, что оно действительно будет иметь максимальный вес среди независимых подмножеств, а пока что оценим время работы алгоритма Greedy. Сортировка (строка 2) занимает время O(ralogra), где п = \S\. Проверка независимости множества (строка 4) проводится п раз; если каждая такая проверка занимает время f(n), то общее время работы будет 0(n\ogn + nf(n)). Теперь покажем, что алгоритм Greedy действительно даёт оптимальное подмножество. Лемма 17.7 (свойство жадного выбора для матроидов). Пусть М = (S,I) - взвешенный матроид с весовой функцией w. Пусть ж £ S - элемент наибольшего веса во множестве {у £ S : {у} независимо}. Тогда х содержится в некотором оптимальном подмножестве ACS. Доказательство. Пусть В - какое-то оптимальное подмножество. Будем считать, что х В, иначе доказывать нечего. Положим А = {ж}. Это множество независимо по выбору ж. Применяя \В\ - 1 раз свойство замены, мы расширяем А элементами из В и в конце концов построим независимое множество А, состоящее из ж и \В\ - 1 элемента множества В. Имеем А = \В\ (так что А максимально) и w(A) = w(B) - w(y) + w(x), где у - единственный элемент В, не входящий в А. В то же время для всякого у £ В множество {у} независимо в силу свойства наследственности, так что w(x) w(y) по выбору ж. Стало быть, w(A) w(B), и множество А также оптимально. Всё доказано.□ Далее, имеет место следующая очевидная Лемма 17.8. Если М = (S,I) - матроид, ж £ S и {ж} 1, то A U {ж} 1 для всех ACS. Наша последняя лемма такова: Лемма 17.9 (свойство оптимальности подзадач для матроидов). Пусть М = (S,T) - взвешенный матроид, и пусть ж £ S - некоторый его элемент, причём множество {ж} независимо. Тогда независимое множество наибольшего веса, содержащее х, является объединением {ж} и независимого множества наибольшего веса в матроиде М = (S,11), где, по определению, s = {yeS:{x,y}ei}, 1 = { В С S \ {ж} : В U {ж} £ 1} , а весовая функция является ограничением на S весовой функции для матроида М (в таких случаях говорят, что матроид М получен из М стягиванием (contraction) элемента ж). |
Среды: 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 | ||