Рандомізований алгоритм
Міністерство освіти РФ
Санкт-Петербурзький державний університет
Рандомізований алгоритм побудови опуклої оболонки
Постановка задачі:
Розробити та написати програму рандомізованого алгоритму побудови опуклої оболонки, за вихідними даними з дипломної роботи. Поліпшити візуалізацію алгоритму. Додати підрахунок часу виконання алгоритму.
Позначимо опуклу оболонку множини точокSчерезconv(S). Кордонconv(S)утворює опуклий багатокутник, вершини якого - підмножинаS. Щоразу, коли немає небезпеки плутанини, ми будемо ставитися до цього багатокутника як доconv(S). обмежує)conv(S).Результат повинен бути представлений у вигляді списку, що містить точкиS, які є вершинамиconv(S), перераховані в порядку проти вартовий стрілки з їхньої появі в багатокутнику; Початкова точка для списку може бути довільною. Для визначеності, будемо вважати, що перша точка в цьому упорядкуванні - точка з S , що має найменшуx- координату. Для простоти припускаємо, що у S немає трьох точок, що лежать на одній прямій. При реалізації цього припущення можна відмовитися.
Покажемо, як рандомізована покрокова конструкція, описана вище (у розділі 3.1) у контексті сортування, може застосовуватися до цього завдання.
Алгоритм спочатку випадково переставляє точки у вхідній множиніS. Нехайpi–i-а точка в цьому випадковому упорядкуванні (1 ≤i≤n).НехайSi- набір p1, …,pi>. Потім алгоритм продовжується на кроках. Післяi-ого кроку, алгоритм обчислитьconv(Si). Наi-му кроці доconv(Si-1)додаєтьсяpi, формуючиconv(Si). Тепер визначимо подробиці цього кроку модифікації.
нехай ми завжди зберігаємо крапку у внутрішній ділянціconv(S); зокрема ми могли б використовувати для цієї мети центр масconv(S3)(який може бути обчислений за постійний час). Позначимо цю точкуp0. Також післяi-ого кроку ми маємо список, що містить вершиниconv(Si). Крім того, для простоти опису ми вважаємо, що цей список також містить ребра, що з'єднують наступні вершини в цьому списку (цього можна легко уникнути в реалізації з незначною додатковою роботою). НехайS\Si-безліч точок, які повинні бути додані післяi-ого кроку, 3 ≤i≤ (n-1). Для кожної точкиpS\Si, ми зберігаємо (двонаправлений) покажчик відpна бікconv(Si), що перетинається променем, який виходить зp0і проходить черезp. Ми говоритимемо, щоpперетинаєдане реброconv(Si). Таким чином, якщо дано будь-яке реброconv(Si), ми можемо перерахувати всі точкиp, які перетинають це ребро в часі , що лінійно залежить від числа таких точок.
Визначивши структури даних, опишемо дії, які потрібні оновлення цих структур на кожному кроці. Точкаpi, вставлена наi-му кроці, знаходиться або всередині, або позаconv(Si-1). Використовуючи відрізокpip0і пов'язаний покажчик, ми завжди можемо визначити положенняpi(наше припущення, що жодні три точки не є колінеарними, перешкоджає можливості знаходженняpiна кордоніconv(Si-1)). Якщоpiзнаходиться всерединіconv(Si-1), ми видаляємо покажчик відpiі переходимо до кроку (i+1). Інакше, якщоpiзнаходиться позаconv(Si-1), ми повинні оновити список, являє собою багатокутник, що обмежує оболонку. Вершиниconv(Si-1)поділяються на три множини при додаванніpi:
1. Вершиниconv(Si-1), які мають бути видалені, тому що вони не вершиниconv(Si).
3. Вершиниconv(Si-1), які залишаються вconv(Si>)з їхніми відповідними ребрами.
Зрозуміло, що крайні точки ребра, перетнутого відрізкомpip0, відносяться до (1) або (2). Відходячи від(в обидві сторони) за списком вершин, що представляєconv(Si-1), ми можемо виявити вершини типів (1) та (2). Ми робимо так у часі, що лінійно залежить від числа таких вершин. Поки ми так робимо, ми виявляємо точкиS\Si, які перетинають вже віддалені ребра, і оновлюємо їх покажчики, вказуючи їх або на реброpiv1, аборiv2. Це займає постійний час (оскільки ми повинні перевірити лише два ребраpiv1іpiv2) для кожної точки зS\Si, покажчик якої має бути оновлений (рис. 5).
Мал. 5: Випукла оболонкаconv(Si-1). При додаванніpiдоconv(Si-1)вершиниsіtвидаляються, і покажчик для точкиqмає бути оновлений, тоді як дляr– ні.
Яка повна робота виконана наi-му кроці? Вартість видалення ребраconv(Si-1)рівноцінна вартості його створення, так як ребро може бути видалено лише одного разу після створення. Так як тільки два ребра створюються на кожному кроці, загальна кількість цих створень/видалень ребер (по всіх кроках) - у гіршому випадку 2n.
Що стосується вартості оновлення покажчиків наi-му кроці, тоце число точокpзS\Si,таких, щоpp0перетинає ребро, яке видаляється на цьому кроці. Щоб обмежити математичне очікування цієї випадкової величини, ми звертаємося до зворотного аналізу. Тобто уявімо, що алгоритм виконується назад, і видалятимемо точкуconv(Si\S3),щоб сформуватиconv(Si-1). Тоді число покажчиків, що оновлюються наi-му кроці початкового алгоритму, таке саме, як число видалених на відповідному кроці зворотного алгоритму. Покажемо, що очікуване число оновлюваних покажчиків єO(n/i) залежно від будь-якої фіксованої множиниSi\S3, з якого ми видаляємо випадкову точку на зворотному кроці. Так як ця верхня межа має силу для будь-якої множини зiточок, залежність від конкретної множиниSi\S3можна не брати до уваги.
Для точкиpS\Siнехайep– реброconv(Si), що перетинаєтьсяpp0. Імовірність того, що покажчикpоновлено - точно ймовірність того, щоepвидалено в результаті кроку видалення. Реброepвидаляється, якщо одна з двох його вершин видаляється на зворотному кроці. Так як точка, що видаляється зSi, обрана рівномірно з (i-3)точок зSi\S3, то ця ймовірність єO(1/i). Очікувана кількість оновлених покажчиків -O((n-i)/i), так що повна робота виконана на цьому кроці єO(n/i). Ключовим моментом тут є те, що на кроці видалення зворотного алгоритму ми видаляємо випадкову точкуSi, а не випадкову вершинуconv(Si).Тепер використовуємо лінійність математичного очікування, щоб обмежити середній час роботи алгоритмуO(n log n).
Теорема:Середній час роботи описаного вище рандомізованого алгоритму для обчислення опуклої оболонки n точок на площині - O(n log n).
Середній час роботи даного алгоритму асимптотично те саме, що час деяких відомих детермінованих алгоритмів опуклої оболонки, зокрема алгоритму Грехема, розглянутого вище, і відповідає його нижній оцінці.
У ході виконання курсового проекту з спідників було відновлено програму, що реалізує побудову опуклої оболонки за допомогою рандомізованого алгоритму.
За допомогою меню «Файл» можна зберігати, завантажувати та очищати безліч точок.
За допомогою меню «Управління» можна застосувати алгоритм побудови опуклої оболонки до багатьох точок. За допомогою підпункту «По кроках» можна простежити за кожним кроком роботи алгоритму. Підпункт «Повернутись на початок» дозволяє привести алгоритм у вихідний стан.
Підпункт "Сгенерувати" дозволяє згенерувати безліч точок за заданими законами розподілу.
За допомогою підпункту «Запуск» можна застосуватиалгоритм побудови опуклої оболонки до безлічі точок і подивитися кількість кроків і час, за який був побудований опуклий багатокутник.
Додавання та зміни у програмі:
Оптимізовано код алгоритму знаходження опуклої оболонки
Русифіковані пункти меню
Поліпшено візуалізацію алгоритму (додано показ вершин і ребер, що обробляються в даний момент)
Додано обчислення часу роботи алгоритму.
Розподіл обов'язків під час роботи над програмою
Бондарєв А. – написання алгоритму програми.
Ільїна О.К. - Написання інтерфейсу до програми.
Добряков М.М. - Написання візуалізації програми.