.

Близькість (реферат)

Язык: украинский
Формат: реферат
Тип документа: Word Doc
0 1128
Скачать документ

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

Близькість

Задача. Найближча пара. На площині задано 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

Нашли опечатку? Выделите и нажмите CTRL+Enter

Похожие документы
Обсуждение

Оставить комментарий

avatar
  Подписаться  
Уведомление о
Заказать реферат!
UkrReferat.com. Всі права захищені. 2000-2020