moglobi.ru Другие Правовые Компьютерные Экономические Астрономические Географические Про туризм Биологические Исторические Медицинские Математические Физические Философские Химические Литературные Бухгалтерские Спортивные Психологичексиедобавить свой файл
страница 1


Дискретные задачи
принятия решений


НГУ  Механико – математический факультет  4 курс

Лектор: Кочетов Юрий Андреевич



http://www.math.nsc.ru/LBRT/k5/tpr.html

Лекция 1.

Задачи комбинаторной оптимизации.

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

Мотивационный пример

Компания планирует производство и продажу бандерснечей в условиях жесткой конкуренции.

Нужен метод для проверки возможности создания узлов бандерснеча с заданными техническими характеристиками.

Вы отвечаете за разработку алгоритмов.





Мрачная перспектива





Удобный выход



Но доказательство может оказаться слишком сложной задачей,


если это вообще можно доказать.

Теория NP-полных задач дает методы доказательства того, что
конкретная задача столь же трудна, как и ряд других задач, признанных очень трудными



Достойный выход

  • Проверить NP–трудность (полноту) и постараться найти.

  • Эффективные алгоритмы для частных случаев.

  • Эффективные приближенные алгоритмы.

  • Алгоритмы, работающие эффективно в среднем.

  • Итерационные методы (метаэвристики), позволяющие в асимптотике находить точное решение задачи.

  • Другие идеи, например, искать быстрые алгоритмы, гарантирующие выполнение бóльшей части ограничений задачи.

Массовая задача

Под массовой задачей (или просто задачей ) будем понимать некоторый


общий вопрос, на который следует дать ответ:

  • Есть ли в задаче гамильтонов цикл?

  • Существует ли в графе клика мощности не менее K?

Задача задается следующей информацией:

    1. списком всех ее параметров;

    2. формулировкой свойств, которым должен удовлетворять отвеет

Индивидуальная задача получается из массовой присвоением конкретных значений всем параметрам.

Алгоритмы

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

Будем выделять


  • точные алгоритмы, которые для любой индивидуальной задачи всегда дают точное решение;

  • приближенные алгоритмы с гарантированной оценкой точности;

  • аппроксимационные схемы — семейство алгоритмов, позволяющих получать решения с любой наперед заданной точностью > 0, время работы которых растет с ростом величины 1/ ;

  • итерационные методы локального поиска (метаэвритстики), для которых вероятность получить точное решение растет с ростом числа итераций;

  • быстрые конструктивные эвристики без гарантии получить точное решение или решение с заданной погрешностью.

Длина входа индивидуальной задачи

Время работы алгоритма и требующуюся память выражают в виде функции от «размера» индивидуальной задачи, т. е. объема входных данных.


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

Пример.

Для задачи коммивояжера требуется задать nn матрицу расстояний (cij).


При двоичном кодировании чисел длина входа (размер) не превышает
величины .

Полиномиальные алгоритмы

Будем говорить, что функция f(n) есть O(g(n)), если существует такая


константа c, что | f(n) |  c g(n) | для всех n  0.

Полиномиальным алгоритмом (алгоритмом полиномиальной временной сложности) называется алгоритм, у которого временная сложность равна O(p(n)), где p(n) — некоторая полиномиальная функция, а n — длина входа.



Алгоритмы, временная сложность которых не поддается подобной оценке, называются экспоненциальными.

Пример. O(n2) — полиномиальная сложность;

O(nlog n) — экспоненциальная сложность.

Сравнение полиномиальных и экспоненциальных

функций временной сложности

Функция временной сложности

Размер n

10

20

30

40

50

60

n

0,00001
сек.

0,00002
сек.

0,00003
сек.

0,00004
сек.

0,00005
сек.

0,00006
сек.

n2

0,0001
сек.

0,0004
сек.

0,0009
сек.

0,0016
сек.

0,0025
сек.

0,0036
сек.

n3

0,001
сек.

0,008
сек.

0,027 сек.

0,064 сек.

0,125 сек.

0,216 сек.

n5

0,1 сек.

3,2 сек.

24,3 сек.

1,7 мин.

5,2 мин.

13 мин.

2n

0,001
сек.

1,0 сек.

17,9 мин.

12,7 дней

35,7 лет

366
столетий

3n

0,059
сек.

58 мин.

6,5 лет.

3855
столетий

2108
столетий

1,31013
столетий

Влияние технического прогресса

Функция

временной

сложности


На современных

PC


На ЭВМ, в 100 раз
более быстрых

На ЭВМ, в 1000 раз
более быстрых

n

N1

100 N1

1000 N1

n2

N2

10 N2

31,6 N2

n3

N3

4,64 N3

10 N3

n5

N4

2,5 N4

3,98 N4

2n

N5

N5 + 6,66

N5 + 9,97

3n

N6

N6 + 4,19

N6 + 6,29

Быстрая сортировка

Сортировкой называют упорядочение множества объектов по неубыванию или невозрастанию какого-нибудь параметра.



  • Алгоритм пузырька (волновой алгоритм) — O(n2).

  • Алгоритм Фон–Неймана — O(n log n).

  • Пирамидальный алгоритм — O(n log n).

  • QuickSort и др.

Сортировка с помощью сравнений

Л
ai < aj ?

нет

да
емма 1.
Бинарное дерево высоты h
содержит не более 2h листьев.

Дерево решений:

Лемма 2. Высота любого дерева решений, упорядочивающего последовательность из n различных элементов, не менее log n!.

Доказательство. Так как результатом может быть любая из n! перестановок, то в дереве решений должно быть не менее n! листьев.
Тогда по лемме 1 высота дерева не меньше log n!. ∎

Теорема. В любом алгоритме, упорядочивающем с помощью сравнений, на упорядочивание последовательность из n элементов тратится не менее c n log n сравнений при некотором c >0 и достаточно большом n.

Доказательство. При n ≥ 4 имеем

n! ≥ n(n – 1) (n2)…( ) ≥ ,

тогда


log n! ≥ () log () ≥ () log n. ∎

Алгоритм Фон–Неймана

На вход подается последовательность чисел a(1),…, a(n). Алгоритм работает log2 n итераций. Перед началом итерации с номером k (k = 1, 2, …, log2 n) имеется последовательность a(i (1)), …, a(i (n)) тех же чисел, разбитая на группы по 2k–1 элементов (последняя группа может быть неполной). Внутри каждой группы элементы упорядочены по неубыванию. Итерация состоит в том, что эти группы разбиваются на пары соседних групп, и элементы упорядочиваются внутри этих новых в два раза больших групп. При этом используется то, что внутри исходных групп элементы уже упорядочены.





слияние за линейное время

O(m)

Упражнение. Показать, что алгоритм Фон–Неймана использует O(nlog n) сравнений.

Пирамидальный алгоритм

Два этапа:



  1. п
    a1
    остроение пирамиды: для каждого i


a2

ai
и

  1. с
    a4
    ортировка массива с помощью
    пирамиды


a2i

a2i+1



a8


Первый этап

(


ai
i, n)–операция состоит в следующем:

Сравниваем a2i и a2i+1,

п
a2i

a2i+1
усть x — меньшее из них.

Если ai > x, то меняем местами ai и x.

(j, n)–процедура: выполняем (j, n)–операцию; если aj переместилось вниз, скажем, стало a2j+1, то производим (2j +1, n)–операцию и т.д., пока наш элемент aj не остановится.

Первый этап состоит в последовательном выполнении (jn)–процедуры для j =n/2, n/2 – 1,…, 1.



Упражнение. Доказать, что первый этап требует не более 2n (i, n)–операций.

Второй этап

Н
anj+1

a1
а j-й итерации (j – 1) самых малых чисел уже найдены и лежат на «полочке» в нужном
порядке. Остальные находятся в пирамиде
(ai ≤ min(a2i, a2+1)). Итерация состоит в том, что элемент a1 из пирамиды кладется на «полку», а на его место ставится элемент a +1 из пирамиды и выполняется (1, nj)–процедура.

После выполнения n-й итерации все числа лежат на полке в полном порядке.

Время — O(n log n).

Замечание. «Полку» можно организовать прямо в пирамиде.

Сбалансированные деревья

Для массива данных требуется



  1. Найти элемент

  2. Найти k-й по порядку элемент

  3. Вставить элемент

  4. Удалить элемент

Если упорядочить массив, то 1 и 2 требуют O(log n) операций, но 3, 4 — O(n).

Если хранить данные в виде списка, то 3, 4 — O(log n), 1, 2 — O(n).

Сбалансированные деревья требуют O(log n) для 1 – 4.

Определение 1. Высотой дерева называется максимальная длина пути от корня до листа.

Определение 2.  Бинарное дерево называется сбалансированным (или AVL–деревом), если для любой его вершины высота правого
поддерева отличается от высоты левого поддерева не более чем на единицу.

Теорема. Длина ветвей в n-вершинном сбалансированном дереве
заключена между log2n и log2n.

Доказательство.


  1. Бинарное дерево высоты h не может содержать больше 2+1
    вершины, то есть n ≤ 2h + 1 или h + 1 ≥ log2 n.

  2. Наиболее ассиметричное AVL–дерево Th высоты h имеет наиболее ассиметричное AVL–дерево T–1 высоты h–1 в качестве одного из своих поддеревьев и наиболее ассиметричное AVL–дерево T–2 в качестве другого. Обозначим через n(h) число вершин в дереве Th. Тогда

n(h) = n(h–1) + n(h–2) + 1; n(0) = 1, n(–1) = 0.

Для h=3,4 можно непосредственно проверить, а затем по индукции доказать, что n(h)>  h+1, где = .

Следовательно, nn(h) >  h+1, откуда h+1 ≤ log n / log  ≈ 1,44 log n. ∎

Пусть в вершинах AVL–дерева расположены элементы массива так, что для любой вершины в левом ее поддереве расположены элементы не больше чем в данной вершине, а в правом поддереве — не меньше, чем в этой вершине.


ai



aj ≥ ai

aj ai


Пример. Поиск в AVL–дереве потребует более 25 сравнений, только если дерево состоит из не менее 196 417 вершин.

Случайные деревья

Для сбалансированного дерева длина пути из корня в лист не превышает 1,44 log n.

Для случайного дерева средняя длина пути из корня в лист составляет 1,39 log n, но в худшем случае может оказаться равной n.

Для сбалансированного дерева средняя длина пути составляет c  log  n,


c ≈1,04.

Включение новой вершины в AVL–дерево

При добавлении новой вершины vnew к AVL–дереву мы «скатываем» ее от корня вдоль веток и получаем новый лист (висячую вершину).


Дерево остается бинарным, но баланс может нарушиться. Эти нарушения могут возникнуть только у вершин, лежащих на пути от корня к новой вершине.

Будем последовательно подниматься от новой вершины к корню и восстанавливать баланс, если это необходимо.

Пусть v  — самая нижняя вершина дисбаланса, то есть наиболее удаленная от корня вершина такая, что ее поддерево с вершиной vnew имеет высоту k+2, а другое поддерево — высоту k:

Будем восстанавливать баланс в v  следующим образом. Если первые два шага на (единственном пути) от v к vnew делаются в одном направлении (оба вправо, или оба влево), то применяем правило простого вращения (ППВ).



Если первые два шага делаются в разных направлениях, то


применяем правило двойного вращения (ПДВ):



Удаление вершины

На место удаленной вершины v ставим либо самую правую вершину vrL левого поддерева, либо самую левую вершину vLr правого поддерева

Нюанс. Каждая из вершин vrL и vLr может быть либо висячей, либо
предвесячей, то есть имеющей в качестве потомков лишь одну вершину
(разумеется, висячую):


Если на место удаленной вершины встает предвисячая вершина y, то ее (вершины y) потомок x подключается к ее предку z:




Итак, можно считать, что всегда удаляем лист. Последовательно поднимаемся от удаленной вершины v к корню и исправляем структуру дерева, если необходимо.

Пусть к текущей вершине x на пути от v к корню мы пришли справа по короткой ветке. Тогда возможно три случая:

а) В вершине y высоты поддеревьев равны:



б) В вершине y высота левого поддерева больше высоты правого поддерева:



в) В вершине y высота левого поддерева меньше высоты правого поддерева



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



Пример. Построить последовательность AVL–деревьев для данных, поступающих в следующем порядке: 29, 19, 9, 1, 4, 14, 39, 18, 36, 24, 15, 12.

Удалить из полученного дерева 24, а затем 19.






Упражнение. Построить последовательность AVL–деревьев для данных, поступающих в следующем порядке: 15, 7, 17, 5, 4, 3, 56, 23, 22, 6, 10, 25, 26.

Удалить из полученного дерева 6 и 10, а затем 15 и 25.




страница 1
скачать файл


Смотрите также: