Пaлыч (26.04.2013 13:53, просмотров: 76) ответил fk0 на Дано неупорядоченное множество точек в многомерном пространстве. Для простоты предположим, что на плоскости. Нужно найти точки близкие (на расстоянии меньше заданного) к данной. Как быть?
Можно немного уменьшить количество вычислений. Для каждой точки иметь структуру: расстояние и номер точки для которой это расстояние вычислено. Т.е. имеем массив структур. Если вычислили расстояние от точки А до точки В, то это же расстояние от В до А.
При определении ближайшей точки для точки 1 вычисляем расстояния до всех точек и заносим в каждую структуру. Туда же заносим и номер точки =1. При вычислении ближайшей ко второй - первую уже "не трогаем" - её расстояние уже храниться в структуре. Если вычисленное расстояние до некоторой точки меньше, чем запомненное в структуре - заменяем и меняем номер точки. Т.о. в структуре храниться минимальное расстояние между точкой и теми точками, для которых определение ближайшей точки уже произведено.
Для последней точки ничего определять уже и не нужно будет - хранится в структуре.
По сравнению с полным перебором - количество вычислений сокращается вдвое.