Реферат на тему:
Близькість
Задача. Найближча пара. На площині задано N точок. Знайти дві з них, відстань між якими найменша.
В одномірному випадку можна впорядкувати координати точок за час O(N * log N) а потім за лінійний час проглянути точки x1, x2, ..., xN обчислюючи значення xi+1 - xi, i = 1, ..., N-1.
Означення. Точа b є найближчим сусідом точки a множини S (позначається a \xF0AE\xF020b), якщо
dist(a, b) = min dist(a, c), c \xF0CE\xF020S / 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 \xF0CE\xF020S1 та q \xF0CE\xF020S2. Рекурсивним чином розв’язуємо задачу про найближчу пару для множин S1 та S2 і отримаємо дві пари точок {p1, p2} та {q1, q2}, які представляють найближчі пари для S1 та S2 відповідно. Позначимо через \xF064\xF020найменшу відстань, знайдену на поточний момент: \xF064\xF020= min( |p2 - p1|, |q2 - q1|). Найближчою парою у множині S буде або {p1, p2}, або {q1, q2}, або {p3, q3}, де p3 – права точка множини S1, а q3 – ліва точка множини S2 (це випливає з того, що точки p3 та q3 повинні знаходитися на відстані, яка не перевищує \xF064 від точки 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);
Двовимірний випадок. Алгоритм розділяй та пануй.
|
Скачати "Реферат на тему Близькість"
