|
||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[153] не добавят). Поэтому в конце рассматривамого нами этапа в очереди будут все вершины, находящиеся на расстоянии $к+1$. Поскольку при добавлении они делаются серыми, а после просмотра вершина делается ч\"~~а5рной, то условие о цветах будет выполнено. Строки 14 и 15 обеспечивают выполнение пунктов леммы о расстоянии и о массиве $\pi$, что завершает доказательство. Теперь для доказательства правильности процедуры \textsc{BFS} достаточно взять большое $к$ (больше максимального расстояния от начальной вершины до всех вершин графа). Тогда вершин на расстоянии $к$ (серых, они же вершины в очереди) не будет, алгоритм завершит работу и все массивы будут заполнены правильно. Мы доказали такую теорему: Теорема 23.4 (Алгоритм \textsc{BFS} правилен) Работая на графе $G=(V,E)$ (ориентированном или неориентированном) с начальной вершиной $s$, процедура \textsc{BFS} обнаружит (сделает ч\"~~а5рными) все достижимые из $s$ вершины, и для всех $v\in V$ будет выполнено равенство $d[v]=\delta (s,v)$. Кроме того, для любой вершины $v\ne s$, достижимой из $s$, один из кратчайших путей из $s$ в $v$ можно получить добавлением ребра $(\pi [v],v)$ к (любому) кратчайшему пути из $s$ в $\pi [v]$. Для недостижимой из $s$ вершины значение $\pi[s]$ равно \textsc{nil}. У, конец доказательства Деревья поиска в ширину. В ходе работы процедуры \textsc{BFS} выделяется некоторый подграф --- дерево поиска в ширину, задаваемое полями $\pi[v]$. Более формально, применим процедуру \textsc{BFS} к графу $G=(V,E)$ с начальной вершиной $s$. Рассмотрим подграф, вершинами которого являются достижимые из $s$ вершины, а р\"~~а5брами являются р\"~~а5бра $(\pi[v],v)$ для всех достижимых $v$, кроме $s$. Лемма 23.5. Построенный таким образом подграф графа $G$ представляет собой дерево, в котором для каждой вершины $v$ имеется единственный простой путь из $s$ в $v$. Этот путь будет кратчайшим пут\"~~а5м из $s$ в $v$ в графе $G$. Доказательство. Существование пути из $s$ в $v$ (как и то, что он будет кратчайшим) следует из теоремы 23.4 (индукция по расстоянию от $s$ до $v$). Поэтому граф связен. Поскольку число р\"~~а5бер в н\"~~а5м на единицу меньше числа вершин, то он является деревом (теорема 5.2). У, конец доказательства Это дерево называется \етрп{подграфом предшествования} (predecessor subgraph), а также \етрЬ{деревом поиска в ширину} (breadth-first tree) для данного графа и данной начальной вершины. (Заметим, что построенное дерево зависит от того, в каком порядке просматриваются вершины в списках смежных вершин Если значения в массиве $\pi$ уже вычислены с помощью процедуры \textsc{BFS}, то крайтчайшие пути из $s$ легко найти их печатает процедура \textsc{Print-Path} \begin{verbatim} Print-Path$(G,s,v)$ 1if $v=s$ 2then напечатать $s$ 3else if $\pi[v]=NIL$ 4then напечатать "пути из $s$ в $v$ нет" 5else Print-Path$(G,s,\pi[v])$ 6напечатать $v$ Время выполнения пропорционально длине печатаемого пути (каждый рекурсивный вызов уменьшает расстояние от s на единицу). Упражнения 23.2-1 Что даст поиск в ширину для ориентированного графа рис. 23.2 (а) и вершины 3 в качестве начальной? 23.2-2 Что даст поиск в ширину для неориентированного графа рис. 23.3 и вершины и в качестве начальной? 23.2-3 Сколько времени будет работать процедура BFS, если граф представлен в виде матрицы смежности (и процедура соответственно изменена)? 23.2-4 Покажите, что при поиске в ширину значение d[u], даваемое алгоритмом, не изменится, если переставить элементы в каждом списке смежных вершин. 23.2-5 Приведите пример ориентированного графа G = (V,E), начальной вершины s £ V и некоторого множества ребер Ev С Е, для которых для каждой достижимой из s вершины v £ V существует единственный путь из s в v, проходящий по рёбрам из Ev, и этот путь является кратчайшим в G, но множество ребер Ev не совпадает с деревом поиска в ширину, даваемым с помощью процедуры BFS, как ни переставляй элементы в каждом из списков смежных вершин. 23.2-6 Придумайте эффективный алгоритм, выясняющий, является ли данный неориентированный граф двудольным. 23.2-7* Диаметр (diameter) дерева Г = (V, Е) определяется как max 5(и, v) u,v(zV (то есть как максимальная длина кратчайшего пути между двумя вершинами). Придумайте эффективный алгоритм вычисления диаметра дерева, и оцените время его работы. 23.2-8 Пусть G = (V, Е) - неориентированный граф. Придумайте алгоритм, отыскивающий за время 0(V + Е) путь в графе, который проходит каждое ребро ровно по одному разу в каждую сторону. Как найти выход из лабиринта, имея с собой большой запас одинаковых монет? 23.1.3. Поиск в глубину Стратегия поиска в глубину такова: идти «вглубь», пока это возможно (есть непройденные рёбра), и возвращаться и искать другой путь, когда таких рёбер нет. Так делается, пока не обнаружены все вершины, достижимые из исходной. Если после этого остаются необнаруженные вершины, можно выбрать одну из них и повторять процесс, и делать так до тех пор, пока мы не обнаружим все вершины графа. Как и при поиске в ширину, обнаружив (впервые) вершину v, смежную с и, мы отмечаем это событие, помещая в поле ir[v] значение и. Получается дерево - или несколько деревьев, если по- |
Среды: 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 | ||