12.3.   МАРКИРОВКА КЛАСТЕРОВ

Вероятно, ваш визуальный алгоритм определения наличия соединяющего пути и вычисления количества кластеров является очень изощренным. Включает ли ои в себя параллельную обработку данных? Однако выполнение вашего алгоритма утомляет и поглощает много времени, и мы хотели бы переложить эту работу на компьютер. Как мы увидям в дальнейшем, такая работа трудна даже для компьютера. Эта трудность связана с тем, что принадлежность ячейки некоторому кластеру является глобальным свойством ячейки, а не локальным.

Мы рассмотрим метод многократной маркировки кластеров Хошена и Копельмана (см. литературу в конце главы). Алгоритм лучше всего описать на примере. Рассмотрим конфигурацию, изображенную на рис. 12.8. Мы присваиваем ячейкам кластерные метки, двигаясь из нижнего левого угла вправо. Поскольку ячейка(\,\) занята, мы присваиваем ей кластерную метку 1. Следующая ячейка пустая, а значит, не маркируется. Следующей занятой ячейкой в первой строке является ячейка(Ъ,\)-   Поскольку соседняя ячейка слева пустая,   мы присваиваем

ей следующую допустимую кластерную метку, т.е. метку 2. Точно так же присваиваются кластерные метки остальным ячейкам первой строки. Затем мы возобновляем процедуру с ячейки(\,2) во второй строке. Поскольку оиа занята и ближайшая соседняя ячейка из первой строки имеет метку 1, мы присваиваем ячейке(\,2) метку 1. Продолжаем в том же духе, двигаясь слева направо по второй строке и проверяя занятость каждой ячейки. Если ячейка занята, то мы проверяем на занятость ее ближайших соседей в предыдущих строке и колонке. Если соседние ячейки пусты, то мы присваиваем ей следующую доступную кластерную метку. Если только одна из соседних ячеек занята, то присваиваем ей метку занятой ячейки. Например, ячейке(2,2) присваиваем метку 1, поскольку соседняя занятая ячейка(\,2) имеет метку 1.

Проблема возникает тогда, когда мы попадаем в занятую ячейку, в которой соединяются два кластера, и необходимо изменить кластерные метки. Этот случай впервые возникает в ячейке(6,2), у которой две соседние ячейки в предыдущих строке и столбце имеют метки 3 и 4 соответственно. Ясно, что правильное присваивание кластерной метки ячейке(&,2) заключается в выборе меньшей из меток 3 и 4. Следовательно, ячейке(<о,2) присваивается метка 3, а метка 4 должна замениться на метку 3. Однако, поскольку в дальнейшем могут проводиться другие изменения присвоенных меток, мы не будем проводить изменение меток до тех пор, пока ие будет обследована вся решетка. Эта процедура изменения меток выполняется с помощью разделения правильных меток, таких, как 3, и неправильных, таких, как 4. Мы введем дополнительный  массив лр(|),   в котором  разделяются  правильные и неправнльные метки и учитываются их связи. Вернемся к конфигурации, показанной на рис. 12.8, чтобы объяснить, как используется этот массив. Прежде чем мы попадем в ячейку(6,2), метки от 1 до 4 считаются правильными и мы полагаем

пр(\) = 0,   пр(2) - 0,     лр(3) = 0,   лр(4) = 0.

Однако в ячейке(&,2), где метки 3 и 4 связаны, мы положим лр(4) = = 3. Этот ненулевой элемент ир(4) массива показывает, что метка 4 является неправильной, а численное значение яр(4) показывает, что метка 4 связана с меткой 3. Заметим, что индекс массива всегда больше самого значения пр.

Приведенная выше процедура несовершенна. Что мы должны сделать, когда попадем в ячейку, в которой предшествующие отмаркироваиные соседн имеют неправильные метки? Рассмотрим, например, ячейку{ЪЛ), у которой имеются занятые соседние ячейки с метками 5 и 4. Соблазнительно было бы присвоить ячейке(ЪА) метку 4 и положить лр(5) = = 4. Однако вместо присваивания ячейке минимальной метки ее соседей мы должны присвоить ей минимальную правильную метку одной нз двух ближайших ячеек. К тому же, если две ближайшие ячейки имеют разные правильные метки, мы должны присвоить элементу массива пр максимальную правильную метку, равную минимальной правильной метке.

Приведенная выше версия алгоритма присваивания меток Хошена — Копельмана реализуется в программе cluster для квадратной решетки. В программе имеется также «меню», так что различные характеристики кластеров можно вычислять, не вызывая другие подпрограммы. В подпрограмме assign каждой ячейке присваивается случайное число и записывается в массив г. Эта подпрограмма вызывается в 1-м и 11-м пунктах меню. Занятость ячеек определяется в подпрограмме occupy и записывается в массив 5. Присваивание кластерных меток производится в подпрограммах cluster_label, newcluster, neighbors, label_min и proper. Каждой ячейке присваиваются кластерные метки и записываются в одномерный массив с/, а связи кластерных меток хранятся в одномерном массиве пр. Подпрограмма plot_label изображает правильные или неправильные метки. Подпрограмма p1ot_conf рисует занятые ячейки, подпрограмма plot_cluster изображает координаты ячейки в кластере, правильный номер которой является аргументом подпрограммы.

После маркировки кластеров мы можем получить некоторые интересующие нас геометрические характеристики.  В подпрограмме span опреде

ляется, содержит ли конфигурация вертикально соединяющий кластер, путем проверки наличия общих правильных меток в верхней и нижней строках. Если имеется соединяющий кластер, то его правильная метка выводится иа экран, в противном случае переменная ispan остается равной 0.

В подпрограмме compute_mass определяется размер (число занятых ячеек) каждого кластера. Распределение кластеров п можно найти, подсчитывая количество кластеров размером п , и отнормировать ре-зультаты, разделив их иа i .

Вероятность того, что занятая ячейка принадлежит соединяющему кластеру, определяется в подпрограмме Pinfinity. В этой подпрограмме для вычисления размера соединяющего кластера и полного числа занятых ячеек используются соответственно метка кластера, полученная в подпрограмме span, и распределение кластеров, полученное в подпрограмме mass. Отношение этих двух величии представляет собой Р .

В подпрограмме mean_size для вычисления среднего размера кластера 5 в несоединяющих кластерах используются данные, полученные в подпрограмме mass. В подпрограмме mean_size значение ns(i) представляет собой размер кластера с правильной меткой i. Для получения 5 мы суммируем по правильным меткам, а не по размеру s, как это сделано в определении (12.3) величины 5. Убедитесь в том, что эти два метода вычисления 5 эквивалентны. Подчеркнем, что соединяющие кластеры не включаются в сумму.

Программа cluster не является самой эффективной реализацией алгоритма Хошена — Копельмаиа. Более эффективная версия программы на Фортране приводится у Стауффера (см. список литературы в конце главы). Хотя можно показать, что алгоритм Хошена —Копельмана является самым эффективным способом маркировки кластеров для двумерной решетки, не ясно, будет ли он самым эффективным для решеток большей размерности. Можете ли вы предложить другой метод идентификации кластеров?

Подпись:

Подпись:

Подпись:

Подпись:

Подпись:

Подпись:

Подпись:

Подпись:

Подпись:

Подпись:

Для более систематического изучения ячеечной перколяции в задаче 12.5 используется алгоритм маркировки кластеров Хошена—Копельмана. В разд. 12.4 мы будем применять конечномерный масштабный анализ, чтобы получить качественные результаты для относительно малых систем. Подпрограммы, которые изображают конфигурации и метки кластеров на экране, необходимо использовать только в задаче 12.5а.