Лекция 7_2 непересекающиеся подмножества.ppt - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Лекция 7_2 непересекающиеся подмножества.ppt, слайд №1

Лекция 7_2 непересекающиеся подмножества.ppt, слайд №2

Лекция 7_2 непересекающиеся подмножества.ppt, слайд №3

Лекция 7_2 непересекающиеся подмножества.ppt, слайд №4

Лекция 7_2 непересекающиеся подмножества.ppt, слайд №5

Лекция 7_2 непересекающиеся подмножества.ppt, слайд №6

Лекция 7_2 непересекающиеся подмножества.ppt, слайд №7

Лекция 7_2 непересекающиеся подмножества.ppt, слайд №8

Лекция 7_2 непересекающиеся подмножества.ppt, слайд №9

Лекция 7_2 непересекающиеся подмножества.ppt, слайд №10

Лекция 7_2 непересекающиеся подмножества.ppt, слайд №11

Лекция 7_2 непересекающиеся подмножества.ppt, слайд №12

Лекция 7_2 непересекающиеся подмножества.ppt, слайд №13

Лекция 7_2 непересекающиеся подмножества.ppt, слайд №14

Лекция 7_2 непересекающиеся подмножества.ppt, слайд №15

Лекция 7_2 непересекающиеся подмножества.ppt, слайд №16

Лекция 7_2 непересекающиеся подмножества.ppt, слайд №17

Лекция 7_2 непересекающиеся подмножества.ppt, слайд №18

Лекция 7_2 непересекающиеся подмножества.ppt, слайд №19

Лекция 7_2 непересекающиеся подмножества.ppt, слайд №20

Лекция 7_2 непересекающиеся подмножества.ppt, слайд №21

Лекция 7_2 непересекающиеся подмножества.ppt, слайд №22

Лекция 7_2 непересекающиеся подмножества.ppt, слайд №23

Лекция 7_2 непересекающиеся подмножества.ppt, слайд №24

Лекция 7_2 непересекающиеся подмножества.ppt, слайд №25

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Лекция 7_2 непересекающиеся подмножества.ppt. Доклад-сообщение содержит 25 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

Лекция 7.2 Лекция 7.2 Раздел: Алгоритмы на графах Тема лекции: Операции с непересекающимися подмножествами

Слайд 2

Описание слайда:

Операции с непересекающимися подмножествами Жадный алгоритм нахождения МОД (фрагмент): Vs - множество множеств Wi узлов (множество деревьев остовного леса) ********************************************************************************************** if (u и v принадлежат разным подмнож.W1 и W2 из Vs ) { Заменить W1 и W2 на W1  W2 в Vs; T := T  {e}; } ********************************************************************************************** Сначала Vs = { {v1}, {v2}, …, {vn} }. В конце Vs = { {v1,v2, …,vn}}. Используются только операции: Найти подмножество W1, такое, что u  W1, Найти подмножество W2, такое, что v  W2, Объединить W1 и W2 (получить W1  W2 )

Слайд 3

Описание слайда:

1. Простая реализация на базе массивов, 1. Простая реализация на базе массивов, т.е. подмножество – массив элементов, тогда: Поиск W1 и W2, таких, что для ребра {u, v} имеем u  W1 и v  W2  O(n) Объединение массивов – O(n1+n2). Т.о. вся обработка ребер из очереди с приоритетами даст O(m*n), что хуже, чем O( m * log m ) и при m =O(n), и при m =O(n2), т.к. O( m * log m ) = O( m * log n2 ) = O( m * log n )

Слайд 4

Описание слайда:

2. Реализация на базе массивов «быстрый поиск – медленное объединение» Пример из лекции 5. Задача о связности графа (об остовном дереве)

Слайд 5

Описание слайда:

3. Реализация на базе массивов : не очень быстрый поиск – быстрое объединение

Слайд 6

Описание слайда:

Пусть исходное множество: Пусть исходное множество: { a, b, c, d, e, f, g, h, i, j, k } Подмножества: { a, b, c }, { d, e }, { f, g, h, i, j }, { k } Имя (по «представителю») подмножества: { a , b, c }, { d, e }, { f, g, h, i, j }, { k } Пусть x - элемент, тогда Make ( x )  { val ( x ) } и x - представитель Find ( x )  имя (представитель) Например, при x = ‘k’: Make ( x ) = { k }, при x = ‘g’: Find ( x ) = h

Слайд 7

Описание слайда:

Пусть x, y – подмножества (различные!), заданные именами, тогда Union (x, y) - порождает новое подмножество (объединение) с именем x или y. Пусть x, y – подмножества (различные!), заданные именами, тогда Union (x, y) - порождает новое подмножество (объединение) с именем x или y. Например, при x = a, y = d Union (x, y) дает { a , b, c } U { d, e } в виде { a , b, c, d, e } или { a , b, c, d, e } . Например, объединить множество, содержащее u, с множеством, содержащим v: x = Find(u); y = Find(v); if x  y then Union (x, y) Какая СД для представления подмножеств эффективна?

Слайд 8

Описание слайда:

Пусть Пусть n – число операций Make (мощность базового множества) k – суммарное число операций Make, Find и Union. k  n, число операций Union  n – 1 (попарно log2 n)

Слайд 9

Описание слайда:

Слайд 10

Описание слайда:

Make, Find - O(1) Make, Find - O(1) Union – переустановка указателей на представителя; оказывается, что в худшем случае O(n2). Пример. Пусть Union (x, y) - порождает новое подмножество с именем y. for (i =1; in; i++) Make ( x(i) ); for (i =1; i < n; i++) Union ( x(i), x(i+1) );

Слайд 11

Описание слайда:

В формуляре множества дополнительно хранится число элементов. В формуляре множества дополнительно хранится число элементов. Union – более короткий список добавляется к более длинному (ссылки на представителя изменяются в коротком списке). Утверждение. Пусть система непересекающихся подмножеств сначала пуста. Далее k – суммарное число операций Make, Find и Union, а n – число операций Make. Тогда суммарная сложность есть O(k + n log2 n)

Слайд 12

Описание слайда:

Доказательство: 1) Стоимость Make, Find, сравнения размеров, сцепления списков, обновления размера – O(1) Доказательство: 1) Стоимость Make, Find, сравнения размеров, сцепления списков, обновления размера – O(1) 2) Какова стоимость обновления указателей на представителя? Зафиксируем какой-либо элемент x. Указатель от x к представителю изменяется, если только x входит в меньшее из объединяющихся подмножеств (в силу эвристики). При этом размер объединения не менее, чем вдвое превышает размер множества, включавшего x. Т.о. x участвует не более чем в log2 n «результативных» объединениях. Суммарно по всем элементам – не более O(n log2 n) изменений указателей. В итоге общая стоимость есть O(k + n log2 n) . В жадном алгоритме O(2m + (n-1) + n log2 n) = O(m + n log2 n)

Слайд 13

Описание слайда:

Замечание. Отметим, что в жадном алгоритме МОД фактически работа с внутрисписковыми указателями не нужна. Важна лишь работа с указателями на представителя! Замечание. Отметим, что в жадном алгоритме МОД фактически работа с внутрисписковыми указателями не нужна. Важна лишь работа с указателями на представителя!

Слайд 14

Описание слайда:

Реализация 2. Лес непересекающихся подмножеств { c, a, b, d } U { f, e, g } = { f, e, g, c, a, b, d } Union  O(1). Find(x)  O(n) (!!!).

Слайд 15

Описание слайда:

Эвристики: Эвристики: «Объединение по рангу» (аналог весовой эвристики) «Сжатие путей» Ранги r(x) – ранг узла х – высота поддерева с корнем x (точнее – верхняя оценка высоты…) Make (x)  r(x) = 0 Find (x) не меняет рангов (!) При Union (x, y) – дерево с меньшим рангом «подвешивается» к корню дерева с не меньшим рангом, при этом ранг нового корня изменяется (увеличивается на 1) только при равенстве рангов объединяемых подмножеств (деревьев леса)

Слайд 16

Описание слайда:

Слайд 17

Описание слайда:

Сценарий 1 for (i =1; i  n; i++) Make ( x(i) ); for (i =1; i  n; i++) Union ( x(i), x(i+1) );

Слайд 18

Описание слайда:

Сценарий 2

Слайд 19

Описание слайда:

Сценарий 2 (продолжение) На k-ом шаге в каждом из n/2k деревьев по 2k элементов, а ранг r = k. Пусть n = 2q. Тогда на q-ом шаге получим одно дерево из n элементов. Вопросы: Сколько тратится на операцию Find (в худшем случае)? Сколько всего действий (в худшем случае)?