KD-Tree, какие узлы посещаются при поиске ближайшего соседа

Учитывая эти точки (7,3), (10,5), (9,0), (5,8), (3,2), (8,1), мне нужно создать сбалансированное дерево KD, чтобы первый уровень дерева KD разбивается по оси x, и когда есть две медианы, мы выбираем «большую» в качестве корня поддерева. После его построения мне нужно перечислить узлы, которые посещаются при попытке найти ближайшего соседа точки (2,4). Вот дерево, которое я построил, используя приведенные выше пункты: Вот KD-дерево, которое я построил< /а>

Я очень запутался в поиске ближайшего соседа, и мне нужно перечислить узлы, которые посещаются, когда дерево находит точку (2,4). Пока я думаю, что он посещает (8,1) -> (7,3) -> (5,8). Но что после этого?? Какие узлы посещаются?


algorithm data-structures tree kdtree
person Lilith X    schedule 24.01.2020    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Ваше k-d дерево правильное.

Алгоритм ближайшего соседа

Поиск ближайшего соседа по дереву kd проходит по дереву, чередуя две фазы:

  1. Фаза спуска:

    • Обратите внимание на расстояние между вашей точкой ввода и текущим узлом в дереве (фактическое расстояние, а не расстояние по оси).

    • Чередуя ось x и ось y, сравните координату оси вашей точки ввода с координатой оси текущего узла в дереве, чтобы определить, к какому поддереву нужно перейти.

    • Повторяйте фазу перехода вниз, пока не достигнете нижней части дерева, затем перейдите в фазу возврата вверх.

  2. Фаза возврата:

    • Поднимитесь на один уровень. Если вы не можете подняться, вам конец.

    • Если вы уже выполнили фазу Go-down для обоих поддеревьев текущего узла, повторите Go-back-up.

    • Если фактическое расстояние до лучшего соседа, которое вы нашли на данный момент, ближе, чем расстояние по оси между вашим входным узлом и текущим узлом в дереве, повторите Go-back-up.

    • В противном случае войдите в фазу Go-down в поддереве, противоположном тому, откуда вы пришли.

Ваш пример

Вот набросок вашего дерева k-d, чтобы было понятнее:

kd эскиз дерева примера

Применяя эти шаги к вашему примеру дерева и входного узла (2,4):

  • Начните с фазы Go-down в корневом узле (8,1). Расстояние между (8,1) и входным узлом (2,4) равно 6,708, поэтому (8,1) является нашим известным ближайшим соседом. Текущей осью является x, поэтому мы сравниваем 8 и 2 и видим, что нам нужно перейти к левому поддереву.
  • Текущий узел (7,3). Расстояние между (7,3) и входным узлом (2,4) составляет 5,099, что лучше, чем предыдущее наиболее известное расстояние, поэтому (7,3) становится нашим новым ближайшим соседом. Текущей осью является y, поэтому мы сравниваем 3 и 4 и видим, что нужно перейти к правому поддереву.
  • Текущий узел (5,8). Расстояние между (5,8) и входным узлом (2,4) равно 5.000, что меньше, чем предыдущее наиболее известное расстояние, поэтому (5,8) становится нашим новым ближайшим соседом. Текущей осью является х, но мы не можем двигаться дальше вниз, поэтому мы входим в фазу возврата вверх.
  • Возвращаемся к (7,3). Текущая ось y. Расстояние по оси Y между (7,3) и входным узлом (2,4) равно |3-4| = 1, что меньше 5, расстояние до ближайшего известного на данный момент соседа. Следовательно, мы должны войти в фазу возврата вниз на другом поддереве. Это видно на рисунке: расстояние между точкой ввода (S) и (5,8) больше, чем расстояние между (S) и разделительной линией, проходящей через (7,3). Это означает, что по другую сторону разделительной линии может быть ближайший сосед.
  • Текущий узел (3,2). Расстояние между (3,2) и входным узлом (2,4) составляет 2,236, что лучше, чем ранее известное наилучшее расстояние, поэтому (3,2) становится нашим известным на данный момент ближайшим соседом. Текущей осью является x, но мы не можем двигаться дальше, поэтому мы входим в фазу Go-back-up.
  • Возвращаемся к (7,3). Текущая ось y. Мы посетили оба поддерева этого узла, поэтому повторяем фазу Go-back-up.
  • Вернемся к (8,1). Текущая ось - x. Расстояние по оси x между (8,1) и входным узлом (2,4) равно |8-2| = 6, что больше, чем расстояние до известного на данный момент ближайшего соседа, поэтому мы повторяем фазу Go-back-up. Вы снова можете видеть это на рисунке: расстояние между входной точкой (S) и текущим ближайшим соседом (3,2) меньше, чем расстояние между (S) и разделительной линией, проходящей через (8,1). Это означает, что по другую сторону разделительной линии не может быть более близкого соседа.
  • Мы не можем подняться выше, так что мы закончили.

Мы посетили следующие узлы: (8,1), (7,3), (5,8), (7,3), (3,2), (7,3), (8,1). Ближайшим соседом, которого мы нашли, был (3,2) с расстоянием 2,236.

person f9c69e9781fa194211448473495534    schedule 12.02.2020