Методы решения оптимизационных задач

Содержание

Слайд 2

Введение Примеры дискретных оптимизационных задач задача о кратчайшем пути: Пусть имеется

Введение

Примеры дискретных оптимизационных задач
задача о кратчайшем пути: Пусть имеется

несколько городов и известны попарные расстояния между соседними городами. При этом два города считаются соседними, если есть дорога, их соединяющая, и не проходящая через какой-либо другой город. Требуется найти кратчайший путь между некоторой парой городов;
задача оптимального назначения:
Пусть имеется n станков и n деталей, каждую деталь можно обрабатывать на любом станке, но время обработки детали на одном станке может отличаться от времени ее обработки на другом. Пусть эти времена для каждой пары «станок — деталь» заданы. Требуется так организовать производство деталей, т.е. разместить их по станкам, чтобы суммарное время работы было наименьшим ;
задача коммивояжера
Путешественник хочет объехать n городов, побывав в каждом ровно по одному разу, и вернуться в исходный, затратив при этом минимальную сумму на поездку. Затраты па поездку складываются из затрат на переезды между парами городов, а эти затраты заранее известны.
Слайд 3

В каждой задаче имеется лишь конечное число вариантов, из которых требуется

В каждой задаче имеется лишь конечное число вариантов, из которых требуется

осуществить выбор (путей между городами, способов распределения деталей по станкам, маршрутов передвижения путешественника).
Каждому варианту выбора сопоставлена некоторая числовая характеристика (длина пути, суммарное время работы, стоимость поездки).
Требуется выбрать вариант, числовая характеристика которого достигает экстремума.
Методы решения подобных задач
полный перебор (поочередно пересмотреть все варианты и выбрать требуемый);
дискретная оптимизация.

Общие свойства дискретных оптимизационных задач

Слайд 4

Типы задач: массовые и индивидуальные задачи. Все вышеприведенные примеры дают образцы

Типы задач: массовые и индивидуальные задачи.
Все вышеприведенные примеры дают образцы

именно массовых задач.
Индивидуальная задача получается из массовой путем фиксации набора условий.
Например, индивидуальная задача коммивояжера получается из массовой, если зафиксировано число городов и определены затраты на переезды между всеми парами городов.
С каждой конкретной массовой задачей (в дальнейшем просто задачей) будем связывать некоторое число (или несколько чисел), называемое ее размером, которое выражает меру количества входных данных. Например, размером задачи коммивояжера естественно считать число городов n, которые собирается посетить путешественник.

Алгоритмы и их сложности

Слайд 5

Говорят, что алгоритм решает некоторую массовую задачу, если он решает любую

Говорят, что алгоритм решает некоторую массовую задачу, если он решает любую

ее индивидуальную задачу.
Для оценки качества алгоритмов имеется ряд критериев.
Одним из важнейших таких критериев является понятие вычислительной сложности (или просто сложности) алгоритма.
Неформально, под сложностью алгоритма решения массовой задачи будем понимать максимально возможное число шагов, выполняемых алгоритмом для решения любой из индивидуальных задач, вычисленное как функция размерности задачи.
Под шагом алгоритма будем понимать выполнение "простой" операции, обычно аппаратно реализованной на любой ЭВМ, а именно любой арифметической операции, операции сравнения, пересылки, косвенной адресации и т.п.
При этом будем рассматривать асимптотическую сложность алгоритма, (а не точную сложность, зависящую от конкретного вида машинных команд), т.е. порядок роста числа шагов алгоритма при неограниченном росте размерности задачи.
При сравнении скорости роста двух неотрицательных функций f(n) и g(n) будем использовать следующие понятия.

Алгоритмы и их сложности

Слайд 6

При сравнении скорости роста двух неотрицательных функций f(n) и g(n) будем

При сравнении скорости роста двух неотрицательных функций f(n) и g(n) будем

использовать следующие понятия.
Будем говорить, что функция f(n) имеет порядок роста
не более чем g(n) (запись: f(n) = О(g(n))),
если существуют константы с, N > 0 такие,
что f(n) < c·g(n) для всех n > N.
Говорят, что функция f(n) имеет порядок роста
не менее чем g(n) (запись: f(n) = Ω (g(n)) ),
если существуют константы с, N > 0 такие,
что f(n) ≥ c g(n) для всех n > N.

Алгоритмы и их сложности

Слайд 7

Например, справедливы следующие соотношения: log2n = О(n); n2 = О(2n); n

Например, справедливы следующие соотношения:
log2n = О(n); n2 = О(2n); n

= Ω (log2n):
На практике алгоритм решения некоторой задачи считается достаточно хорошим, если сложность этого алгоритма есть O(n·p) при некотором р > 0.
В этом случае говорят, что задача полиномиально разрешима,
или, что то же самое, задача может быть решена за полиномиальное время.
Важность понятия сложности алгоритма хорошо иллюстрируют следующие таблицы.

Алгоритмы и их сложности

Слайд 8

Алгоритмы и их сложности Таблица 1.2. Влияние технического совершенствования ЭВМ на

Алгоритмы и их сложности

Таблица 1.2. Влияние технического совершенствования ЭВМ на полиномиальные

и экспоненциальные алгоритмы

Таблица 1.1. Максимальная размерность задач, разрешимых за данное время

Слайд 9

Пусть для решения некоторой задачи имеется алгоритм сложности n3. Тогда, как

Пусть для решения некоторой задачи имеется алгоритм сложности n3. Тогда, как

это следует из таблицы 1.2, десятикратное увеличение скорости быстродействия ЭВМ позволит увеличить размер задачи, решаемой за 1 минуту в 2,15 раз. Однако замена этого алгоритма другим, имеющим сложность n2, позволит решать задачу в 6 раз большего размера (см. таблицу 1.1). Если в качестве единицы взять 1 час, то сравнение будет еще более впечатляющим.

Алгоритмы и их сложности

Слайд 10

Алгоритмы будем записывать на некотором специальном языке, который назовем упрощенным Паскалем.

Алгоритмы будем записывать на некотором специальном языке, который назовем упрощенным Паскалем.

В этом языке возможно использование любого типа данных: тип данных какой-либо переменной и ее область действия должны быть ясны либо по ее названию, либо по контексту.
В упрощенном Паскале применяются традиционные конструкции математики и языков программирования такие, как выражения, условия, операторы и процедуры. Операторы языка Паскаль используются, как правило, в соответствии с правилами языка Паскаль, но иногда будут применяться неформальные конструкции такие, как, например,
1) циклы for х ϵ X do Р, т.е. выполнять оператор Р для всех элементов х множества X в произвольной последовательности;
2) x[i] ↔ x[j] — переставить i-ый и j-ый элементы массива; или описание типа: "пусть х — наименьший элемент множества X".
3) Будем также предполагать, что все операторы, записанные в одной строке алгоритма, образуют один составной оператор. Поэтому ключевые слова begin и end, идентифицирующие этот оператор, будут опускаться.

Запись алгоритмов

Слайд 11

АЛГОРИТМ 1.1. ВЫБОР МИНИМАЛЬНОГО ЭЛЕМЕНТА Данные: числовое множество X. Результат: число

АЛГОРИТМ 1.1. ВЫБОР МИНИМАЛЬНОГО ЭЛЕМЕНТА
Данные: числовое множество X.
Результат: число minX -

минимальный элемент X
begin
minX := +∞;
for х ϵ X do
if x < minX then minX := x;
end.
Поясним на этом примере понятие сложности алгоритма.
Размером этой задачи естественно считать n — количество элементов во множестве X.
Цикл в строках 3-4 работает ровно n раз. В строке 4 при каждом шаге цикла осуществляется одна операция сравнения и, в худшем случае, одна операция присваивания.
Таким образом, в строках 3 и 4 проводится не более чем 2n операций. С учетом оператора присваивания в строке 2 получаем, что число шагов алгоритма не превосходит 2n+1. Значит сложность этого алгоритма есть О(n).
Алгоритмы такой сложности принято называть линейными.

Запись алгоритмов

Слайд 12

Повсюду в дальнейшем будем использовать следующие обозначения. Для произвольного вещественного числа

Повсюду в дальнейшем будем использовать следующие обозначения. Для произвольного вещественного числа

х через |_x_|
(читается дно х) и |¯х¯| (потолок х) будем обозначить соответственно наибольшее целое число, не превосходящее х, и наименьшее целое, не меньшее х.
Все логарифмы являются логарифмами чисел по основанию 2.
Поэтому вместо log2x будем писать logx.

Запись алгоритмов

Слайд 13

Графы и сети Многие задачи дискретной оптимизации могут быть интерпретированы как

Графы и сети

Многие задачи дискретной оптимизации могут быть интерпретированы как задачи

на сетях и графах.
Поэтому повторим основные понятия теории графов.
Слайд 14

Графы и сети Рис. 2.1. Изображение графов и орграфов, а) Неориентированный граф, б) Ориентированный граф

Графы и сети

Рис. 2.1. Изображение графов и орграфов,
а) Неориентированный граф,

б) Ориентированный граф
Слайд 15

Удобно вершины графа считать пронумерованными натуральными числами, и на рисунках сразу

Удобно вершины графа считать пронумерованными натуральными числами, и на рисунках сразу

вместо точки ставить соответствующий номер
Число ребер, инцидентных данной вершине, называется степенью вершины.
Вершины степени 1 называют висячими вершинами,
а степени 0 — изолированными.
Например, в графе, изображенном на рис. 2.1.а,
вершины 2, 5, 6 являются висячими.
Степенью захода узла в некотором орграфе называется число дуг, в нее входящих,
степенью исхода — из нее исходящих. Под степенью узла будем понимать сумму степеней исхода и захода данного узла. Например, в орграфе, изображенном на рис. 2.1.б, степень исхода узла 1 равна 2, а степень захода — 1.

Графы и сети

Слайд 16

Цепью (соответственно путем) в графе (орграфе) G = (V,E) назовем чередующуюся

Цепью (соответственно путем) в графе (орграфе)
G = (V,E) назовем чередующуюся

последовательность вершин и ребер
(узлов и дуг) v0,e0, v1, ... ,ek-1, vk такую,
что каждое ребро ek соединяет вершины vk и vk+1
(соответственно исходит из vk и входит в vk+1).
Вершины (узлы) v0 и vk будем называть соответственно началом и концом цепи (пути).
Если все вершины (узлы) цепи (пути) различны, то такую цепь (путь) будем называть
простой цепью (простым путем).

Графы и сети

Слайд 17

Цепь в графе (соответственно путь), начальная и конечная вершины (узлы) которого

Цепь в графе (соответственно путь), начальная и конечная вершины (узлы) которого

совпадают, будем называть циклом {контуром).
Если в цикле (соответственно в контуре) все промежуточные вершины различны, то такой цикл (контур) будем на­зывать простым.
Иногда нам будет удобно цепь (путь)
v0,e0,v1, ... , ek-1,vk отождествлять
с множеством ребер (дуг) е0, ... , ek-1
или вершин (узлов) v0,v1, ... ,vk,
его образующих.
Длиной цепи (пути) будем называть число входящих в нее ребер (дуг).

Графы и сети

Слайд 18

Графы и сети

Графы и сети

Слайд 19

Графы и сети Граф, имеющий ровно одну компоненту связности, будем называть

Графы и сети
Граф, имеющий ровно одну компоненту связности, будем называть связным.


Из определения вытекает, что неориентированный граф G=(V,E) связен
тогда и только тогда, когда для любых вершин v,w V существует цепь в графе G, их соединяющая.
Всюду в дальнейшем через |А| будем обозначать количество элементов конечного множества А.
Говоря о некотором графе или орграфе G=(V,E),
через n будем обозначать количество вершин (или узлов), то есть будем полагать n=|V|,
через m — количество ребер (или дуг), то есть будем полагать m=|E|.
Слайд 20

Графы и сети Условимся считать, что в графах и орграфах нет

Графы и сети

Условимся считать, что в графах и орграфах
нет ребер

вида {v,v} и дуг вида (v,v)
(так называемых петель), и,
что для любых v,w V существует не более одного ребра или не более двух дуг им инцидентных
Тогда справедливы неравенства:
m ≤ n∙(n-1 )/2 — для неориентированных графов,
m ≤ n∙(n-l) — для орграфов.
Слайд 21

Деревья Одним из важнейших понятий в теории графов является понятие дерева.

Деревья

Одним из важнейших понятий в теории графов является понятие дерева. Деревом

называется связный неориентированный граф без циклов.
Теорема1. Пусть G = (V,E) — граф, n=|V|, m=|E|. Тогда следующие условия эквивалентны:
G — дерево.
Для любых двух вершин u,v V существует и притом единственная цепь, их соединяющая.
Граф G связен, и m=n-l.
Граф G не содержит циклов, и m=n-l.
Граф G не содержит циклов, и при соединении любых двух несмежных вершин ребром образуется ровно один цикл.
Слайд 22

Ориентированный граф без контуров называется корневым деревом, если имеется в точности

Ориентированный граф без контуров называется корневым деревом, если
имеется в точности один

узел, называемый корнем, в который не входит ни одна дуга
(т.е. степень захода равна нулю);
в каждый узел, кроме корня, входит ровно одна дуга;
для каждого узла существует путь, начинающийся в корне и заканчивающийся в этом узле.

Корневое дерево

Слайд 23

Корневое дерево Корневое дерево Корневое дерево обычно изображают корнем вверх, располагая

Корневое дерево

Корневое дерево
Корневое дерево обычно изображают корнем вверх, располагая узлы одной

глубины на одном уровне.
У корневого дерева на рис. 2.2
узел с номером 1 является корнем, узлы 4, 5, 6, 7 —- листья.
Высота этого дерева равна 2.
Слайд 24

Корневое дерево Пусть G - (V,E) — корневое дерево, v,w V.

Корневое дерево

Пусть G - (V,E) — корневое дерево, v,w V.
Будем

говорить, что узел v является отцом узла w,
a w — сыном узла v, если (v,w) Е.
Если в G существует путь из v до w, то будем говорить, что w — потомок v, a v — предок w.
Вершина, не имеющая сыновей, называется листом. Глубина узла v в корневом дереве — это длина пути из корня в v. При этом глубину корня будем считать равной нулю.
Высота узла v — это длина самого длинного пути из v в какой-нибудь лист.
Высотой дерева будем называть высоту его корня.
Слайд 25

Двоичные (бинарные) деревья Корневое дерево, каждый узел которого имеет не более

Двоичные (бинарные) деревья

Корневое дерево, каждый узел которого имеет не более двух

сыновей, будем называть двоичным деревом.
Методом математической индукции легко доказать следующее утверждение.
Лемма 2.2. Двоичное дерево высоты k содержит не более 2k листьев.
Специфика дискретных оптимизационных задач практически всегда предполагает, что, как ребра графов, так и дуги орграфов, снабжены некоторой числовой характеристикой.
Практический смысл этих характеристик может быть самым разнообразным.
Например, в задачах, сформулированных ранее, это были:
длина дороги между соседними городами (задача о кратчайшем пути), время обработки конкретной детали на конкретном станке (задача оптимального назначения), стоимость проезда из одного города в другой (задача коммивояжера).
Слайд 26

Двоичные (бинарные) деревья Граф (орграф) будем называть взвешенным, если задана функция

Двоичные (бинарные) деревья

Граф (орграф) будем называть взвешенным,
если задана функция с:

Е→R, иначе говоря,
каждому ребру (дуге) из Е
поставлено в соответствие вещественное число с(е). Число с(е) назовем весом ребра (дуги) е.
Впрочем, в зависимости от специфики той или иной задачи дискретной оптимизации,
число с(е) будем также называть стоимостью ребра (дуги) е,
или пропускной способностью ребра (дуги) е.
Слайд 27

Машинное представление графов и сетей Ориентированный взвешенный граф будем называть сетью.

Машинное представление графов и сетей

Ориентированный взвешенный граф будем
называть сетью.


Таким образом, взвешенный граф или сеть задаются тройкой G = (V,E,c).
Задать граф (орграф) — значит описать множества его вершин (узлов) и ребер (дуг),
а в случае взвешенного графа или сети, описать также функцию весов с: Е→R.
Мы будем предполагать, что вершины графов и узлы сетей занумерованы натуральными числами от 1 до n. Поэтому для описания множества вершин (узлов),
если не указана какая-нибудь дополнительная информация,
достаточно задать одно число —
число вершин (узлов) n.
Слайд 28

Машинное представление графов и сетей Разберем несколько способов машинного представления графа

Машинное представление графов и сетей

Разберем несколько способов машинного представления графа

(орграфа) G = (V,E), где n= |V |, m= | Е |.
Матрица смежностей
определяется как матрица А размера n х n,
в которой A[v,w]=l тогда и только тогда,
когда ребро {v,w} (соответственно дуга (v,w)) имеется в графе (орграфе),
и A[v,w]=0 в противном случае.

А=

Рис 2.3. а) Неориентированный граф и его матрица смежностей,

Слайд 29

Машинное представление графов и сетей А= Рис 2.3. б) Ориентированный граф

Машинное представление графов и сетей

А=

Рис 2.3. б) Ориентированный граф и

его матрица смежностей
Легко видеть, что матрица смежностей неориентированного графа является симметричной.
Представление графа матрицей смежностей удобно для тех алгоритмов, которым многократно нужно выяснять,
есть ли в графе ребро (дуга), соединяющее заданные вершины v и w,
ибо это осуществляется за один шаг — одно обращение к матрице.
Слайд 30

Машинное представление графов и сетей Однако, для ответа на вопросы «к

Машинное представление графов и сетей

Однако, для ответа на вопросы
«к

каким вершинам (узлам) ведут ребра (дуги) из V?» и «какова степень вершины (узла) v?»
нужно просмотреть всю строку матрицы с номером v.
Следовательно, сложность ответа на любой из этих вопросов для фиксированной вершины есть О(n).
Матрица смежностей является достаточно удобным способом представления графа, если не принимать во внимание затраты памяти: граф на n вершинах требует памяти пропорционально n2, независимо от числа ребер.
Особенно сильно этот недостаток проявляется для разреженных графов, т.е. таких, в которых число ребер невелико по сравнению с числом вершин: в этом случае матрица смежностей почти целиком состоит из нулей.
Слайд 31

Машинное представление графов и сетей Взвешенный граф (или сеть) G =

Машинное представление графов и сетей

Взвешенный граф (или сеть) G =

(V,E,c),
может быть задан в ЭВМ матрицей весов А,
в которой полагают A[v,w] = c({v,w}) - весу ребра {v,w} (или весу дуги c((v,w)) ),
и A[v,w] = ∞ — для ребер (дуг), отсутствующих в графе (сети).
Иногда, в зависимости от специфики конкретной задачи, уточняют знак бесконечности, выбирая либо +∞, либо - ∞.
Слайд 32

Машинное представление графов и сетей Более экономным, чем матрица смежностей, и

Машинное представление графов и сетей

Более экономным, чем матрица смежностей, и

универсальным способом является представление графов и сетей списками смежностей.
Списком смежностей для вершины (узла) v называется список всех вершин (узлов) w, смежных с v.
Граф (орграф) представляется с помощью п списков смежностей: по одному для каждой вершины (узла). Точнее, каждый элемент такого списка является записью r, имеющей два поля. Первое поле, обозначим его r^.строка, предназначается для хранения вершин, смежных дан­ной; второе — r^.след — для ссылки на следующую запись в списке. При этом будем считать, что r^.след = nil для последней записи в списке.
Слайд 33

Машинное представление графов и сетей Начало каждого списка хранится в массиве

Машинное представление графов и сетей

Начало каждого списка хранится в массиве

НАЧАЛО,
а именно, HAЧAJIO[v] является указателем на начало списка, соответствующего вершине (узлу) v;
если v — изолированная вершина (узел), то полагаем HAЧAЛО[v] = nil.
Весь такой список для не­ориентированного графа будем обозначать ЗАПИСЬ[v].
Ясно, что в этом случае каждое ребро (v, w) графа представлено дважды:
вершиной w в списке ЗАПИСЬ[v] и вершиной v в списке ЗАПИСЬ[w].
Слайд 34

Машинное представление графов и сетей НАЧАЛО Рис 2.3. Неориентированный граф и его списки смежностей.

Машинное представление графов и сетей

НАЧАЛО

Рис 2.3. Неориентированный граф и

его списки смежностей.
Слайд 35

Для ориентированных графов возможны два способа формирования списков смежностей. В первом

Для ориентированных графов возможны два способа формирования списков смежностей.
В первом

в список ЗАПИСЬ[v] включаются лишь те узлы w, для которых (v, w) E,
т.е. те узлы, к которым ведут дуги из w.
Такой список будем обозначать СЛЕД[v]. Д
ругой способ — включать в список ЗАПИСЬ[v] лишь те узлы w, из которых идут дуги в узел v.
Этот список будем обозначать ПРЕДШ[v].
Для представления взвешенного графа или сети достаточно в соответствующих списках смежностей отвести одно дополнительное поле для весов ребер или дуг.

Машинное представление графов и сетей

Слайд 36

Проанализируем способ представления графов и сетей списками смежностей. Понятно, что объем

Проанализируем способ представления графов и сетей списками смежностей.
Понятно, что объем памяти,

необходимый для представления графа или сети, имеет порядок n+m, что, вообще говоря, лучше, чем представление матрицей смежности. Особенно заметным этот выигрыш по памяти становится для редких графов (m ˂˂ n2).
Ограничимся далее случаем неориентированного графа. Для ответа на вопросы
имеется ли в графе (орграфе) ребро {v,w} (дуга (v,w))?
к каким вершинам (узлам) ведут ребра (дуги) из V?
какова степень вершины (узла) v?
достаточно просмотреть список ЗАПИСЬ[v].
Сложность такого просмотра есть О(n) — такая же, как и в случае матрицы смежностей.

Машинное представление графов и сетей

Слайд 37

Однако, если определять степень всех вершин графа, то здесь сложность ответа

Однако, если определять степень всех вершин графа,
то здесь сложность ответа

будет O(n+m), так как каждое ребро смотрится ровно два раза,
в то время как для матрицы смежностей вычислительная сложность такого просмотра есть О(n2).
Списки смежностей являются достаточно удобным инструментом для решения задач добавления или удаления ребер из графа.
Осуществляются подобные процедуры стандартными средствами для работы со списками.
Понятно, что сложность процедуры добавления ребра является константой, если известно, что данного ребра в графе нет, и имеет сложность О(n),
если предварительно требуется осуществить поиск для ответа на вопрос о том, есть или нет данное ребро в графе. Аналогично обстоит дело и с процедурой удаления ребра (дуги) из графа (соответственно орграфа).

Машинное представление графов и сетей

Слайд 38

Докажите, что в любом графе число вершин нечетной степени четно. В

Докажите, что в любом графе число вершин нечетной степени четно.
В некоторых

задачах удобно представлять граф связанными списками смежностей. А именно, каждая запись в списке 3AПИСЬ[v] имеет еще одно поле, где в записи, содержащей вер­шину w, в дополнительном поле ставится ссылка на ту запись списка 3AПИСЬ[w], которая содержит вершину v. Напишите алгоритмы удаления и добавления ребра в граф, заданный связанными списками смежностей.
Предложите алгоритм, сложности О(n), записывающий все вершины в списке ЗАПИСЬ[v] в обратном порядке.
Пусть некоторый граф задан матрицей смежностей.
Рассмотрим следующую процедуру:
begin х:=0;
for р:=1 to n do
for q:=p to n do
х:= х + A[p,q];
end.
Чему будет равен х в результате работы этой процедуры?

ЗАДАЧИ

Слайд 39

В тех случаях, когда нет необходимости добавлять и удалять ребра или

В тех случаях, когда нет необходимости добавлять и удалять ребра или

дуги из графа, все списки смежностей вместе с массивом НАЧАЛО можно упаковать в один массив, называемый массивом смежностей.
Массив смежностей представляет собой одномерный массив А длины (n+2m+2) для неориентированного графа, и (n+m+2) — для ориентированного.
Рассмотрим случай неориентированного графа. Первые n+1 элементов массива А являются адресной частью, а именно, значением A[v] (v=l,2,...,n) является адрес (индекс) в массиве А, начиная с которого в А записаны подряд все вершины, смежные с вершиной v; А[n+1] указывает на конец массива.

Машинное представление графов и сетей

Слайд 40

Поскольку каждое ребро графа встречается в таком массиве дважды (и имеет

Поскольку каждое ребро графа встречается в таком массиве дважды (и имеет

индексы в массиве от А[n+2] до А[n+1]-1), то массив действительно имеет длину n+2m+2. Отсюда следует, что этот способ представления графа требует меньше памяти, чем матрица смежностей и чем списки смежностей (так как в последнем случае нет нужды в храпении ссылок на следующие записи).
Для ориентированных графов в массиве смежностей, так же как и в списках смежностей, можно хранить дуги по одному разу, записывая либо только исходящие дуги, либо только входящие. И в том, и в другом случае массив будет иметь длину n+m+2 .

Машинное представление графов и сетей

Слайд 41

Пример. Для неориентированного графа 1 2 3 4 массив смежностей должен

Пример. Для неориентированного графа
1 2
3 4
массив смежностей должен быть следующим:
6 8 10 13

14 2 3 1 3 1 2 4 3 32767

Машинное представление графов и сетей

Слайд 42

Поясним на примере: Количество вершин n = 4 Количество ребер m

Поясним на примере:
Количество вершин n = 4
Количество ребер m = 4
Ниже

перечислены для указанного в примере графа вершины и соответствующие каждой вершине смежные вершины.
1: 2, 3;
2: 1, 3;
3: 1, 2, 4;
4: 3.

Машинное представление графов и сетей

Слайд 43

Для взвешенного неориентированного графа (25) 1 2 (4) (0) 3 4

Для взвешенного неориентированного графа
(25)
1 2
(4) (0)
3 4
(7)

массив смежностей должен быть следующим:
6 10 14 20 nil 2 25 3 4 1 25 3 0 1 4 2 0 4 7 3 7 nil
22 – количество элементов массива 32767

Машинное представление графов и сетей

Слайд 44

Поясним Количество вершин n = 4 Количество ребер m = 4

Поясним
Количество вершин n = 4
Количество ребер m = 4
Ниже перечислены для

указанного в примере графа вершины и соответствующие каждой вершине пары вида (вес, смежная вершина).
1: (25, 2); (4, 3);
2: (25, 1); (0, 3);
3: (4, 1); (0, 2); (7, 4);
4: (7, 3);

Машинное представление графов и сетей

Слайд 45

Вернемся к предложенным на прошлой паре задачам. После решения задачи «Предложите

Вернемся к предложенным на прошлой паре задачам.
После решения задачи «Предложите алгоритм,

сложности О(n), записывающий все вершины в списке ЗАПИСЬ[v] в обратном порядке»
Программа, работающая по указанному алгоритму должна выдавать соответствующие каждой вершине пары вида (вес, смежная вершина) в обратном порядке.
1: (4, 3); (25, 2);
2: (0, 3); (25, 1);
3: (7, 4); (0, 2); (4, 1);
4: (7, 3).

Машинное представление графов и сетей

Слайд 46

Входные данные содержат описание графа, заданного массивом смежности. В первой строке

Входные данные содержат описание графа,
заданного массивом смежности.
В первой строке n

- число элементов в массиве.
Далее построчно расположен массив
смежности (не более 10 чисел в одной строке). Последний элемент массива равен 32767.
22
6 10 14 20 22 2 25 3 4 1
25 3 0 1 4 2 0 4 7 3
7 32767

Решение задачи

Слайд 47

На выходе программа построчно выдает для каждой вершины (начиная с первой

На выходе программа построчно выдает для каждой вершины (начиная с первой

и до n-ой) пары вида
(вес, смежная вершина) в прямом порядке.
А затем для каждой вершины (опять начиная с первой и до N-ой) пары вида
(вес, смежная вершина) в прямом порядке.
Количество вершин n = 4
Cписок смежности в прямом порядке:
1: (25, 2); 1: (4, 3);
2: (25, 1); 2: (0, 3);
3: (4, 1); 3: (0, 2); 3: (7, 4);
4: (7, 3);
Cписок смежности в обратном порядке:
1: (4, 3); 1: (25, 2);
2: (0, 3); 2: (25, 1);
3: (7, 4); 3: (0, 2); 3: (4, 1);
4: (7, 3);

Решение задачи

Слайд 48

// Библиотеки #include #include #include #include using namespace std; void main()

// Библиотеки
#include
#include
#include
#include
using namespace std;
void main() {
int n

= 0;
vector < pair < int, pair > > g; // ребра: вес - вершина 1 - вершина 2
freopen("in.txt","r", stdin);
freopen("out.txt","w", stdout);
int temp;
cin >> temp;// сколько чисел вообще считывать
int *temp_ar = new int [temp];//весь массив смежностей
int *temp_ar_number = new int [temp];//вспомогательный массив для хранения только позиций (адресов)

Программа на C++

Слайд 49

for (int i = 0; i temp_ar_number[i] = -1; } for(int

for (int i = 0; i < temp; i++) {
temp_ar_number[i] =

-1;
}
for(int i = 0; i < temp; i++) {
cin >> temp_ar[i]; // считали из файла массив, где все входные данные (весь массив смежности)
}
for (int i = 0; i < temp; i++){
temp_ar_number[i] = temp_ar [i]; //массив с адресной частью
if (temp_ar[i] == temp) {
n = i;
break;
}
}
// Определили количество вершин графа (в соответствии с придуманной и реализованной нами структурой входного файла)

Программа на C++

Слайд 50

cout Формирование массива смежности int fict = 1;//фиктивная переменная начало ребра

cout << "\n" <<"Количество вершин n = "<< n << "\n";
Формирование

массива смежности
int fict = 1;//фиктивная переменная начало ребра
int k;
for (int i = 0; i < temp; i++){
int numb_begin = temp_ar_number[i]-1;
//взяли первое определяющее число массива
int numb_end = temp_ar_number[i+1]-1;
//взяли второе определяющее число массива
for (int j = numb_begin; j < numb_end; j+=2){
g.push_back(make_pair(temp_ar[j+1], make_pair (fict, temp_ar[j])));
}
fict++;
if (numb_end == (temp-1)) break;
}

Программа на C++

Слайд 51

Вывод (печать) массива смежности cout for( int i = 0; i

Вывод (печать) массива смежности
cout <<«Список смежности в прямом порядке:\n";
for( int i

= 0; i < g.size(); i++ ) {
cout << g[i].second.first<<": (" << g[i].first << ", " << g[i].second.second << "); ";
k = i+1;
if(g[i].second.first != g[k].second.first){
cout << "\n";
}
}

Программа на C++

Слайд 52

Формирование массива смежности vector > > g_convert; // обратные списки смежности

Формирование массива смежности
vector < pair < int, pair > > g_convert;

// обратные списки смежности
fict = 1;
for (int i = 0; i < temp; i++){
int numb_begin = temp_ar_number[i]-1;//взяли первое определяющее число массива
int numb_end = temp_ar_number[i+1]-1;//взяли второе определяющее число массива
for (int j = numb_end; j > numb_begin; j-=2){
g_convert.push_back(make_pair(temp_ar[j-1], make_pair (fict, temp_ar[j-2])));
}
fict++;
if (numb_end == (temp-1)) break;
}

Программа на C++

Слайд 53

Вывод массива смежности cout for( int i = 0; i cout

Вывод массива смежности
cout <<"\nCписок смежности в обратном порядке:\n";
for( int i =

0; i < g_convert.size(); i++) {
cout << g_convert[i].second.first<<": (" << g_convert[i].first << ", " << g_convert[i].second.second << "); ";
k = i+1;
if( g_convert[i].second.first != g_convert[k].second.first){
cout << "\n";
}
}
}

Программа на C++

Слайд 54

Обучающийся 1) рисует взвешенный граф, 2) «вручную» пишет на листке массив

Обучающийся
1) рисует взвешенный граф,
2) «вручную» пишет на листке массив

смежности (в прямом и обратном порядках),
3) подписанный листок с нарисованным графом сдает преподавателю (мне!!!),
4) пишет программу на Java или на Паскале, которая решает задачу,
5) после проверки правильности ее работы преподаватель проверяет работоспособность программы на нескольких графах (скорее всего, на графах, предложенных одногруппниками),
6) объясняет код и получает «плюсик».

Индивидуальное задание для реализации на уроке (прямо сегодня!!!)

Слайд 55

Сортировка является неотъемлемой частью многих алгоритмов решения математических задач. Задача сортировки

Сортировка является неотъемлемой частью многих алгоритмов решения математических задач.
Задача сортировки

формулируется следующим образом:
Дана последовательность из n элементов a1,...,an, выбранных из множества, на котором задано отношение линейного порядка.
Требуется найти перестановку
s = (s(l),…,s(n)) индексов, для которой
as(1) ≤ as(2) ≤ ... ≤ as(n),
т.е. расположить элементы данной последовательности в неубывающем порядке
(или в невозрастающем, т.е. as(1) ≥ as(2) ≥ ... ≥ as(n)).

Сортировка данных

Слайд 56

При формулировании задачи сортировки в общем виде информацию о последовательности элементов

При формулировании задачи сортировки в общем виде информацию о последовательности элементов

можно получать только с помощью операции сравнения двух элементов.
Пусть а1,...,аn - последовательность сортируемых элементов.
Не ограничивая общности, можно считать, что элементы заданной последовательности помещены в некоторый массив А
Не ограничивая общности, можно считать, что элементы заданной последовательности помещены в некоторый массив А в том же порядке,
m.е. A[i] = ai при i = 1,2,...,n.

Сортировка данных

Слайд 57

Алгоритм сортировки выбором Данные: массив А[1..n]. Результат: массив А[1..n] такой, что

Алгоритм сортировки выбором
Данные: массив А[1..n].
Результат:
массив А[1..n] такой, что А[1]

≤ А[2] ≤ ... ≤ A[n].
begin
procedure MIN(i):
begin for j = i to n do
if A[i] < A[j] then A[i]↔A[j];
end;
begin (* главная программа *)
for i := 1 to n-1 do MIN(i);
end;
end.

Сортировка выбором

Слайд 58

Процедура MIN(i) выбирает минимальный элемент из массива аi,...,аn и ставит его

Процедура MIN(i)
выбирает минимальный элемент из
массива аi,...,аn и ставит его

на первое место, т.е. на место ai.
Алгоритм начинает работу с вызова процедуры MIN(l), которая перемещает
на первое место наименьший элемент исходного массива.
Далее процедура повторяется для массива
а2,...,аn и т.д.

Сортировка выбором

Слайд 59

Сортировка выбором имеет вычислительную сложность O(n2). Действительно, в процедуре MIN(i) осуществляется

Сортировка выбором имеет вычислительную сложность O(n2).
Действительно, в процедуре MIN(i) осуществляется (n-i)

операции сравнения и, в худшем случае, (n-i) операции обмена.
Значит, общее число шагов, выполняемое процедурой MIN(i) пропорционально (n-i).
Число сравнений в алгоритме
(n - 1) + (n - 2) + ... + 1 = n(n - 1 )/2
Т.е. сложность алгоритма есть O(n2).

Сортировка выбором

Слайд 60

Приведем теорему, позволяющую оценить снизу сложность любого алгоритма сортировки. В любом

Приведем теорему, позволяющую оценить снизу сложность любого алгоритма сортировки.
В любом алгоритме,

упорядочивающем с помощью сравнений,
на упорядочение последовательности из n элементов
тратится не менее c∙n∙loq n сравнений
при некотором с > 0 и достаточно большом n.
Для доказательства представим алгоритм в виде корневого дерева.
Любой алгоритм, упорядочивающий с помощью сравнений, можно схематично представить в виде корневого дерева, называемого двоичным деревом решений.
Это дерево можно рассматривать как блок-схему алгоритма сортировки, в котором показаны все сравнения элементов и исходы алгоритма.
Вершины дерева (кроме листьев) соответствуют сравнениям элементов, при этом корень дерева соответствует первому сравнению, осуществляемому алгоритмом.
Сыновья вершин изображают возможные исходы сравнения отца.
Листья соответствуют исходу алгоритма в зависимости от начальных значений переменных.

Сортировка данных

Слайд 61

Двоичное дерево решений для сортировки трех элементов

Двоичное дерево решений для сортировки трех элементов

Слайд 62

Поскольку, всякое двоичное дерево высоты к имеет не более 2к листьев,

Поскольку, всякое двоичное дерево высоты к имеет не более 2к листьев,

то получаем, что должно выполняться неравенство 2к > n!,
т.к. листьев в двоичном дереве решений должно быть не меньше, чем перестановок из n элементов.
Отсюда, k > log n!
Осталось заметить, что при n > 1 справедлива следующая цепочка неравенств:
n! ≥ n(n - 1 )(n - 2)... () ≥ (n/2)n/2, так что
log n! ≥ log( n/2 )n/2 = n/2 log n/2 ≥ n/4 log n
Итак, k ≥ n/4 log n — полученное неравенство завершает доказательство теоремы.

Сортировка данных

Слайд 63

Алгоритм сортировки, называемый СОРТДЕРЕВО, имеет сложность O(n log n). В разных

Алгоритм сортировки, называемый СОРТДЕРЕВО, имеет сложность O(n log n).
В разных

учебниках он называется: алгоритмом пирамидальной сортировки, Heapsort или Treesort.
Определим структуру корневого двоичного дерева в массиве А[1..n], считая,
что в корне находится элемент А[1],
и элемент A[i] имеет двух сыновей:
A[2i] (если 2i ≤ n) и A[2i+1] (если 2i+1 ≤ n).
Такую структуру назовем двоичным деревом массива А.

Алгоритм СОРТДЕРЕВО

Слайд 64

Алгоритм СОРТДЕРЕВО Лемма. Двоичное дерево массива длины n имеет высоту Напомним,

Алгоритм СОРТДЕРЕВО

Лемма.
Двоичное дерево массива длины n имеет высоту
Напомним, что высота

корневого дерева есть по определению длина самого длинного пути из корня до какого-нибудь листа. Например, на рис.3.2 это путь до листа, в котором находится число 7. Легко видеть, что длина этого пути равна 3.
Слайд 65

Пусть k - высота двоичного дерева массива длины n. Для всех

Пусть k - высота двоичного дерева массива длины n.
Для всех

s < k в дереве имеется ровно 2s вершин глубины s. Пусть h — количество вершин глубины k.
Тогда справедливо неравенство 1 < h < 2k. Поскольку число вершин равно n — длине массива, то справедливо равенство:
n = 1 + 2 + ... + 2k-1 + h = 2k - 1 + h.
Учитывая, что h ≤ 2k, получаем, что
n = 2k - 1 + h ≤ 2k - 1 + 2k < 2k+1.
Отсюда n < 2k+1. С другой стороны, так как h ≥ 1, то
n= 2k - 1 + h ≥ 2k.
Таким образом, справедливо неравенство 2k ≤ n ≤ 2k+1.
Отсюда, k ≤ logn ≤ k+1, то есть k =

Алгоритм СОРТДЕРЕВО

Слайд 66

Двоичное дерево массива А называется сортирующим деревом массива А, если выполняются

Двоичное дерево массива А называется сортирующим деревом массива А, если выполняются

условия:
А[k] ≥ А[2 k] и А[k] ≥ А[2 k +1] для к = l,2,....
Непосредственно из определения вытекает, что наибольший элемент массива находится в корне его сортирующего дерева.
Легко видеть также, что двоичное дерево, изображенное на представленном выше рис., не является сортирующим.
Именно на представлении массива сортирующим деревом основан один из теоретически наилучших алгоритмов сортировки данных — СОРТДЕРЕВО.

Алгоритм СОРТДЕРЕВО

Слайд 67

На первом этапе двоичное дерево массива А преобразуется в сортирующее. Процедуру,

На первом этапе двоичное дерево массива А преобразуется в сортирующее. Процедуру,

осуществляющую это преобразование, будем называть ПСД.
Затем, поскольку по свойству сортирующего дерева,
элемент в корне, а именно, А[1] является наибольшим в А, то, переставляя А[1] и А[n],
и удаляя А[n] из дерева, получим массив А[1.. n-1] и A[n] = max А[1..n]. Теперь преобразуем А[1..n-1] в сортирующее дерево,
затем переставим А[1] и А[n-1] и удалим А[n-1]. Процесс продолжается до тех пор, пока в сортирующем дереве не останется один элемент. Тогда А[1],...,А[n] — упорядоченная по неубыванию последовательность.

Алгоритм СОРТДЕРЕВО

Слайд 68

Перейдем к формальному описанию алгоритма СОРТДЕРЕВО. Начнем с описания процедуры ПСД

Перейдем к формальному описанию алгоритма СОРТДЕРЕВО. Начнем с описания процедуры ПСД

(построение сортирующего дерева). В его основе лежит рекурсивная процедура ПЕРЕСЫПК(i,j), имеющая параметры i и j. Они задают область ячеек массива А, которая в результате процедуры ПЕРЕСЫПКА будет обладать свойством сортирующего дерева, при этом его корень помещается в вершину i.

Алгоритм СОРТДЕРЕВО

Слайд 69

Алгоритм СОРТДЕРЕВО АЛГОРИТМ 3.2. СОРТДЕРЕВО Данные: массив элементов А[1..n]. Результат: массив

Алгоритм СОРТДЕРЕВО

АЛГОРИТМ 3.2. СОРТДЕРЕВО
Данные: массив элементов А[1..n].
Результат: массив элементов

А[1..n], упорядоченный по неубыванию, то есть А[1] ≤ А[2] ≤ ... ≤ А[n].
begin
ПСД; (* вначале строится сортирующее дерево *)
for i := n downto 2 do
begin
A[l] ↔ A[i];
ПЕРЕСЫПКА( 1,i-1)
end;
end
Слайд 70

procedure ПСД; begin for i := downto 1 do ПЕРЕСЫПКА(i,n) End

procedure ПСД;
begin
for i := downto 1 do ПЕРЕСЫПКА(i,n)
End
Ниже дано формальное описание

процедур ПЕРЕСЫПКА. Без формального описания используется функция MAXCЫH(i), значением которой является тот сын i, который со­держит наибольший из элементов A[2i] и A[2i+1].

Алгоритм СОРТДЕРЕВО

Слайд 71

procedure ПЕРЕСЫПКА( i ,j); begin if i ≤ then (* если

procedure ПЕРЕСЫПКА( i ,j);
begin
if i ≤ then (* если i — не

лист *)
begin k := MAXCЫH(i);
if A[i] < A[k] then
begin
A[i]↔ A[k]; ПЕРЕСЫПКА(k,j)
end;
end;
end;

Алгоритм СОРТДЕРЕВО

Слайд 72

Разберем пример, иллюстрирующий работу обеих этих процедур Пусть задан числовой массив

Разберем пример, иллюстрирующий работу обеих этих процедур
Пусть задан числовой массив А[1…10]:
I 1 2 3 4 5 6 7 8 9 10
А[I] 2 3 6 1 4 5 8 0 7 9

Алгоритм

СОРТДЕРЕВО
Слайд 73

Алгоритм СОРТДЕРЕВО

Алгоритм СОРТДЕРЕВО

Слайд 74

Алгоритм СОРТДЕРЕВО Изобразим окончательный результат в виде таблицы: I 1 2

Алгоритм СОРТДЕРЕВО

Изобразим окончательный результат в виде таблицы:
I 1 2 3 4 5 6 7 8 9 10
A[I] 9 7 8 2 4 5 6 0 1 3

Слайд 75

Алгоритм СОРТДЕРЕВО

Алгоритм СОРТДЕРЕВО

Слайд 76

Алгоритм СОРТДЕРЕВО На рис.3.4 дерево f) является сортирующим деревом исходно­го массива

Алгоритм СОРТДЕРЕВО

На рис.3.4 дерево f) является сортирующим деревом исходно­го массива

А, полученным в результате работы процедуры ПСД. Затем происходит перестановка А[1] и А[10] (дерево g) ). К дере­ву g) применяется процедура ПЕРЕСЫПКА(1,9), в результате которой число 3 проходит путь по правым ветвям из корня дере­ва до листа. Затем вновь происходит перестановка корня с лис­том и т.д. В результате получится массив А, упорядоченный по возрастанию.
Слайд 77

Поиск в графе Поиск в графе Большинство алгоритмов на графах основаны

Поиск в графе

Поиск в графе
Большинство алгоритмов на графах основаны на систематическом

переборе всех вершин графа, при котором каждая вершина просматривается в точности один раз,
при этом переход от уже рассмотренной вершины к еще не рассмотренной вершине осуществляется по ребрам графа.
В этой главе будут рассмотрены два стандартных, широко используемых на практике метода такого перебора: поиск в глубину и поиск в ширину.
Оба этих метода поиска будут описаны только для неориентированных графов.
Слайд 78

Поиск в глубину Поиск начинается с некоторой фиксированной вершины v, называемой

Поиск в глубину

Поиск начинается с некоторой фиксированной вершины v, называемой

корневой вершиной поиска или корнем. При этом считаем v просмотренной вершиной. Затем выбираем какое-нибудь ребро {v,w}, инцидентное v, проходим его и попадаем в вершину w.
Слайд 79

Поиск в глубину Тот факт, что в процессе поиска использовано именно

Поиск в глубину

Тот факт, что в процессе поиска использовано именно

ребро {v,w} отмечается обычно следующим образом.
Ребро {v,w} ориентируется из v в w. Полученную дугу (v,w) считают дугой корневого дерева с корнем v.
Такое дерево называется ПВГ-деревом с корнем v, или короче ПВГ(v)—деревом.
При переходе от v к w, вершина v объявляется отцом вершины w
и обозначается OTEЦ[w], вершина w объявляется просмотренной, и поиск продолжается из вершины w.
Слайд 80

Поиск в глубину В общем случае, когда мы находимся в некоторой

Поиск в глубину

В общем случае, когда мы находимся в некоторой

вершине v, возникают две возможности:
1) Все вершины, смежные с v, уже просмотрены. В этом случае возвращаемся к вершине ОТЕЦ[v] и продолжаем поиск из нее, а вершину v с этого момента считаем использованной.
Слайд 81

Поиск в глубину 2) Существует еще не просмотренная вершина w, смежная

Поиск в глубину

2) Существует еще не просмотренная вершина w, смежная

с вершиной v. Тогда ребро {v,w} превращаем в дугу (v,w),
добавляя ее к ПВГ(v)-дереву;
полагаем ОТЕЦ[w]=v;
проходим по дуге из v в w и продолжаем поиск из w.
Слайд 82

Поиск в глубину Поиск в глубину завершается тогда, когда все вершины

Поиск в глубину

Поиск в глубину завершается тогда, когда все вершины

графа будут просмотрены. Здесь возможны две ситуации:
1) Корневая вершина использована (т.е. все смежные с ней вершины просмотрены), однако в графе еще есть не просмотренные вершины. В этом случае выбираем произвольную не просмотренную вершину, объявляем ее корнем и вновь начинаем поиск уже из этой вершины. Такая ситуация возникает только в случае несвязного графа.
2) Корневая вершина и все другие использованы. Поиск на этом заканчивается.
Слайд 83

Поиск в глубину Представим формальное описание изложенного алгоритма поиска в глубину,

Поиск в глубину

Представим формальное описание изложенного алгоритма поиска в глубину,

основанную на рекурсивной процедуре ПВГ(v) — поиск в глубину из вершины v. В рассматриваемом алгоритме связность графа не предполагается.
АЛГОРИТМ Поиск в глубину.1
Данные: неориентированный граф G=(V,E), заданный списками смежностей ЗАПИСЬ[v].
Результаты: массив ОТЕЦ, множество Т.
procedure ПВГ (v); (*поиск в глубину с корнем v)
begin METKA[v]:=l;
for w ЗАПИСЬ[v] do
if METKA[w]=0 then
begin OTEЦ[w]:=v; T:=T{(v,w)}; ПВГ(w);
end;
end;
begin (*Главная программа)
T := Ø;
for v V do METKA[v]:=0; (*инициализация)
for v V do
if METKA[v]=0 then
begin OTEЦ[v]:=nil; ПВГ(v);
end;
end.
Слайд 84

Поиск в глубину Примечание. Массив МЕТКА, используемый в алгоритме имеет по

Поиск в глубину

Примечание.
Массив МЕТКА, используемый в алгоритме имеет по одному

элементу для каждой вершины графа и служит указателем на то, что просмотрена или нет данная вершина.
Считаем, что METKA[v]=0, если v не просмотрена, и METKA[v]=1 в противном случае.
Массив ОТЕЦ описан ранее. Понятно, что он имеет длину n, где n — число вершин в графе.
В множестве Т будем хранить дуги ПВГ-деревьев.
Слайд 85

Поиск в глубину На следующем рис. показано, как поиск в глубину

Поиск в глубину

На следующем рис. показано,
как поиск в глубину

исследует неориентированный граф G. Предполагается, что в списках смежности этого графа вершины встречаются в порядке возрастания номеров, и, что цикл в строках 11-14 алгоритма Поиск в глубину.1 выполнялся в порядке возрастания номеров вершин.
Слайд 86

Поиск в глубину

Поиск в глубину

Слайд 87

Поиск в глубину В просмотренном графе G дуги ПВГ-деревьев обозначены стрелками

Поиск в глубину

В просмотренном графе G дуги
ПВГ-деревьев обозначены стрелками

в соответствии с ориентацией, полученной в ходе поиска.
Такие дуги часто называют прямыми дугами поиска. Прочие ребра графа, называемые иногда обратными дугами поиска, обозначены на рисунке пунктирами.
Числа в скобках, стоящие у вершин просмотренного графа, соответствуют очередности, в которой они просматривались в ходе поиска.
Отметим, что вершины с номерами 1, 9 и 11 являются корнями ПВГ-деревьев.
Слайд 88

Поиск в глубину Разберем теперь нерекурсивную версию процедуры ПВГ(v). Рекурсия устраняется

Поиск в глубину

Разберем теперь нерекурсивную версию процедуры ПВГ(v).
Рекурсия устраняется

стандартным способом с помощью стека.
Каждая вершина помещается в стек сразу, как только будет достигнута, то есть просмотрена, и удаляется из стека после того, как будет использована.
Поиск новой непросмотренной вершины ведется из той вершины, которая последней попала в стек.
Слайд 89

Поиск в глубину Для организации такого процесса понадобится дополнительно массив указателей

Поиск в глубину

Для организации такого процесса понадобится дополнительно массив указателей


УКАЗ длины n, где n=|V|.
Предполагается, что в начале работы процедуры поиска выполняются равенства УKA3[v]=HAЧAЛO[v], для всех v из V, иначе говоря, УКАЗ[v] дает адрес первой записи в списке ЗАПИСЬ[v].
В процессе работы процедуры поиска УКАЗ[v] меняется таким образом, что указывает на следующую запись в списке ЗАПИСЬ[v] после той, которая содержит последнюю просмотренную из нее вершину.
Слайд 90

Поиск в глубину procedure ПВГ1(v); (* нерекурсивная версия *) begin СТЕК

Поиск в глубину

procedure ПВГ1(v); (* нерекурсивная версия *)
begin
СТЕК :=Ø; СТЕК

v; METKA[v]:=l;
while СТЕК ≠ Ø do
begin u СТЕК;
while (УКАЗ[u] ≠ nil) and (МЕТКА[УКАЗ[u]^.строка]=1) do
УКАЗ[u] := УКАЗ[u]^.след;
if УКАЗ[u] ≠ nil then (*найдена непросмотренная вершина *)
begin w := УКАЗ[u]^.строка:
СТЕК w; OTEЦ[w]:=u; METKA[w]:=l;
T := T(u,w); УКАЗ[u]:= УКАЗ[u]^.след;
end;
else СТЕК (* вершина u использована *)
end;
end.
Слайд 91

Поиск в глубину Теорема. Сложность алгоритма Поиск в глубину 1 есть

Поиск в глубину

Теорема.
Сложность алгоритма
Поиск в глубину 1 есть

O(n+m).
Следствие.
Связные компоненты неориентированного графа могут быть найдены за время O(n+m).
Слайд 92

Поиск в глубину Поиск в глубину в ориентированном графе отличается от

Поиск в глубину

Поиск в глубину в ориентированном графе отличается от

поиска в неориентированном графе только тем, что ребра проходятся в соответствии с их ориентацией.
Поскольку в главе 2 мы условились считать, что в списке ЗАПИСЬ[у] встречаются только те вершины w,
для которых (v,w) E,
то алгоритм Поиск в глубину1 корректно работает и в ориентированных графах.
Слайд 93

Поиск в ширину Поиск в ширину Другое название этого популярнейшего метода

Поиск в ширину

Поиск в ширину
Другое название этого популярнейшего метода

— волновой алгоритм.
Причины появления такого названия станут ясны из дальнейшего.
Поиск в ширину начинается с некоторой фиксированной вершины v, называемой корнем.
Вершину v считаем просмотренной и помещаем ее в организуемую нами очередь.
Считаем также, что вершина v образует нулевой фронт распространения волны.
Слайд 94

Поиск в ширину Затем проходим все ребра {v,w}, инцидентные v, в

Поиск в ширину

Затем проходим все ребра {v,w}, инцидентные v, в

каком-нибудь порядке и ориентируем их из v в w.
Вершины w, смежные с v, считаем просмотренными
и размещаем их в порядке просмотра ребер в очередь.
Для всех таких вершин w полагаем
OTEЦ [w]:=v и говорим, что w просмотрена из v.
Ориентированные ребра (v,w) будем называть ребрами ПВШ(v)-дерева.
Говорят часто, что все такие вершины w образуют первый фронт распространения волны.
Вершина v после этих действий считается использованной и удаляется из очереди.
Слайд 95

Поиск в ширину Дальнейший поиск продолжается следующим образом. Берем очередную вершину

Поиск в ширину

Дальнейший поиск продолжается следующим образом. Берем очередную вершину

v из очереди, проходим по всем ребрам, ин­цидентным v, которые соединяют вершину v с еще непросмотренными вершинами w.
Все такие вершины w объявляются просмотренными, для них
полагают OTEЦ[w]:=v, ребра (v,w) относят к ПВШ(v)-дереву.
Слайд 96

Поиск в ширину После этих действий вершина v считается использованной и

Поиск в ширину

После этих действий вершина v считается использованной и

удаляется из очереди. Говорят также, что вершины, просмотренные из вершин, принадлежащих фронту с номером k,
образуют (k+1)-ый фронт распространения волны.
Завершается поиск в ширину с корнем в заданной вершине таким же образом, как и поиск в глубину, а именно тогда, когда ни одной новой вершины просмотреть не удается.
Слайд 97

Поиск в ширину На следующем рисунке (2) показано, как поиск в

Поиск в ширину

На следующем рисунке (2) показано, как поиск в

ширину исследует граф G, изображенный ранее на рис. (1).
Дуги ПВШ-деревьев изображены стрелками в соответствии с ориентацией, полученной в ходе поиска. Прочие ребра исходного графа изображены пунктиром.
Предполагалось, что вершины в ходе поиска просматривались в порядке возрастания их номеров.
Слайд 98

Поиск в ширину

Поиск в ширину

Слайд 99

Поиск в ширину Отметим, что в ПВШ(1) - дереве поиска вершины

Поиск в ширину

Отметим, что в ПВШ(1) - дереве поиска вершины

2, 3, 4 обра­зуют первый фронт распространения волны, вершины 5, 6 и 7 — второй, а вершина 8 — третий.
Слайд 100

Поиск в ширину Отметим, что в ПВШ(1) – дереве поиска вершины

Поиск в ширину

Отметим, что в ПВШ(1) –
дереве поиска вершины

2, 3, 4 образуют первый фронт распространения волны,
вершины 5, 6 и 7 — второй,
а вершина 8 — третий.
Далее представлен
АЛГОРИТМ 4.2. ПОИСК В ШИРИНУ
Данные: неориентированный граф G=(V,E), заданный списками смежностей.
Результаты: массив ОТЕЦ, множество D.
Слайд 101

Поиск в ширину procedure ПВШ(v); (* поиск в ширину с корнем

Поиск в ширину

procedure ПВШ(v); (* поиск в ширину с корнем v

*)
begin ОЧЕРЕДЬ :=Ø; ОЧЕРЕДЬ v; METKA[v]:=1;
while ОЧЕРЕДЬ ≠Ø do
begin u ОЧЕРЕДЬ; ОЧЕРЕДЬ;
for w ЗАПИСЬ[u] do (* используем вершину u *)
if METKA[w]=0 then
begin ОЧЕРЕДЬ w; OTEЦ[w]:=u; METKA[w]:=1;
D=Du{(u,w)};
end;
end;
end;
begin (*главная программа*)
D:=Ø; for vV do METKA[v]:=0; (* инициализация *)
for v V do
if METKA[v]=0 then (*v – корень*)
begin OTEЦ([v]:=nil; ПВШ(v);
end;
end.
Слайд 102

Поиск в ширину В приведенном формальном описании алгоритма поиска в ширину

Поиск в ширину

В приведенном формальном описании алгоритма поиска в ширину

переменная МЕТКА имеет тот же смысл, что и ранее в алгоритме Поиск в глубину 1.
Дуги ПВШ-деревьев хранятся в множестве D.
Смысл переменной ОТЕЦ объяснен выше. Просмотренные вершины помещаются в ОЧЕРЕДЬ и удаляются оттуда сразу после их использования (строка 4 алгоритма).
Слайд 103

Поиск в ширину В алгоритме Поиск в ширину 2 связность графа

Поиск в ширину

В алгоритме Поиск в ширину 2 связность графа

не предполагается. Для корневых вершин поиска и только для них выполняется равенство ОТЕЦ[v]=nil.
Теорема 4.2. Алгоритм ПОИСК В ШИРИНУ 2 имеет вычислительную сложность O(n+m).
Слайд 104

Цепи и пути в графах Применительно к только связным неориентированным графам

Цепи и пути в графах

Применительно к только связным неориентированным графам

нетрудно проверить, что и ПВГ-дерево, и ПВШ-дерево действительно являются деревьями, и более того — корневыми деревьями, причем корнями этих деревьев являются те вершины, с которых начинался поиск
(собственно поэтому они и в ПВГ и в ПВШ названы корневыми вершинами).
Слайд 105

Цепи и пути в графах Если в ориентированном графе имеется дуга

Цепи и пути в графах

Если в ориентированном графе имеется дуга

(v,w), то v — отец w, a w — сын v. Легко видеть, что даваемые алгоритмами ПоискВглубину1 и ПоискВширину2 значения переменных ОТЕЦ[w] согласуются с ранее введенным понятием, а именно, если v=ОТЕЦ[w], то (v,w)E.
Вершина v называется предком вершины w, и, соответственно, w — потомком v, если в корневом дереве существует путь от v до w. Например, в корневом дереве ПВШ(1)
из рис. вершина 8 является потомком вершины 2.
Слайд 106

Цепи и пути в графах Теорема 3. Пусть Т — ПВГ-дерево

Цепи и пути в графах

Теорема 3. Пусть Т — ПВГ-дерево

связного неориентиро­ванного графа G=(V,E), и пусть {u,w}E. Тогда либо u — потомок w, либо w потомок u в корневом дереве Т.
Понятно, что ПВШ-дерево не обладает свойством, сформули­рованным в теореме3.
Например, в ПВШ(1)-дереве, изобра­женном на рис. 2, ни вершина 3 не является потомком вершины 6, ни вершина 6 не является потомком вершины 3
(говорят, что такие вершины несравнимы в корневом дереве).
Слайд 107

Цепи и пути в графах Как в ПВГ-дереве, так и в

Цепи и пути в графах

Как в ПВГ-дереве, так и в

ПВШ-дереве для каждой вершины w,
существует единственный путь из корня v в w.
Как построить этот путь?
Это несложно делается с помощью массива ОТЕЦ.
Отметим только, что под путем в орграфе мы договорились понимать в зависимости от степени удобства,
либо последовательность ребер, либо последовательность вершин.
Слайд 108

Цепи и пути в графах В предлагаемом ниже алгоритме ПостроениеПути3 требуемый

Цепи и пути в графах

В предлагаемом ниже алгоритме ПостроениеПути3 требуемый

путь идентифицируется последовательностью вершин. Предполагается, что перед работой этого алгоритма работала либо процедура ПВГ(v), либо процедура ПВШ(v).
Слайд 109

Цепи и пути в графах АЛГОРИТМ ПостроениеПути3. Данные: корневая вершина поиска

Цепи и пути в графах

АЛГОРИТМ ПостроениеПути3.
Данные: корневая вершина поиска

v, вершина w. массив ОТЕЦ.
begin
СТЕК:=Ø; СТЕК w; u:=w;
while u≠v do
begin u:=ОТЕЦ[u];
CTEK u;
end;
end.
Результат: СТЕК, содержащий последовательность вершин, об­разующих v-w-путь.
Слайд 110

Цепи и пути в графах Понятно, что последовательность вершин v=v0,v1,...,vk=w, по­лученная

Цепи и пути в графах

Понятно, что последовательность вершин v=v0,v1,...,vk=w, по­лученная

считыванием СТЕКА, образует как v-w-путь в корневом дереве Т (или D), так и v-w-цепь в исходном графе G.
Оказывается, что пути, построенные поиском в ширину, обладают очень полезным свойством, а именно, справедлива.
Теорема 4. Пусть D — ПВШ-дерево с корнем v связного неориентированного графа G=(V,E).
Тогда для любой вершины w V единственный v-w-путь в D определяет кратчайшую по числу ребер цепь среди всех v-w-цепей в графе G.
- Предыдущая
Делинквентті жасөспірімдердің құндылық бағдарын қалыптастыру
Следующая -
Холодное сердце. Книги об Анне и Эльзе

Похожие презентации

Логические элементы
Задачи на сравнение предметов
Мера центральной тенденции
Математика
Решение задач типа В10 МАОУ СОШ №3 г. Железнодорожный Автор: Гренкова Анна Александровна
Физминутка в картинках
Элементы математической логики. Интегральное исчисление функций одной переменной и его приложения
Усеченное гауссово моделирование. Методы моделирования дискретных свойств в Petrel
Квадратные матрицы. Определители
Геометрия сызымнарда (7 класс)
Урок математики в 4 классе Тема: «Среднее арифметическое» Автор: учитель начальных классов ГБОУ ЦО №1456 Аксенова Ольга Борисовна
Модели временных рядов. (Лекция 7)
Задания на повторение курса алгебры 9 класс
Типовые законы распределения
ЗОЛОТОЕ СЕЧЕНИЕ Сергеев Никита 10A
Практическое применение интегралов в различных областях
Элементы математической статистики
Закон больших чисел
Как измерить рост жирафа. Занимательная геометрия
Виды треугольников
Игра "Поле чудес" геометрия
Арккосинус и решение уравнения cost=а
Конструирование компетентностно-ориентированных заданий по математике
20161108_urok_46_treugolniki._vidy_treugolnikov
Презентация по математике "Свойства функций и их графики" - скачать бесплатно
Трапеция
Аналитический метод отыскания точки минимума функции двух переменных
Модуль числа. Противоположные числа
Вы можете прислать нам Вашу презентацию и мы опубликуем ее на сайте.
Обратная связь
Для правообладателей
Email: Нажмите что бы посмотреть