Есть замкнутая в кольцо цепочка шаров заданной длины L. Цепочка разбита на N непрерывных сегментов, сумма длин всех сегментов равна L. Все сегменты пронумерованы. Цепочка размещается произвольным образом на равномерной сетке (в пространстве), один шар в один узел сетки, соседние шары в соседние узлы сетки. Известно, какие сегменты цепочки касается друг друга (то есть какие либо шары одного и другого сегмента находится в соседних узлах клетки). Восстановить структуру цепи, то есть положение шаров цепочки на сетке (с точности до симметрии и сдвига).

Какими способами решаются подобные задачи? Если предлагается перебор с возвратами, то как можно обеспечить его эффективность?
Допустима любая эмпирика и неточные решения (то есть если алгоритм генерит структуры с малым(!) числом ошибочных контактов, но делает это быстро, то это хорошее решение). 

область науки - биоинформатика

Приведённых данных явно недостаточно для однозначного восстановления конфигурации. Даже для двумерного случая - а у тебя, как я понимаю, нужно будет переносить решение в пространство.


Присоединённый файл ( Кол-во скачиваний: 9 )
 1.gif 4,73 Kb

Это так. 

Нужна идея быстрой генерации вариантов, которые далее ранжируются с использованием оценочных функций, и выбираются варианты с максимальным рангом. Нужна совокупность наиболее "хороших" вариантов.

1) Решение ТОЧНО нужно в 2D?
2) Гарантируется ли, что решение имеется? Если в 2D - то несамопересекающееся?
3) Как задаются исходные данные?

1. нужна идея эффективного решения, обобщение просто, потому безразлично 2 или 3D. 3D относится к реальности.

2. Данные берутся из эксперимента, потому решение гарантируется. Наоборот, данных зачастую не хватает, потому решение неоднозначно. В 2D пересечения запрещены.

3. матрица контактов

Ага, знать бы ещё что именно названо этим термином, и какие именно данные содержит...

Индексы элемента - номера сегментов (пары возможно пересекающихся сегментов), значение элемента - число контактов между сегментами этой пары

Число контактов - это количество последовательных точек одного контакта или количество точек, между которыми у сегмента могут быть контакты с третьим сегментом? Т.е. если между сегментами 1 и 2 есть 2 контакта, может ли быть на сегменте 1 между этими точками ещё точка контакта с сегментом 3? Или взаимное расположение точек контакта в принципе не определено?

Взаимное расположение точек контакта в принципе не определено. Потому все вышеперечисленное возможно. 

Значит, надо сразу моделировать в 3D.