Компьютерное моделирование физических явлений. Малютин В.М - 87 стр.

UptoLike

ВУЗ: 

ТПУ | Томск

Составители: 

Рубрика: 

обработки подструктур перколяционного кластера и алгоритмы,
основанные на параллельных вычислениях.
Важной особенность алгоритма Хошена-Копельмана является его од-
нопроходность. За один проход алгоритм позволяет выяснить, к какому
кластеру относится тот или иной узел решетки. Идея алгоритма заключа-
ется в том, что всем занятым узлам решетки приписываются различные
кластерные метки.
Рассмотрим метод многократной маркировки кластеров Хошена-
Копельмана. Алгоритм лучше всего описать на примере. Рассмотрим
конфигурацию, изображенную на рис.5.6. Мы присваиваем ячейкам
кластерные метки, двигаясь из верхнего левого угла вправо. Поскольку
ячейка(1,1) занята, мы присваиваем ей кластерную метку 1. Следующая
ячейка пустая, а значит, не маркируется. Следующей занятой ячейкой в
первой строке является ячейка(3,1). Поскольку соседняя ячейка слева
пустая, мы присваиваем ей следующую допустимую кластерную метку, т.е.
метку 2. Точно так же присваиваются кластерные метки остальным ячейкам
первой строки. Затем мы возобновляем процедуру с ячейки(1,2) во второй
строке. Поскольку она занята и ближайшая соседняя ячейка из первой
строки имеет метку 1, мы присваиваем ячейке(1,2) метку 1. Продолжаем в
том же духе, двигаясь слева направо по второй строке и проверяя занятость
каждой ячейки. Если ячейка занята, то проверяем на занятость ее
ближайших соседей в предыдущих строке и колонке. Если соседние
ячейки пусты, то присваиваем ей следующую доступную кластерную
метку. Если только одна из соседних ячеек занята, то присваиваем ей метку
занятой ячейки. Например, ячейке(2,2) присваиваем метку 1, поскольку
соседняя занятая ячейка(1,2) имеет метку 1.
a б
Рис. 5.6. Перколяционная конфигурация на квадратной решетке L = 7:
координаты ячеек определяются относительно левого верхнего угла (1,1);
а — показаны неправильные кластерные метки; б - показаны правильные
кластерные метки
Проблема возникает тогда, когда мы попадаем в занятую ячейку, в
которой соединяются два кластера, и необходимо изменить кластерные
метки. Этот случай впервые возникает в ячейке(6,2), у которой две соседние
ячейки в предыдущих строке и столбце имеют метки 3 и 4 соответственно.
87

Страницы