Уточнение алгоритма ближайшего соседа 2d дерева

Я пытаюсь реализовать рекурсивный алгоритм ближайшего соседа для 2d-дерева. Рекурсия (и раскручивающаяся рекурсия) все еще сбивает меня с толку, и лучший псевдокод, который я нашел, взят из этого вопроса StackOverflow:

2D-дерево KD и поиск ближайшего соседа

Однако в ответе используется значение «Медиана», которое я не знаю, как вычислить. Также в статье в Википедии о kd-деревьях есть псевдокод ближайшего соседа, который не использует медианное значение.

Я хотел бы знать, можно ли построить рекурсивную версию алгоритма ближайших соседей без использования медианного значения. Если кто-нибудь может предоставить мне для этого псевдокод, я буду признателен.


recursion algorithm nearest-neighbor kdtree pseudocode
person 636f6465    schedule 26.04.2015    source источник
comment
Не уверен, что это полностью прояснит вам ситуацию, но вы можете взглянуть на мой недавний ответ на этот вопрос, который обеспечивает минимальную реализацию 2D-дерева KD.   -  person Alex    schedule 26.04.2015
comment
Синтаксис мне незнаком, так как я использую в основном Java. Но я просмотрю ваш ответ завтра и посмотрю, поможет ли он, спасибо.   -  person 636f6465    schedule 27.04.2015
comment
Терминология связанной статьи немного неправильная. То, что OP называет медианой, - это просто значение разделения. По возможности, для разделения полезно использовать медианное значение данных, потому что оно дает дереву минимальную высоту, но это не является обязательным требованием. Например. если у вас нет доступа ко всем данным заранее, вы не сможете найти медиану. Все построение и поиск kd-дерева основаны на разделении значений, независимо от того, являются они медианами или нет.   -  person Gene    schedule 27.04.2015
comment
Я считаю, что медиана рассчитывается путем сохранения списка узлов в текущем поддереве и выбора среднего значения. Мне было интересно, есть ли версия, в которой вам вообще не нужно использовать медиану и, следовательно, не поддерживать список узлов. Еще лучше, если есть пример алгоритма псевдокода, который вы можете связать, я ценю это. Я изо всех сил пытаюсь найти хороший пример. Спасибо.   -  person 636f6465    schedule 28.04.2015
comment
@ Адам, я знаю, что за мой ответ проголосовали. Однако спасибо, было бы неплохо, если бы вы тоже приняли ответ, чтобы он отображался в том виде, в котором он был дан в ленте вопросов. :)   -  person gsamaras    schedule 09.05.2016

Ответы (1)


arrow_upward
1
arrow_downward

Если вы отчаянно пытаетесь не использовать медианное значение, вы можете использовать среднее значение. Здесь есть простой подход:

Пример 1: Что такое среднее значение этих чисел?

6, 11, 7

Add the numbers: 6 + 11 + 7 = 24
Divide by how many numbers (there are 3 numbers): 24 / 3 = 8

Среднее значение 8

Однако я настоятельно рекомендую вам выбрать медианное значение, поскольку размеры позволяют это в вашем случае.

Пример: найти медианное значение 12, 3 и 5

Расставьте их по порядку:

3, 5, 12

Среднее число - 5, поэтому медиана - 5.

Источник

Вам действительно не нужно их сортировать. Достаточно псевдосортировки, например, используя Quickselect.

В C ++, например, вы можете использовать nth_element () для эффективного поиска медианы. Вы можете увидеть мой вопрос здесь , где мне нужна была медиана для общих размеров. В случае с 2D, его можно упростить.

person gsamaras    schedule 27.04.2015