эффективный алгоритм поиска ближайшей точки на графе, который не имеет известного уравнения - PullRequest
10 голосов
/ 22 июля 2011

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

У меня есть график данных реального мира.В графике нет повторяющихся значений X и значений X с постоянной скоростью, но данные Y основаны на реальных результатах.Я хочу найти ближайшую точку на графике из произвольно заданной точки P программно.Я пытаюсь найти эффективный (то есть быстрый) алгоритм для этого.Мне не нужна точная ближайшая точка, я могу согласиться на точку, которая находится «почти» вблизи ближайшей точки.

Очевидное ленивое решение состоит в том, чтобы увеличивать каждую точку на графике, вычислять расстояние, а затем найдите минимум расстояния.Это, однако, теоретически может быть медленным для больших графов;слишком медленный для того, что я хочу.

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

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

Я могу 'Это не поможет, но я чувствую, что должен быть более быстрый алгоритм, чем мое решение (что полезно только потому, что я предполагаю, что 99% времени моя точка P будет точкой, близкой к прямой).Я попробовал поискать лучшие алгоритмы, но нашел так много алгоритмов, которые не совсем подходили, и было трудно найти то, что я искал, среди всего множества неуместных алгоритмов.Итак, есть ли у кого-нибудь здесь предложенный алгоритм, который был бы более эффективным?Имейте в виду, мне не нужен полный алгоритм, поскольку то, что у меня есть, работает для моих нужд, мне просто любопытно, каким было бы правильное решение.

Ответы [ 3 ]

4 голосов
/ 22 июля 2011

Если вы сохраните точки [x, y] в квадре , вы сможете быстро найти ближайшую (что-то вроде O (log n)). Я думаю, что это лучшее, что вы можете сделать, не делая предположений о том, где будет смысл. Вместо того, чтобы повторять алгоритм здесь, посмотрите на эту ссылку .

Ваше решение довольно хорошее, изучая, как точки изменяются по y, вы не можете рассчитать границу для количества точек вдоль оси x, которое вы должны исследовать вместо использования произвольной.

2 голосов
/ 22 июля 2011

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

  • quad-tree (и октри и т. Д.).
  • кД дерево
  • BSP дерево (только для статического набора точек).
  • г-дерево * +1010 *

R-дерево выпускается в нескольких вариантах. Оно очень тесно связано с деревом B +, но с (в зависимости от варианта) различными порядками элементов (точек) в конечных узлах.

В дереве Гильберта R используется строгое упорядочение точек на основе кривой Гильберта. Кривая Гильберта (или, скорее, ее обобщение) очень хороша при упорядочении многомерных данных, так что соседние точки в пространстве обычно находятся рядом в линейном порядке.

В принципе, порядок Гильберта можно применить, отсортировав простой массив точек. Естественная кластеризация в этом случае будет означать, что при поиске обычно требуется искать только несколько довольно коротких промежутков в массиве, при этом вам необходимо выяснить, какие это промежутки.

Раньше у меня была ссылка на хорошую статью о вычислениях порядка кривой Гильберта, но я ее потерял. Упорядочение по кодам Грея будет проще, но не настолько эффективно при кластеризации. На самом деле, существует глубокая связь между кодами Грея и кривыми Гильберта - эта бумага, которую я потерял, довольно часто использует функции, связанные с кодом Грея.

РЕДАКТИРОВАТЬ - Я нашел эту ссылку - http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.133.7490

2 голосов
/ 22 июля 2011

Допустим, ваша точка P=(x,y) и ваши реальные данные - это функция y=f(x)

Шаг 1: Расчет r=|f(x)-y|.

Шаг 2: Поиск точек в интервалеI=(x-r,x+r)

Шаг 3: Найти ближайшую точку от I до P.

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