Архитектура электронного правительства: Единая архитектура – это методологический подход при создании системы управления государства, который строится...
История развития хранилищ для нефти: Первые склады нефти появились в XVII веке. Они представляли собой землянные ямы-амбара глубиной 4…5 м...
Топ:
Установка замедленного коксования: Чем выше температура и ниже давление, тем место разрыва углеродной цепи всё больше смещается к её концу и значительно возрастает...
Особенности труда и отдыха в условиях низких температур: К работам при низких температурах на открытом воздухе и в не отапливаемых помещениях допускаются лица не моложе 18 лет, прошедшие...
Интересное:
Финансовый рынок и его значение в управлении денежными потоками на современном этапе: любому предприятию для расширения производства и увеличения прибыли нужны...
Уполаживание и террасирование склонов: Если глубина оврага более 5 м необходимо устройство берм. Варианты использования оврагов для градостроительных целей...
Мероприятия для защиты от морозного пучения грунтов: Инженерная защита от морозного (криогенного) пучения грунтов необходима для легких малоэтажных зданий и других сооружений...
Дисциплины:
2018-01-04 | 1024 |
5.00
из
|
Заказать работу |
|
|
Манхэттенское расстояние — это сумма расстояний по строкам и столбцам от текущего расположения костяшки до ее правильной позиции:
⇒ |
На этой схеме манхэттенское расстояние равно 4.
Линейный конфликт (Linear conflict)
Считается, что костяшка I и костяшка J находятся в линейном конфликте по строке, если они обе стоят в своей строке, но костяшка I находится левее костяшки J, хотя на самом деле должна быть справа:
⇒ |
На этой схеме I = 15, J = 13.
Мы должны подвинуть одну из костяшек со строки, поэтому можем добавить 2 к манхэттенскому расстоянию. Аналогичным образом рассматривается линейный конфликт по столбцу.
Угловые фишки (Corner tiles)
Рассмотрим правый верхний угол. Пусть «3» или «8» стоит на своей позиции, а на месте «4» — любая другая костяшка:
|
|
В таком случае, чтобы поставить «4» на место, костяшки придется подвинуть. Для этого добавим 2 к манхэттенскому расстоянию. Если «3» или «8» участвует в линейном конфликте (linear conflict), то двойка уже добавлена.
Аналогично с левым верхним и левым нижним углами. Правый нижний угол в эвристике не рассматривается, так как очень сложно скомбинировать этот случай с эвристикой «Последний ход».
|
Последний ход (Last move)
На последнем ходу мы либо двигаем костяшку «15» влево, либо «12» — вверх:
⇒ |
⇒ |
Если костяшки не находятся на требуемых позициях («15» — в крайнем правом ряду или «12» — в самой нижней строке), манхэттенское расстояние не учитывает переход через угол. Следовательно, мы можем добавить к нему 2.
Минимальное остовное дерево. Алгоритм Прима. Биномиальная куча.
Минимальное остовное дерево:
Дано дерево G=<V,E>
Задача: выкинуть ребра (оставить |V| - 1 ребро) так, чтобы граф был связным и имел минимальный возможный вес, где под весом дерева понимается сумма весов входящих в него рёбер. Тогда полученное дерево – минимальное остовное дерево.
Строим А – множество ребер
A = empty
While (A!= MST)
Ищем безопасное ребро (u,v)
A = A + (u,v)
Инвариант: На каждом шаге алгоритма А – подмножество некоторых MST (их может быть много разных)
Безопасное ребро – такое, что при добавлении его к А – инвариант сохраняется
Разрез – разбиение графа на 2 множества (два графа) – S и V\S
Разрез согласован с A, если ни одно ребро из A не пересекает разрез
Легкое ребро – ребро, пересекающее разрез и имеющее наименьший вес из таких же.
Теорема: G=(V,E) – связный, неориентированный. A лежит в E. Есть разрез (S, V\S), согласованный с A. (u,v) – легкое ребро (S, V\S). Тогда (u,v) – безопасно для А
Док-во:
Покажем, что другой ситуации не может быть.
A лежит в T = MST. (u,v) не лежит в T. Иначе - тривиально
u и v в разных сторонах разреза è существует путь из u в v (ведь это ребро не лежит в T, а связность должна выполняться). Пусть ребро, пересекающее разрез в этом пути – (x,y).
w(u,v) <w(x,y) (по условию) èw(T + (u,v) - (x,y) = T’) <= w(T), но T – minè или T’ тоже MST и (u,v) – безопасно для А (MST может быть несколько), или, в другом случае, противоречие. Чтд
|
Алгоритм Прима
Алгоритм построения минимального остовного дерева (дерево, сумма весов ребер которого минимальна)
Вход: взвешенный граф (неориентированный)
Алгоритм:
Примечания:
Сложность:
Способ представления графа и приоритетной очереди | Асимптотика |
Массив d, списки смежности (матрица смежности) | O(|V|^2) |
Бинарная пирамида, списки смежности | O(ElogV) |
Фибоначчиева пирамида, списки смежности | O(E + VlogV) |
Биномиальная куча
Описание: структура данных, реализующая абстрактный тип данных «Очередь с приоритетом», которая представляет собой набор биномиальных деревьев с двумя свойствами:
Слoжность:
Make – O(1)
Merge – O(logN)
Insert – O(log N) – где N – количество элементов в куче.
Minimum – O(log n)
ExtractMin – O(log N)
Decrease – O(log N)
Delete – O(log N)
Биномиальное дерево – дерево, которое задается рекуррентно:
Bi – это Bi-1, в котором левым сыном корня сделали дерево Bi-1.
B0 — это просто вершина.
Примеры для B0, B2, B3:
У биномиального дерева(Bk) есть ряд интересных свойств:
D(k,i) = D(k-1,i) + D(k-1,i-1) = C(k-1)I + C(k-1)(i-1) = Cki – предпоследнее равенство по индукции.
Биномиальная куча – множество биномиальных деревьев, со следующими ограничениями:
|
Хранение: корневой список (root_list), его длина, в котором будут корни биномиальных деревьев, в порядке возрастания высоты. У каждой вершины будут следующие поля:
root_list.length = O(log N), где N — количество элементов в куче, т.к. в каждом дереве 2^kвершин, то есть в двоичном представлении числа <=lognразрядов, а каждое дерево представляет собой разряд
Операции:
Make
Задача: создать пустую кучу.
Алгоритм: создаем пустой список root_list.
Сложность: O(1).
Merge
Задача: объединить 2 кучи в 1.
Алгоритм: сначала объединим корневые списки куч в 1 корневой список, поддерживая упорядоченность по degree. Алгоритм аналогичен слиянию 2-х массивов в mergeSort:
Храним по указателю на начало списков и в результирующий список записываем минимальный из них, тот откуда только что записали сдвигаем на следующий. Далее проходимся от начала до конца нового полученного корневого списка и сливаем деревья одинакового размера в 1. Могут быть случаи:
При объединении двух деревьев нужно лишь посмотреть в корне какого из них меньший ключ и сделать другое дерево левым сыном корня этого дерева.
Пример, того, что получается после объединения двух куч:
Сложность: Время работы O(root_list1.length) + O(root_list2.length) = O(log N).
За один проход (O(log N)) мы получим объединенное биномиальное дерево. Получаем, что общая сложность O(log N).
Insert
Задача: вставить новый элемент в кучу.
Алгоритм: Создаем кучу из одного элемента и объединяем с нашей кучей.
Сложность: O(1) + O(log(N)) = O(log(N)).
Minimum
Задача: найти минимум в куче.
Алгоритм: минимум находится в корневом списке, то есть, чтобы его найти нужно пройтись по корневому списку.
Сложность: O(root_list.length) = O(log(N)).
|
ExtractMin
Задача: удалить минимальный элемент.
Алгоритм: находим его при помощи Minimum. Удаляем его из корневого списка. Из перевернутого списка его детей делаем root_list для новой кучи и объединяем исходную кучу с H1.
Сложность: так как каждая операция в извлечении минимума работает за O(log N): O(log N) + O(log N) + O(log N) = O(log N)
DecreaseKey
Задача: уменьшить значение key в данной вершине.
Алгоритм: уменьшаем значение в вершине. Тогда свойство кучи будет возможно нарушено для нашей вершины и ее предка, тогда меняем их местами. Продолжаем процесс, пока наша вершина не “всплывет” на свое место. Алгоритм работает также, как аналогичный в двоичной куче.
Сложность: В худшем случае наша вершина будет всплывать до корня, то есть мы совершим O(log N) действий (вершина на каждом шаге “всплывает” на уровень выше, а высота биномиального дерева O(log N))
Delete
Задача: удалить произвольный элемент.
Алгоритм: сначала уменьшим при помощи Decrease значение в вершине до минимально возможного. А затем удалим минимальный в куче (ExtractMin).
Сложность: O(log N) + O(log N) = O(log N)
|
|
Семя – орган полового размножения и расселения растений: наружи у семян имеется плотный покров – кожура...
Биохимия спиртового брожения: Основу технологии получения пива составляет спиртовое брожение, - при котором сахар превращается...
Своеобразие русской архитектуры: Основной материал – дерево – быстрота постройки, но недолговечность и необходимость деления...
Археология об основании Рима: Новые раскопки проясняют и такой острый дискуссионный вопрос, как дата самого возникновения Рима...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!