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

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

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

Содержание слайда: РАНДОМИЗИРОВАННЫЕ АЛГОРИТМЫ В ЗАДАЧАХ ВЫЧИСЛИТЕЛЬНОЙ ГЕОМЕТРИИ Рандомизированная пошаговая сортировка Дано n чисел, которые нужно отсортировать. Схема сортировки: После i-ого из n шагов (1 < i < n) имеем i вставленных чисел в отсортированном списке. Эти i отсортированных чисел разобьют ранги (n-i) еще не отсортированных чисел на (i+1) интервалов. (i+1)-ый шаг состоит в выборе одного из (n-i) еще не отсортированных чисел случайным образом и вставки его в отсортированный список.

Содержание слайда: Рандомизированная пошаговая сортировка

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

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

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

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

Содержание слайда: Пример работы алгоритма

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

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

Содержание слайда: Построение произвольного треугольника

Содержание слайда: Нахождение центра масс треугольника

Содержание слайда:

Содержание слайда: По шаговое описание (продолжение) 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); }

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

Содержание слайда: Добавление новой вершины

Содержание слайда: Построенная выпуклая оболочка

Содержание слайда: Теорема: Среднее время работы описанного выше рандомизированного алгоритма для вычисления выпуклой оболочки n точек на плоскости - О(n log2 n). Теорема: Среднее время работы описанного выше рандомизированного алгоритма для вычисления выпуклой оболочки n точек на плоскости - О(n log2 n).