madf: (Default)
[personal profile] madf
Ехал вчера с работы в маршрутке и придумалась мне такая задачка: есть 2 множества точек (скажем, на плоскости). Нужно каждой точке из первого множества найти такую точку из второго, что расстояние между ними будет минимальным.
Самый тупой алгоритм - перебор. То есть проходим по всем точкам одного множества и для каждой из них проходим по всем точкам второго. Тупой поиск минимума. В результате получаем квадратичную сложность алгоритма. Никуда не годится! И вот вчера целый вечер и сегодня весь день я пытался придумать более хорошее решение.
Сразу на ум приходит сортировка. Отсортировать один массив и потом двоичным поиском для каждой точки из второго множества найти ближайшую. Но вот ведь проблема - у точки 2 координаты! Думал я думал, думал... Сперва додумался до сортировки по расстоянию к некоторой точке (например, к центру координат). Но у нас может быть много точек, лежащих на окружности, с одинаковым расстоянием до центра координат. Это уже, несомненно, улучшение исходного алгоритма, но...
Думаем дальше. Преобразование в число (а-ля, A = y * MAX_Y + x) не подходит - теряется транзитивность. Буквально пол часа назад в голову случайно стукнула другая мысль: "а почему бы в качестве базиса не использовать не 1, а 2 точки?". Точно! Тут неопределенность уже намного меньше: всего 2 точки могут иметь одинаковое расстояние до базиса: с одной и с другой его стороны. До 3-й точки додуматься уже было несложно. По 3 точкам (Триангуляция!) можно нормально сортировать одно из множеств.

Profile

madf: (Default)
madf

April 2017

S M T W T F S
      1
2345678
9101112131415
1617 1819202122
23242526272829
30      

Most Popular Tags

Style Credit

Expand Cut Tags

No cut tags
Page generated Oct. 23rd, 2017 10:12 pm
Powered by Dreamwidth Studios