Пошук сусідів в метричному просторі
Loading...
Date
2020
Authors
Мазуркевич, Віра
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Однією з відомих проблем пошуку, що розглядаються для метричних просторів є проблема пошуку найближчого сусіда. Для заданого метричного простору (U, D) і заданої підмножини S множини точок U проблема пошуку найближчого сусіда полягає в тому, щоб побудувати структуру даних для S, щоб для точки q можна було швидко знайти точку s ∈ S, для якої відстань D(s, q) є мінімальною. В курсовій роботі розглядаються різні підходи до цієї проблеми. Підходи залежать як від властивостей метричного простору, зокрема від розмірності метричного простору, так і від потужності множини S. Крім того, є декілька варіацій задачі пошуку найближчого сусіда, які розглянуті нижче. Останніми роками було запропоновано декілька структур даних, які, очевидно, є зручними для просторів і їх підмножин з невеликої розмірності та (або) невеликою кількістю точок. Саме такі підходи розглядаються в курсовій роботі.
Description
Keywords
пошук сусідів, метричний простір, математика, алгоритм Орчарда, AESA, метричне дерево, бакалаврська робота