Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 19
Из текста вроде бы следует, что они доказали существование универсального алгоритма, но еще не обнаружили его.
Заинтриговали… В результате прочитал внимательно всю статью, но алгоритма так и не увидел:)
Можно ли ожидать новой статьи с описанием самого алгоритма?
Можно ли ожидать новой статьи с описанием самого алгоритма?
В предпоследнем абзаце вся статья.
больше ничего в статье нет, кроме большого количества букв, имеющих весьма отдаленное отношения к сути.
В итоге новые работы впервые обобщают поиск ближайшего соседа в многомерных данных. Вместо того, чтобы разрабатывать специализированные алгоритмы для определённых метрик, у программистов появился универсальный подход для поиска алгоритмов.
больше ничего в статье нет, кроме большого количества букв, имеющих весьма отдаленное отношения к сути.
очередные грантопилы?
Если я правильно понял, то это не решает проблему поиска, когда ребра выступают в качестве разных свойств. Что-то вроде «найти ближайших соседей по зеленым синим и розовым дорогам». Тогда из запроса приходится хэшировать вот эти различия и считать уже тем же дейкстрой. Хэш специфичный подбирать опять же под конкретную задачу.
Если, допустим, ваши данные описывают расположение коров на пастбище, то вы можете заключить каждую из них в круг. Потом поместим на луг новую корову и зададим вопрос: в какой из кругов она попадает? Практически гарантировано, что ближайший сосед новой коровы окажется в том же самом круге
это песня
Про алгоритм сортировки пузырьком тоже можно написать много букв, и это тоже будет непонятно.
Я как-то не понял. Алгоритм поиска ближайших же описан вполне себе универсально. Есть точки в многомерном пространстве поиска, есть функция расстояния от двух этих точек. Заменой функции можно работать на любом таком пространстве с данными любой сложности.
Поиск ближайшего в случае полного перебора это O(n), хочется быстрее. Например для Евклидова пространства можно оптимизировать до O(logN). Вопрос именно в более быстром универсальном алгоритме.
А можно подробнее как оптимизировать для Евклида до O(logN)? Ибо как я предполагаю, здесь этот метод оптимизации будет основан на предсортировке новых данных, а не случая, когда данные лежат как есть. Но тогда, что мешает заменой функции предсортировки сделать такую же оптимизацию?
> Но тогда, что мешает заменой функции предсортировки сделать такую же оптимизацию?
Ну например не известны алгоритмы, сортирующие данные необходимым образом для такой-то метрики. Пример: на плоскости или в трёхмерном пространстве на множестве точек можно построить триангуляцию Делоне (диаграмму Вороного), и тогда для любой точки ближайшие соседи ищутся за константное время. Проблема в том, что для трёхмерного пространства триангуляция строится за O(n log(n)) (n — количество точек), а для пространств большей размерности есть алгоритмы только со сложностью O(n^(1 + d/2) ) (d — количество измерений).
Ну например не известны алгоритмы, сортирующие данные необходимым образом для такой-то метрики. Пример: на плоскости или в трёхмерном пространстве на множестве точек можно построить триангуляцию Делоне (диаграмму Вороного), и тогда для любой точки ближайшие соседи ищутся за константное время. Проблема в том, что для трёхмерного пространства триангуляция строится за O(n log(n)) (n — количество точек), а для пространств большей размерности есть алгоритмы только со сложностью O(n^(1 + d/2) ) (d — количество измерений).
А в чем сложность найти ближайшего соседа в экспандере? Берешь первое попавшееся ребро из текущей точки, точка с другой стороны ребра и есть ближайший сосед. Аналогично находятся все ближайшие соседи с растоянием 1 за линейное время от количества соседов. И так для любого растояния.
Мне кажется или все таки не хватает ссылок на сами публикации, в оригинале они присутствуют
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Обнаружен универсальный метод сортировки сложной информации