K-d tree: алгоритм поиска ближайшего соседа с управляемым псевдокодом

Псевдокод для поиска ближайшего соседа (NN) в Википедии мне не подходит. Еще несколько сообщений с реализациями, но они, похоже, зависят от языка. Поэтому мне трудно понять, как работает поиск NN. Эта диаграмма взята из https://www.cs.cmu.edu/~ckingsf/bioinfo-lectures/kdtrees.pdf. И я пытаюсь понять это в конкретном случае, скажем, точка запроса Q = (52,52). Предположим, что два dim - это (x, y), и корневой уровень разделен на x-dim. введите описание изображения здесь

Поиск NN:

Сначала я спускаюсь от корня к листу, как будто пытаюсь вставить Q; и при этом лист будет (55,1). Обновите (глобальную) переменную current_best с INFINITY до (55-52) 2 + (1-52) 2 = 2610.

Затем я перехожу к (70,70) и обновляю current_best с 2610 до 18 2 +18 2 = 648. Так как это дает лучшее расстояние, мы должны исследовать это поддерево: это правильное понимание?

Кроме того, мы видим, что узел (60,80) не дает лучшего результата (т.е. нет обновления для current_best).

В процессе дальнейшего продвижения мы обнаруживаем, что root (51,75) дает еще лучший результат (current_best получает значение 530). Итак, исходя из моего понимания, мы должны проверить это другое поддерево.

(25,40) не дает лучшего результата. Я понимаю, что нам все еще нужно проверить поддерево (25,40). Однако в этом случае, поскольку этот узел использует y-dim, и поскольку Qy> 40, нам нужно проверить только правое поддерево (с корнем (35,90)): это правильное понимание?

Короче говоря, я вижу, что если узел обеспечивает лучший результат для current_distance, мы должны проверить оба дочерних узла; и если узел НЕ обеспечивает лучший результат, все, что мы можем сделать, это игнорировать одно поддерево, но необходимо исследовать другое поддерево на основе условия (разделение гиперплоскости по определенному измерению). Это правильное понимание?

Наконец, я очень признателен любому, кто предоставит управляемый псевдокод для поиска NN для Kd-дерева


algorithm data-structures nearest-neighbor kdtree
person KGhatak    schedule 14.08.2019    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Представьте себе точку цели и диск вокруг нее с радиусом, равным наименьшему найденному на данный момент расстоянию (изначально бесконечность).

Вы находитесь у корня дерева, которое разделяет плоскость на две полуплоскости. Сделайте радиус равным минимуму текущего радиуса и расстояния от цели до корня. Затем перейдите к полуплоскостям, которые пересекают диск, если у корня есть сыновья.

Обязательно следите за тем, какой корень достиг минимума.

Visit(root):
    d= distance(target, root)
    if d < r:
        r= d
        closest= root

    if root.left and root.x - target.x < r:
        Visit(root.left)
    if root.right and target.x - root.x < r:
        Visit(root.right)

Внимание: проверка полуплоскости выполняется на x или y в зависимости от политики выбора оси, которую вы используете.

person Yves Daoust    schedule 14.08.2019
comment
@ Yves Daoust - По этому алгоритму мы исследуем поддерево с корнем (10,30) - похоже, в этом нет необходимости. Это моя трассировка для цели (52,52): посещение (51,75) установит r = 24. Тест (root.x - target.x ‹r, т.е. 51-52‹ 24) завершается успешно, и вызывается посещение (25,40). visit (25,40) не обновляет r, но успешно проходит тест (root.y - target.y ‹r, т.е. 40-52‹ 24). Таким образом, он вызывает визит (10,30). Я что-то упускаю! - person KGhatak; 14.08.2019
comment
@KGhatak: откуда ты знаешь, что это не нужно? - person Yves Daoust; 14.08.2019
comment
@ Ив Дауст - Плохо, это действительно необходимо. Если бы за углом была точка (51,40), то в противном случае она была бы упущена. Спасибо, что указали на это. - person KGhatak; 14.08.2019
comment
@KGhatak: на самом деле вы можете связать с каждым корнем прямоугольник, который он контролирует. После разделения у вас есть два новых корня, которые контролируют каждый подпрямоугольник. И вам нужно посетить каждый прямоугольник, который пересекает текущий диск. В качестве оптимизации вы можете использовать эвристику ближайшего первого. - person Yves Daoust; 14.08.2019
comment
@KGhatak Это нормально, но мне нравится использовать приоритетную очередь, чтобы сначала следовать наиболее многообещающему пути, например: stackoverflow.com/questions/41306122/ - person Matt Timmermans; 16.08.2019
comment
@ Мэтт Тиммерманс - Я не могу понять, как приоритетная очередь используется в наших интересах. Игнорируем ли мы вставку дочернего элемента, если расстояние до него больше текущего максимума. Было бы полезно добавить эту ясность (или мне что-то не хватает) - person KGhatak; 17.08.2019