2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 [Wolfram Mathematica] поиск подграфа или подмножества?
Сообщение17.02.2015, 11:07 
Странная задача.

Есть куча ($N_O$) атомов, у каждого импульс $ q_i$. Они сгруппированы в 3D пространстве (допустим простая решетка), то есть имеют соседей (ближайший атом).
Импульсы $ q_i$ случайно направленны в разные стороны. Нужно найти количество блоков из $N$ атомов, таких, чтобы любой атом блока был связан с остальными хотя бы через одного соседа, при этом сумма их импульсов была бы равна x.

Начал думать. В голову приходит 2 пути решения:

1. Нужно задать как-то пространственное положение атомов, что бы выявить соседей. Допустим, создать граф, который объединяет соседние атомы своими ребрами. в VertexWeight вершины запихаем собственно, вектор. Обходим граф, ищем удовлетворяющие фрагменты, удаляем повторы и те, которые на самом деле объединены в один больший блок.

2. Пускай вектора задаются множеством. Каждый элемент множества - список из координат атома и его вектора $ q_i$. При помощи SubSet формируем кучу N-атомных подмножеств. Проверяем их функцией, подходят под критерий или нет. Исключаем повторы.

Собственно, может подскажет кто: какой вариант позволит обработать большие объемы информации? или есть какой-нибудь другой эффективный путь?

 
 
 [ 1 сообщение ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group