Комбинаторные алгоритмы вычислительной геометрии Рандомизированный алгоритм построения выпуклой оболочки

Сентябрь 3, 2022

Главная
Алгебра
Комбинаторные алгоритмы вычислительной геометрии Рандомизированный алгоритм построения выпуклой оболочки

Содержание

2. Комбинаторные алгоритмы вычислительной геометрии Рандомизированный алгоритм построения выпуклой оболочки Рандомизированные геометрические алгоритмы Рандомизированная пошаговая конструкция: n
3. РАНДОМИЗИРОВАННЫЕ АЛГОРИТМЫ В ЗАДАЧАХ ВЫЧИСЛИТЕЛЬНОЙ ГЕОМЕТРИИ Рандомизированная пошаговая сортировка Дано n чисел, которые нужно отсортировать. Схема
4. Рандомизированная пошаговая сортировка
5. Рандомизированная пошаговая сортировка Какая работа требуется, чтобы сохранить указатели на каждое число? Мы вставляем число х,
6. Рассмотрим работу, проделанную на i-ом шаге Обратный анализ: представим, что алгоритм выполняется назад, начиная с того,
7. Работана i-ом шаге Каково ожидаемое число указателей, которые должны быть обновлены на этом шаге? Так как
8. Рандомизированный алгоритм построения выпуклой оболочки S – множество всех точек на плоскости; conv(S) – выпуклая оболочка
9. Пример работы алгоритма 1.
10. Рандомизированный алгоритм построения выпуклой оболочки
11. Пошаговое описание 1. Построить выпуклую оболочку из трех точек conv(S3). 2. Найти точку р0 во внутренней
12. 2. Построение произвольного треугольника
13. Нахождение центра масс треугольника 3. центр масс треугольника
14. 4.
15. По шаговое описание (продолжение) 4. ПОКА (S\Si-1 не пусто) { Выбрать случайным образом точку pi из
16. Нахождение соседних вершин для выбранной точки 5. выбранная точка правая соседняя вершина левая соседняя вершина
17. Добавление новой вершины 6.
18. Построенная выпуклая оболочка 7.
20. Скачать презентацию

Слайд 2

Комбинаторные алгоритмы вычислительной геометрии Рандомизированный алгоритм построения выпуклой оболочки Рандомизированные геометрические алгоритмы

Рандомизированная пошаговая конструкция: n объектов, составляющих входные данные к задаче, рассматриваются по одному в каждый момент времени в произвольном порядке, и вычисляется результат воздействия каждого добавленного объекта на решение задачи. Для многих геометрических задач этот подход похож на другие известные алгоритмы, за исключением того, что в них обычно объекты обрабатываются в порядке, существующем на входе, а не в произвольном порядке.

Слайд 3

РАНДОМИЗИРОВАННЫЕ АЛГОРИТМЫ В ЗАДАЧАХ ВЫЧИСЛИТЕЛЬНОЙ ГЕОМЕТРИИ
Рандомизированная пошаговая сортировка
Дано n чисел, которые

нужно отсортировать.
Схема сортировки:
После i-ого из n шагов (1 < i < n) имеем i вставленных чисел в отсортированном списке.
Эти i отсортированных чисел разобьют ранги (n-i) еще не отсортированных чисел на (i+1) интервалов.
(i+1)-ый шаг состоит в выборе одного из (n-i) еще не отсортированных чисел случайным образом и вставки его в отсортированный список.

Слайд 4

Рандомизированная пошаговая сортировка

Слайд 5

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

Мы вставляем число х, указатель которого указывает на интервал I.
При вставке х, мы имеем три задачи:
найти все числа, указатели которых указывают на I;
(2) обновить указатели всех чисел, чьи указатели указывают на I;
(3) удалить указатель от х к I.

Слайд 6

Рассмотрим работу, проделанную на i-ом шаге
Обратный анализ:
представим, что алгоритм

выполняется назад, начиная с того,
что уже имеется отсортированный список.
При анализе i-ого шага прямого алгоритма мы представляем, что удаляется одно из i чисел в
отсортированном списке и обновляются указатели.
Работа по обновлению указателей в этом случае такая же, как если бы алгоритм выполнялся вперед как обычно.
Ключевой момент в обратном анализе:
так как в первоначальном алгоритме числа были добавлены в произвольном порядке,
то в обратном анализе мы можем принять, что каждое число в отсортированном списке равновероятно может быть удалено на этом шаге.

Рандомизированная пошаговая сортировка

Слайд 7

Работана i-ом шаге
Каково ожидаемое число указателей, которые должны быть обновлены

на этом шаге?
Так как у нас i интервалов и (n-i+1) указателей, оставшихся после удаления, то ожидаемое число указателей, которые были изменены на i-ом шаге - О((n-i)/i), которое есть О(n/i).
Просуммируем проделанную работу по всем шагам и получим верхнюю границу математического ожидания полной работы. Так как
где γ - константа Эйлера, то получаем O( ) =
= О(n lоg n).

Рандомизированная пошаговая сортировка

Слайд 8

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

на плоскости;
conv(S) – выпуклая оболочка множества S;
Для упрощения предполагаем, что в S нет трех точек лежащих на одной прямой

Слайд 9

Пример работы алгоритма
1.

Слайд 10

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

Слайд 11

Пошаговое описание
1. Построить выпуклую оболочку из трех точек conv(S3).
2. Найти

точку р0 во внутренней области conv(S) - это центр масс треугольника conv(S3).
3. Для каждой точки p определить ребро conv(S3), пересекаемое отрезком pp0, и сформировать двунаправленный указатель от р на ребро и обратно. При это исключить из дальнейшего рассмотрения точки, находящиеся внутри conv(S3).

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

Слайд 12

2.
Построение произвольного треугольника

Слайд 13

Нахождение центра масс треугольника
3.
центр масс
треугольника

Слайд 14

4.

Слайд 15

$По шаговое описание (продолжение) 4. ПОКА (S\Si-1 не пусто) { Выбрать$

По шаговое описание (продолжение)
4. ПОКА (S\Si-1 не пусто) {
Выбрать случайным образом

точку pi из S\Si-1;
Найти в conv(Si-1) вершину v1, которая является левой соседней (опорной) для pi в conv(Si). В процессе поиска запомнить в списке recheck указатели от удаляемых ребер;
Найти в conv(Si-1) вершину v2, которая является правой соседней (опорной) для pi в conv(Si), дополнив при этом список recheck указателями от удаляемых ребер;
Вставить pi в выпуклую оболочку, сформировав conv(Si);
Для каждой точки , указатель на которую содержится в списке recheck, обновить её указатель на ребро conv(Si), пересекаемое отрезком рр0, указав его на [pi,v1] или [pi,v2]. При этом исключить из дальнейшего рассмотрения точки, которые попадают внутрь conv(Si);
}

Слайд 16

Нахождение соседних вершин для выбранной точки
5.
выбранная
точка
правая соседняя
вершина
левая соседняя
вершина

Слайд 17

Добавление новой вершины
6.

Слайд 18

Комбинаторные алгоритмы вычислительной геометрии Рандомизированный алгоритм построения выпуклой оболочки

Содержание

Комбинаторные алгоритмы вычислительной геометрии Рандомизированный алгоритм построения выпуклой оболочки Рандомизированные геометрические алгоритмы

РАНДОМИЗИРОВАННЫЕ АЛГОРИТМЫ В ЗАДАЧАХ ВЫЧИСЛИТЕЛЬНОЙ ГЕОМЕТРИИРандомизированная пошаговая сортировкаДано n чисел, которые

Рандомизированная пошаговая сортировка

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

Рассмотрим работу, проделанную на i-ом шаге Обратный анализ: представим, что алгоритм

Работана i-ом шаге Каково ожидаемое число указателей, которые должны быть обновлены

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

Пример работы алгоритма1.

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

Пошаговое описание 1. Построить выпуклую оболочку из трех точек conv(S3).2. Найти

2.Построение произвольного треугольника

Нахождение центра масс треугольника3.центр масс треугольника

4.

По шаговое описание (продолжение)4. ПОКА (S\Si-1 не пусто) {Выбрать случайным образом

Нахождение соседних вершин для выбранной точки5.выбранная точкаправая соседняявершина левая соседняявершина

Добавление новой вершины6.

Построенная выпуклая оболочка7.

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

РАНДОМИЗИРОВАННЫЕ АЛГОРИТМЫ В ЗАДАЧАХ ВЫЧИСЛИТЕЛЬНОЙ ГЕОМЕТРИИ
Рандомизированная пошаговая сортировка
Дано n чисел, которые

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

Рассмотрим работу, проделанную на i-ом шаге
Обратный анализ:
представим, что алгоритм

Работана i-ом шаге
Каково ожидаемое число указателей, которые должны быть обновлены

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

Пример работы алгоритма
1.

Пошаговое описание
1. Построить выпуклую оболочку из трех точек conv(S3).
2. Найти

2.
Построение произвольного треугольника

Нахождение центра масс треугольника
3.
центр масс
треугольника

По шаговое описание (продолжение)
4. ПОКА (S\Si-1 не пусто) {
Выбрать случайным образом

Нахождение соседних вершин для выбранной точки
5.
выбранная
точка
правая соседняя
вершина
левая соседняя
вершина

Добавление новой вершины
6.

Построенная выпуклая оболочка
7.