Отбор равноотстоящих друг от друга последовательно выпадающих точек

yurijm123

Есть такая задача:
есть последовательность точек, для которых известна матрица расстояний. Нужно выбрать из них хотя бы один набор точек такой, чтобы
а) последовательность отобранных точек была та же (если было десять последовательно нумерованных точек, то в отбираемом наборе должны быть точки (1, 3, 5, 9 но не (1,9,3,5
б) чтобы расстояния между любыми i-ой и i+1-ой точками в выбранном наборе были возможно более одинаковыми

shpanenoc

Приведи пример. Пусть, к примеру, у нас есть 10 точек, расположенные на прямой, с координатами 2,3,5,7,11,13,17,19,23,29 . Какую последовательность следует выбрать? А то "возможно более одинаковые" сбивают с толку.

yurijm123

Ну например 2, 7, 13, 19, 23, 29 (расстояния: 5, 6, 6, 4, 6).

shpanenoc

почему не 3,5,7 ? расстояния более одинаковые :)

yurijm123

Ну тоже вариант, просто хочется охватить набор от начала до конца

komBAR

Набор 2, 29 устроит? Все расстояния между собой равны, весь исходный набор охвачен.

shpanenoc

Если у тебя есть естественная задача, то давай ее сюда. Твоя мат.модель пока не достаточна, чтобы думать об алгоритме.

yurijm123

http://lurkmore.to/%D4%E0%E9%EB:Okay_Guy.jpg
Есть траектория от молдинамики - набор состояний молекулярной системы, каждое описано набором координат атомов и соответствует определенному времени. При расчете там происходит некое сложное конформационное изменение. Мне надо прояснить путь этого процесса. Для этого я кластеризовал все рассчитанные состояния и получил набор состояний, лежащих наиболее близко к центроидам кластеров, считатя, что эти состояния находятся возле локальных минимумов и седловин на ландшафте свободной энергии. Теперь мне надо отобрать из этих кластеров некоторое количество состояний для обсчета энергетики процесса: по этим состояниям программа протащит изучаемую систему. Так вот, чем более одинаковым будет расстояние между соседними состояниями, расставленными по пути протекания конформационного перехода, тем лучше пройдет расчет. Здесь и возникает задача об отборе состояний

shpanenoc

Как я себе вижу, у тебя есть ломаная, ее вершины - это твои кластеры состояний. Тебе надо выкинуть из нее некоторые точки так, чтобы получившаяся ломаная обладала двумя свойствами:
* Расстояние от нее до исходной ломаной должно быть малым, то есть она хорошо аппроксимирует исходную ломаную.
* Длины ребер ломаной должны быть близки между собой.
Эти два требования надо как-то уравновесить в один функционал, иначе непонятно, что минимизировать.
Еще скажи, сколько у тебя точек.

yurijm123

Точек 20-50, точно не более сотни

shpanenoc

Тогда предлагаю так доопределить задачу:
Выкинуть из ломаной точки, так чтобы:
1. Дискретное расстояние Фреше ( wiki ) между исходной и результирующей ломаной было минимальным.
2. Если Ei - длины ребер получившейся ломаной, то величина Ei/E1 должна лежать в пределах от alpha до 1/alpha. Альфа - это параметр.
Алгоритм следующий:
1. Фиксируем какую-нибудь альфу, например, 0.8, то есть допускаем 20% отклонение по длине, все остальное отвергаем.
2. Первые две точки ломаной выбираем произвольно, тем самым фиксируем E1.
3. Достраиваем ломаную до "оптимальной"
3.1. Каждая последующая точка ломаной не должна нарушать требования (2).
3.2. За один линейный проход можно найти ломаную, доставляющую минимум расстоянию Фреше, с помощью простого динамического программирования.
Когда цикл из п.2. целиком пройден, у нас будет готов "ответ" (т.е. наилучшая ломаная). Но он может оказаться сродни варианту , то есть ломаная из 2 точек, которая не очень-то хорошо интерполирует исходную ломаную.
Если так получилось (если построенная "оптимальная" ломаная тебе не нравится уменьшаем альфу и повторяем алгоритм сначала.
Сложность одного прохода - O(N^3 для 100 точек будет считаться мгновенно.
Как мне представляется, алгоритм в 3.2 не требует неравенства треугольника, то есть будет работать с любыми матрицами расстояний.
Оставить комментарий
Имя или ник:
Комментарий: