Реферат Близькість Задача. Найближча пара. На площині задано В точок. Знайти дві з них, відстань між якими найменша. В одномірному ви

СкачатиСкачать (DOC|ZIP):
Близькість Задача. Найближча пара. На площині задано В точо

Реферат на тему:

Близькість

Задача. Найближча пара. На площині задано N точок. Знайти дві з них, відстань між якими найменша.

В одномірному випадку можна впорядкувати координати точок за час O(N * log N) а потім за лінійний час проглянути точки x1, x2, ..., xN обчислюючи значення xi+1 - xi, i = 1, ..., N-1.

Означення. Точа b є найближчим сусідом точки a множини S (позначається a → b), якщо

dist(a, b) = min dist(a, c), c ∈ S / a.

Відношення найближчий сусід на множині точок

Задача. Єдиність елементів. Дано N дійсних чисел. Чи є серед них два рівних числа?

Теорема. Задача єдиність елементів лінійно зводиться до задачі найближча пара.

Доведення. Дано множину дійсних чисел {x1, x2, ..., xN}. Розглядаємо їх як точки на прямій y = 0 та намагаємося знайти найближчу пару точок. Якщо відстань між найближчою парою точок не дорівнює нулю, то усі числа різні.

Задача. Найближчі сусіди. На площині задано N точок. Знайти найближчого сусіда для кожної точки множини.

Задача. Евклідове мінімальне остове дерево (ЕМОД). На площині задано N точок. Побудувати дерево, вершинами якого є всі задані точки і сумарна довжина всіх ребер якого мінімальна.

Теорема. Задача сортування за лінійний час зводиться до задачі ЕМОД.

Доведення. Розглянемо кожне число xi множини {x1, x2, ..., xN} як точку (xi, 0) на площині та будуємо ЕМОД. В побудованому дереві вершини, які відповідають числам xi та xj, сполучені ребром тоді і тільки тоді, коли утворюють пару послідовних чисел у впорядкованій множині. Розв’язком задачі ЕМОД є список з N - 1 пар (i, j), кожна з яких визначає ребро дерева. Цей список можна впорядкувати за лінійний час.

Задача. Триангуляція. На площині задано N точок. Сполучити їх неперетинаючими відрізками так, щоб кожна область всередині опуклої оболонки цієї множини точок була трикутником.

Теорема. Задача сортування за лінійний час зводиться до задачі триангуляції.

Доведення. Розташуємо N-1 точку з множини {x1, x2, ..., xN} на одній прямій, а одну точку не на прямій. Триангуляція множини точок може бути проведена єдиним чином:

Список ребер, що породжується алгоритмом триангуляції, можна використати для отримання впорядкованого списку чисел xi за час O(N)

Найближча пара

Одномірний випадок. Алгоритм розділяй та пануй.

Припустимо, що точка m розбиває множину S на дві підмножини S1 та S2, при чому p < q для всіх p ∈ S1 та q ∈ S2. Рекурсивним чином розв’язуємо задачу про найближчу пару для множин S1 та S2 і отримаємо дві пари точок {p1, p2} та {q1, q2}, які представляють найближчі пари для S1 та S2 відповідно. Позначимо через δ найменшу відстань, знайдену на поточний момент: δ = min( |p2 - p1|, |q2 - q1|). Найближчою парою у множині S буде або {p1, p2}, або {q1, q2}, або {p3, q3}, де p3 – права точка множини S1, а q3 – ліва точка множини S2 (це випливає з того, що точки p3 та q3 повинні знаходитися на відстані, яка не перевищує δ від точки m).

Blpara (S, Begin, End)

if Begin = End then return MAXINT;

if (Begin - End) = 1 then return S[End] - S[Begin];

Mediana = (Begin + End) / 2;

ResS1 = blpara(Begin, Mediana);

ResS2 = blpara(Mediana + 1, End);

Delta = S[Mediana + 1] - S[Mediana ];

return min (ResS1, ResS2, Delta);

Двовимірний випадок. Алгоритм розділяй та пануй.

Розіб’ємо множину S на дві підмножини S1 та S2 так, щоб кожна точка S1 лежала лівіше довільної точки S2. Тобто множина точок розбивається на частини вертикальною прямою l, що визначається медіаною множини S по x координаті. Розв’язавши задачу для S1 та S2, отримаємо числа δ1 та δ2 – мінімальні відстані для множин S1 та S2 відповідно. Покладемо δ = min (δ1, δ2).

Якщо найближчу пару утворюють точки p ∈ S1 та q ∈ S2, то відстані від p та q до l не перевищують δ. Позначимо через P1 та P2 дві вертикальні смуги шириною δ, розташовані відповідно зліва та справа від l. Тоді p ∈ P1 та q ∈ P2. Ми повинні знайти всі точки q ∈ P2, віддалені від p не більш ніж на δ. Всі такі точки повинні знаходитися в прямокутнику R розміром δ × 2δ. Відомо, що жодна пара точок в P2 не знаходиться на відстані, меншій за δ. Максимальна кількість точок, яку можна розмістити в такому прямокутнику, дорівнює 6. Оже для кожної точки з P1 необхідно дослідити не більше шести точок з P2. На кроці злиття розв’язків підзадач необхідно виконати не більш ніж 6 * N/2 = 3N порівнянь.

1. Розбити S на дві підмножини S1 та S2 вертикальною прямою l, яка ділить множину S навпіл.

2. Рекурсивно знайти відстані для найближчих пар δ1 та δ2.

3. δ = min (δ1, δ2).

4. Нехай P1 – множина точок з S1, що лежать в смузі на віддалені δ від розділяючої прямої l, а P2 – аналогічна підмножина в S2. Спроеціювати P1 та P2 на l та впорядкувати проекції за y координатою. Нехай P1* та P2* – відповідні впорядковані послідовності.

5. Злиття можна виконати, переглядаючи P1* і для кожної точки з P1* досліджувати точки з P2*, що знаходяться на відстані не більшій за δ. Нехай δl – найменша відстань між парою точок, знайдена в ході виконання процедури злиття.

6. δS = min (δ, δl).

Теорема. Найкоротша відстань, яка визначається N точками на площині, може бути знайдена за час O(N * log N), який є оптимальним.

СкачатиСкачати: Близькість Задача. Найближча пара. На площині задано В точо


Схожі реферати:
  • Розвиток категорії простору (реферат)
  • Перші та Другі Олімпійські ігри Однією з найвизначніших культурних подій давньої Греції були Олімпійські ігри, форум згоди між усіма грецьким
  • Формування, використання і структура масиву штатного розпису підприємства При організації раціонального
  • КУРСОВА РОБОТА на тему: Шляхи удосконалення порядку складаня, розгляду, затвердження місцевих бюджетів ПЛАН ВСТУП 1. С
  • Призиденство України (реферат)
  • Заправні перші страви Заправними називають такі перші страви, які готують на бульйонах, відварах або во
  • Особливості контролю знань при викладанні комп ютерних дисциплін в умовах кмсонп Розглянуто методичні пере
  • РПС. Економічна характеристика Полтавської області (курсова)
  • “Соціологія та психологія особистості. Проблеми адаптації людини до сучасної дійсності” Що таке особист




  • Скористайтеся пошуком:
    Loading

    Пошук :

    0.029244