|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Valentin Davydov 2:5020/400 09 Jan 2003 18:37:41
To : All
Subject : Минимаксная "сортировка"
--------------------------------------------------------------------------------
Есть множество из N точек в метрическом пространстве, надо отсортировать
их следующим образом: в качестве первой точки берётся некая произвольная,
а каждая следующая выбирается так, чтобы минимальное расстояние от неё до
уже выбранных было бы самым большим среди всех оставшихся точек. Все точки
сортировать необязательно, достаточно первых K, причём K обычно много
меньше, чем N. Тривиальный алгоритм прямого перебора линеен по N и
квадратичен по K. Можно ли его как-нибудь ускорить?
Вал. Дав.
--- ifmail v.2.15dev5
* Origin: St. Petersburg State University (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
