|
||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[159] фа G = (V, Е) называется цикл, проходящий по каждому ребру G ровно один раз (в одной и той же вершине можно бывать многократно). a.Покажите, что в G есть эйлеров цикл тогда и только тогда, когда входящая степень каждой вершины равна ее исходящей степени. b.Придумайте алгоритм, который за время О(Е) находит в графе эйлеров цикл (если таковой имеется). (Указание: объединяйте циклы, у которых нет общих рёбер.) Замечания Прекрасные руководства по алгоритмам на графах написали Ивен [65] и Тарьян [188]. Поиск в ширину рассмотрел Мур [150] при изучении путей в лабиринтах. Ли [134] независимо открыл тот же алгоритм применительно к соединениям контактов в электронных схемах. Хопкрофт и Тарьян [102] указали на пользу представления в виде списков смежных вершин для редких графов и обнаружили важность поиска в глубину для построения алгоритмов на графах. Сам по себе поиск в глубину начал использоваться незадолго до 1960 года, в превую очередь в программах, связанных с «искусственным интеллектом». Тарьян [185] придумал алгоритм поиска сильно связных компонент за линейное время. Алгоритм раздела 23.5 взят из книги Ахо, Хопкрофта и Ульмана [5], которые ссылаются на Косараю (S.R. Kosaraju) и Шарира (М. Sharir). Кнут [121] первым построил алгоритм тополигической сортировки за линейное время. Минимальные покрывающие деревья Пусть даны п контактов на печатной плате, которые мы хотим электрически соединить. Для этого достаточно использовать п-1 проводов, каждый из которых соединяет два контакта. При этом мы обычно стремимся сделать суммарную длину проводов как можно меньше. Упрощая ситуацию, можно сформулировать задачу так. Пусть имеется связный неориентированный граф G = (V,E), в котором V - множество контактов, а Е - множество их возможных попарных соединений. Для каждоого ребра графа (и, v) задан вес w(u, v) (длина провода, необходимого для соединения и и v). Задача состоит в нахождении подмножества Т С Е, связывающего все вершины, для которого суммарный вес w(T) =w(u,v) (u,v)eT минимален. Такое подмножество Г будет деревом (поскольку не имеет циклов: в любом цикле один из проводов можно удалить, не нарушая связности). Связный подграф графа G, являющийся деревом и содержащий все его вершины, называют покрывающим деревом (spanning tree) этого графа. (Иногда используют термин «остовное дерево»; для краткости мы будем говорить просто «остов». ) В этой главе мы рассматриваем задачу о минимальном покрывающем дереве (minimum-spanning-tree problem). (Здесь слово «минимальное» означает «имеющее минимально возможный вес».) На рисунке 24.1 приведён пример связного графа и его минимального остова. [Возвращаясь к примеру с проводниками на печатной плате, объясним, почему задача о минимальном дереве является упрощением реальной ситуации. В самом деле, если соединяемые контакты находятся в вершинах единичного квадрата, разрешается соединять его любые вершины и вес соединения равен его длине, то минимальное покрывающее дерево будет состоять из трёх сторон квадрата. Между тем все его четыре вершины можно электрически Рис. 24.1 24.1 Минимальное покрывающее дерево. На каждом ребре графа указан вес. Выделены ребра минимального покрывающего дерева (суммарный вес 37). Такое дерево не единственно: заменяя ребро (Ь, с) ребром (a,h), получаем другое дерево того же веса 37. соединить двумя пересекающимися диагоналями (суммарная длина 2 у/2 < 3) и даже ещё короче (введя две промежуточные точки, в которых проводники сходятся под углом 120°.).] В этой главе мы рассмотрим два способа решения задачи о минимальном покрывающем дереве: алгоритмы Крускала и Прима. Каждый их них легко реализовать с временем работы O(ElgV), используя обычные двоичные кучи. Применив фибоначчиевы кучи, можно сократить время работы алгоритма Прима до 0(E-\-V\gV) (что меньше E-\-\gV, если \V\ много меньше \Е\). Оба алгоритма (Крускала и Прима) следуют «жадной» стратегии: на каждом шаге выбирается «локально наилучший» вариант. Не для всех задач такой выбор приведёт к оптимальному решению, но для задачи о покрывающем дереве это так. (Мы обсуждали это в главе 17; задача о покрывающем дереве является превосходной иллюстрацией введённых там понятий.) В разделе 24.1 описана общая схема алгоритма построения минимального остова (добавление рёбер одного за другим). В разделе 24.2 указаны две конкретных реализации общей схемы. Первый алгоритм, восходящий к Крускалу, аналогичен алгоритму поиска связных компонент из раздела 22.1. Другой (алгоритм Прима) аналогичен алгоритму Дейкстры поиска кратчайших путей (раздел 25.2). 24.1. Построение минимального остова Итак, пусть дан связный неориентированный графа G = (V, Е) и весовая функцией w : Е -> Ж. Мы хотим найти минимальное покрывающее дерево (остов), следуя жадной стратегии. Общая схема всех наших алгоритмов будет такова. Искомый остов строится постепенно: к изначально пустому множеству А на каждом шаге добавляется одно ребро. Множество А всегда является подмножеством некоторого минимального остова. Ребро (и, v), добавляемое на очередном шаге, выбирается так, чтобы не нарушить этого свойства: Аи{(и, v)} тоже должно быть подмножеством минимального остова. Мы называем такое ребро безопасным ребром (safe edge) для А. \textsc{Generic-MST> $(G,w)$ 1$А \leftarrow \emptyset$ 2{\bf while} $A$ не является остовом |
Среды: 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 | ||