Re: Минимаксная "сортировка"

From

Nick Kovaliov ()

To

Valentin Davydov

Date

2003-01-10T10:06:52Z

Area

RU.ALGORITHMS

From: "Nick Kovaliov" <Nick@urm.ru>

    VD> Есть множество из N точек
    VD> в метрическом пространстве,
    VD> надо отсортировать их следующим образом:
    VD> в качестве первой точки берётся некая произвольная,
    VD> а каждая следующая выбирается так,
    VD> чтобы минимальное расстояние от неё
    VD> до уже выбранных было бы самым большим
    VD> среди всех оставшихся точек.

Именно бОльшим ? ...
Для меньших задача решена ...
Называется "Vantage Point Tree".
Для поиска минимального соседа используется.

Там строится дерево за N*log(N),
И потом ближайшего найти можно за log(N).

Наверное, можно приспособить и для твоего случая ...

Можно придумать вот что -
один раз (может быть тормозно) построить
структуру что-то типа с идеей хеширования,
а потом быстро искать самого далёкого.
В применении к твоей задаче будет
быстро находить такие цепочки,
начиная с любой точки.

До встречи, всего наилучшего


--- ifmail v.2.15dev5
 * Origin: Demos online service (2:5020/400)