Блог

Проблема:

N узлов связаны друг с другом коэффициентом «близости» в диапазоне от 0 до 1, где коэффициент 1 означает, что два узла не имеют ничего общего, а 0 означает, что два узла абсолютно одинаковы.

Если два узла находятся близко к другому узлу (т. Е. у них коэффициент близок к 0), то это не означает, что они будут находиться близко друг к другу, хотя вероятностно у них гораздо больше шансов оказаться близко друг к другу.

—

Вопрос:

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

Это не вопрос домашнего задания, это реальная проблема, которую мне нужно решить, Но я никогда не посещал никаких курсов по алгоритмам и т.д., Поэтому я понятия не имею, какой алгоритм я должен исследовать.

Я могу проиндексировать все узлы до добавления другого и собрать данные о близости между каждым узлом, но, за исключением сравнения всех узлов с новым узлом, я не смог придумать эффективное решение. Любые идеи или помощь были бы высоко оценены 🙂

Поскольку ваша метрика ‘closeness’ подчиняется неравенству треугольника, вы должны иметь возможность использовать вариант BK-деревьев для организации ваших элементов. Адаптация их к действительным числам должна заключаться просто в выборе интервала для квантования вашего числа и в противном случае в использовании стандартной процедуры Bk-Tree. Может потребоваться некоторое экспериментирование — например, вы можете захотеть увеличить разрешение квантования по мере продвижения вниз по дереву.

но, за исключением сравнения всех узлов с новым узлом, я не смог найти эффективного решения

Без какой-либо другой информации об отношениях между узлами это единственный способ, которым вы можете это сделать, поскольку вам нужно выяснить коэффициент близости между новым узлом и каждым существующим узлом. Алгоритм O (n) может быть вполне приличным решением.

Одно дополнение, которое вы могли бы рассмотреть — имейте в виду, что мы понятия не имеем, какую структуру данных вы используете для своих объектов, — это организовать все существующие узлы в виде графика, где узлы с коэффициентами ниже определенного порога могут считаться связанными, поэтому вы можете сначала проверить узлы, которые с большей вероятностью будут похожи / связаны.

Если вам нужен оптимальный алгоритм с точки зрения скорости, но с объемом O (n ^ 2), то для каждого узла создайте отсортированный список других узлов (упорядоченный по близости).

Когда вы получаете новый узел, вы должны добавить его в индексированный список всех других узлов, и все остальные узлы должны быть добавлены в его список.

Чтобы найти ближайший узел, просто найдите первый узел в списке любого узла.

Поскольку вам уже нужно пространство O (n ^ 2) (для хранения всей информации о близости вам нужна в основном матрица NxN, где A [i, j] представляет близость между i и j), вы могли бы также отсортировать его и получить извлечение O (1).

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

Например, если мы рассматриваем буквы — A близко к B, но далеко от Z — тогда можно сохранить сортировку ранее существующих элементов, скажем: A, B, E, G, K, M, Q, Z. Чтобы вставить, скажем, ‘F’, вы начинаете со сравнения со средним элементом [3] G и следующим за ним: [4] K. Вы устанавливаете, что F ближе к G, чем K, поэтому наилучшее совпадение находится либо в G, либо слева, и мы перемещаемся на полпути в неисследованную область влево … 3/2 = [1] B, за которым следует E, и мы находим, что E ближе к F, поэтому совпадение либо в E, либо справа от него. Уменьшив вдвое интервал между нашими предыдущими проверками в [3] и [1], мы проверяем в [2] и находим его одинаково удаленным, поэтому вставляем его между ними.

РЕДАКТИРОВАТЬ: это может лучше работать в вероятностных ситуациях и требовать меньше сравнений, начинать с концов спектра и продвигаться по своему усмотрению (например, сравнить F с A и Z, решить, что это ближе к A, посмотреть, ближе ли A или промежуточная точка [3] G). Кроме того, было бы неплохо закончить сравнением с несколькими ближайшими точками по обе стороны от того места, куда привел вас двоичный файл / интерполяция.

В исследованиях ACM в сентябре 2001 года были опубликованы две статьи, которые могут быть актуальны, по крайней мере, для справки. «Поиск в метрических пространствах», ведущий автор Чавес, и «Поиск в пространствах высокой размерности — структуры индексов для повышения производительности мультимедийных баз данных», ведущий автор Бом. Из памяти, если все, что у вас есть, это неравенство треугольника, вы можете использовать его для некоторого эффекта, но если вы можете урезать свои данные до разумного количества измерений, вы можете добиться большего успеха, используя структуру поиска, которая знает об этой размерной структуре.

В Facebook есть такая штука, когда он помещает вас и всех ваших друзей в график, затем медленно перемещает всех по кругу, пока люди не будут сгруппированы на основе общих друзей и так далее.

Мне показалось, что они просто сделали что угодно <0,5 силой притяжения, что угодно > 0,5 силой отталкивания и перемещали людей с каждой итерацией на основе суммарной силы. После пары сотен итераций это выглядело чертовски хорошо.

Примечание: это не алгоритм, это эвристика. В реализации facebook, которую я видел, два человека не смогли достичь равновесия и продолжали танцевать друг вокруг друга. Оказывается, на самом деле это был один и тот же человек с двумя разными учетными записями.

Кроме того, это заняло около 15 минут на приличном компьютере и ~ 100 узлах. YMMV.

Это подозрительно похоже на проблему поиска ближайшего соседа (также называемую similarity search )