|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Nick Kovaliov 2:5020/400 10 Jan 2003 11:06:52
To : Valentin Davydov
Subject : Re: Минимаксная "сортировка"
--------------------------------------------------------------------------------
VD> Есть множество из N точек
VD> в метрическом пространстве,
VD> надо отсортировать их следующим образом:
VD> в качестве первой точки берётся некая произвольная,
VD> а каждая следующая выбирается так,
VD> чтобы минимальное расстояние от неё
VD> до уже выбранных было бы самым большим
VD> среди всех оставшихся точек.
Именно бОльшим ? ...
Для меньших задача решена ...
Hазывается "Vantage Point Tree".
Для поиска минимального соседа используется.
Там строится дерево за N*log(N),
И потом ближайшего найти можно за log(N).
Hаверное, можно приспособить и для твоего случая ...
Можно придумать вот что -
один раз (может быть тормозно) построить
структуру что-то типа с идеей хеширования,
а потом быстро искать самого далёкого.
В применении к твоей задаче будет
быстро находить такие цепочки,
начиная с любой точки.
До встречи, всего наилучшего
--- ifmail v.2.15dev5
* Origin: Demos online service (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Re: Минимаксная "сортировка" 