Методы нахождения замкнутых контуров

Размещено на http://www.allbest.ru/

Содержание

Введение

1. Исследование графена

1.1 Основные задачи теория перколяции

1.2 Энтропия Реньи

1.2.1 Частные случаи энтропии Реньи

1.3 Регрессионный анализ

2 Алгоритмы нахождения замкнутых контуров на графе

2.1 Алгоритм Ли

2.2 Алгоритм Флойда-Уоршалла

2.3 Алгоритм Флери

3. Практическая часть - Реализация метода для определения замкнутых областей на поверхности четырех и шестиугольной решеток

Заключение

Литература

Приложение A Листинг программы

замкнутый контур граф перколяция



Введение

Цель настоящей курсовой работы - ознакомиться с методами нахождения замкнутых контуров и написать программу, позволяющую находить корали на поверхности графена.

Для достижения этой цели были поставлены и решены следующие основные задачи:

1) ознакомление с предметной областью, ее основными понятиями;

2) анализ методов нахождения замкнутых контуров на графе;

3) составление алгоритма для решения поставленной задачи;

4) реализация программы для определения замкнутых областей на поверхности четырех и шестиугольной решеток;

5) расчет энтропии Реньи.



1. Исследование свойств графена

Графен - двумерная аллотропная модификация углерода, образованная слоем атомов углерода толщиной в один атом, соединённых в гексагональную двумерную кристаллическую решётку [18].

В каждом узле решетки может находиться электрон. Физикам удалось заселить свободное место в графене лишним электроном.

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

По словам ученых, в местах, где ионы выбили атомы углерода из поверхности графита, наблюдались скачки электропроводности. Физики полагают, что эти скачки были связаны с наличием в этом месте электрона. Подобный эффект был предсказан достаточно давно, однако на практике наблюдался только в случае большого количества дефектов в структуре графена. Теперь, однако, данное явление было изучено в случае отдельно взятой «дырки» в листе [5].

Для исследования свойств графена нами проводились эксперименты для гексагональной решетки, заполненной электронами на 66% и 68% (т.е. для вероятности распределения электронов вблизи пороговой перколяции).

1.1 Основные задачи теория перколяции

Слово перколяция (percolation - англ.) означает просачивание или протекание. Первый пример процесса просачивания (как модель распространения жидкости или газа в среде) привели Бродбент (1954) и Хамерсли (1957) [15]. До сих пор это направление занимает существенную часть в работах по теории перколяции.

Теория перколяции (протекания) - теория, описывающая возникновение бесконечных связных структур (кластеров), состоящих из отдельных элементов.

Наиболее распространенными задачами теории перколяции являются решеточные задачи: задача узлов и задача связей.

Рассмотрим бесконечную квадратную сетку. Назовем точки пересечения линий узлами. Сами линии будем называть связями.

В задаче связей ищут ответ на вопрос: какую долю связей нужно удалить (перерезать), чтобы сетка распалась на две части? В задаче узлов блокируют узлы (удаляют узел, перерезают все входящие в узел связи) и ищут, при какой доле блокированных узлов сетка распадется (рисунок 1.1).

Квадратная сетка является только одной из возможных моделей. Можно рассматривать перколяцию на треугольной, шестиугольной сетках, деревьях, трехмерных решетках, например, кубической, в пространстве с размерностью больше 3 [10]. Сетка не обязательно должна быть регулярной. Рассматриваются процессы и на случайных решетках.

Рисунок 1.1 Задача узлов (слева) и задача связей (справа) на квадратной решетке

Цепочка связанных объектов, например черных квадратов, называется в теории перколяции кластер (cluster - англ. - гроздь). Кластер, соединяющий две противоположные стороны системы, называется перколяционным (percolating), бесконечным (infinity), стягивающим (spanning) или соединяющим (connecting). Изучение свойств соединяющего кластера -- еще одна из задач теории перколяции. Ниже порога перколяции имеются только кластеры конечного размера. [26]

Кроме определения порога перколяции исследуют также следующие вопросы:

- структура субкритической и суперкритической фаз;

- что происходит вблизи порога перколяции;

- какова структура перколяционного кластера;

- каковы значения и свойства различных макроскопических величин, как, например, средний размер кластера;

- что происходит при изменении структуры решетки и размерности пространства.

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

1.2 Энтропия Реньи

Энтропия Реньи играют важную роль в различных областях человеческой деятельности: в экологии и статистике как индекс разнообразия, в квантовой информации - как мера сложности, в статистической механике - для описания квантовых диссипативных систем. Важными областями приложений энтропии являются квантово-механические и релятивистские объекты. В квантовой физике и астрофизике такие приложения энтропии представляют большой интерес. Достаточно вспомнить один из красивых результатов термодинамики черных дыр: энтропия черной дыры равна четверти площади ее поверхности (площади горизонта событий) (Хокинг, 1978) [29]. Широкая популярность формул типа в разных областях связана, возможно, с особой ролью степенных законов в природе [32]. Для таких случаев выражение является удобной аддитивной мерой. Удобной в плане нашего восприятия количества чего бы то ни было -- информации, хаоса, нелокальности, интенсивности света звезды и так далее. Ведь наши органы чувств работают по логарифмическому закону Вебера-Фехнера: интенсивность ощущения пропорциональна логарифму интенсивности стимула. В последнее время появилось много работ связывающих энтропию Реньи и запутанность [3] - явление, при котором квантовые состояния объектов взаимозависимы даже при разнесении их в пространстве. Данный эффект может оказаться полезным для квантовых вычислений или квантовой криптографии.

В работе «Математическая теория связи» К. Шеннон [31], исследуя передачу сообщений по шумящим линиям, ввел меру дискретного распределения вероятности на множестве альтернативных состояний передатчика и приемника сообщений и вывел формулу, ставшую основой количественной теории информации:

где Н - мера неопределенности;

n - число символов, из которых может быть составлено сообщение (алфавит);

- вероятность появления -го символа в сообщении, - число встречаемости -го символа в сообщении, N - число всех переданных и принятых символов в сообщении.

Величина Н была названа энтропией.

В 1960 г. венгерский математик Альфред Реньи предложил свое обобщение энтропии [7]. Он вводит энтропию как - момент меры - разбиения (покрытия):

где ;

- число элементов системы, приходящихся на i-элемент -разбиения;

- полное число элементов заданного покрытия;

- константа, может принимать любые значения, однако смысл энтропии Реньи при этом, соответственно, меняется.

Рассмотрим энтропию Реньи более подробно.

Пусть некий объект (фрактал, аттрактор) вложен в n-мерное эвклидово пространство. Часть пространства, занятого объектом, покроем равными гиперкубами с ребром . Пусть -- элемент «массы» или «значение» (число точек, поток вектора, почернение, амплитуда процесса и т. д.) в i-том гиперкубе данного покрытия. Тогда соответствующая вероятность равна [6]:

Где

- полная «масса» исследуемого объекта (ряда, магнитограммы, ССD изображения, аттрактора и т. д.), -- общее число ячеек, покрывающих объект. Очевидно следующее:

Обобщенная энтропия Реньи порядка q определяется так:

где .

1.2.1 Частные случаи энтропии Реньи

Если наш объект однороден, то есть все равны между собой, то . То есть энтропия Реньи любого порядка q в случае однородного объекта равна логарифму числа ячеек разбиения. Покажем это. Из формулы (1.4) получаем, , откуда . Подставляя в формулу (1.6), получаем:

Если и все , то из формулы (1.6) получаем тот же результат:

Пусть . Подставляя в формулу (1.7) и раскрывая неопределенность по правилу Лопиталя, получаем:

что с точностью до основания логарифмов (то есть постоянного множителя) совпадает с энтропией (информацией) Шеннона. В этой связи энтропию Реньи первого порядка называют информационной энтропией.

Пусть . Квадрат вероятности можно рассматривать как вероятность корреляции «значений» нашего объекта на расстоянии . Тогда сумма является аналогом корреляционного интеграла:

Поэтому энтропию Реньи второго порядка представляют в виде:

и называют также корреляционной энтропией.

В заключение можно отметить следующее. Энтропии Реньи при надлежащем определении выборок нечувствительны к разрывам в данных измерений и вообще к вариациям шага по времени. Поэтому энтропийная параметризация временного ряда выгодно отличается от любого типа фильтрации, которая к разрывам в данных обычно очень чувствительна. Такая параметризация особо предпочтительна для стохастических и автономных временных рядов, поскольку не требует предположений о гладкости и непрерывности [30]. Сама вариация может быть не гладкой и даже разрывной. Процедура измерений вносит дополнительно свои разрывы и свою стохастичность, связанную с ошибками и спецификой измерений. Расчет энтропии Реньи открывает новые возможности для анализа данных такого типа.

1.3 Регрессионный анализ

Регрессионный анализ - статистический метод исследования влияния одной или нескольких независимых переменных на зависимую переменную . Независимые переменные иначе называют регрессорами или предикторами, а зависимые переменные - критериальными [28].

Цели регрессионного анализа:

1) определение степени детерминированности вариации критериальной (зависимой) переменной предикторами (независимыми переменными);

2) предсказание значения зависимой переменной с помощью независимой(-ых);

3) определение вклада отдельных независимых переменных в вариацию зависимой;

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

Суть регрессионного анализа сводится к установлению уравнения регрессии, т.е. вида кривой между случайными величинами (аргументами и функцией ), оценке тесноты связей между ними, достоверности и адекватности результатов измерений.

Различают однофакторные (парные) и многофакторные регрессионные зависимости. Парная регрессия при парной зависимости может быть аппроксимирована прямой линией, параболой, гиперболой, логарифмической, степенной или показательной функцией, полиномом и др. Двухфакторное поле можно аппроксимировать плоскостью, параболоидом второго порядка, гиперболоидом [23].

При построении теоретической регрессионной зависимости используется метод наименьших квадратов (МНК). Суть МНК заключается в следующем: из всего множества линий, которые можно провести через экспериментальные точки на корреляционном поле, линия регрессии выбирается так, чтобы сумма квадратов расстояний по вертикали между экспериментальными точками и этой линией была наименьшей. Расстояния между экспериментальными точками и линией регрессии есть отклонения . Следовательно, при использовании МНК минимизируется следующая функция:

где - фактические ординаты поля;

- среднее значение ординаты.

Для анализа общего качества уравнения регрессии используют коэффициент детерминации R², называемый также квадратом коэффициента множественной корреляции [24]. Коэффициент детерминации (мера определенности) всегда находится в пределах интервала [0;1]. Если значение R² близко к единице, это означает, что построенная модель объясняет почти всю изменчивость соответствующих переменных. И наоборот, значение R² близкое к нулю, означает плохое качество построенной модели.

Коэффициент детерминации R² показывает, на сколько процентов найденная функция регрессии описывает связь между исходными значениями Y и Х. Соответственно, величина показывает, сколько процентов вариации параметра Y обусловлены факторами, не включенными в регрессионную модель.

При высоком значении коэффициента детерминации можно делать прогноз для конкретного значения в пределах диапазона исходных данных. При прогнозах значений, не входящих в диапазон исходных данных, справедливость полученной модели гарантировать нельзя. Это объясняется тем, что может проявиться влияние новых факторов, которые модель не учитывает.

Оценка значимости уравнения регрессии осуществляется с помощью критерия Фишера. При условии справедливости нулевой гипотезы критерий имеет распределение Фишера с числом степеней свободы , (для парной линейной регрессии р = 1). Если нулевая гипотеза отклоняется, то уравнение регрессии считается статистически значимым. Если нулевая гипотеза не отклоняется, то признается статистическая незначимость или ненадежность уравнения регрессии.

Регрессионный анализ удобно проводить с помощью возможностей Exel. Режим работы «Регрессия» служит для расчета параметров уравнения линейной регрессии и проверки его адекватности исследуемому процессу.

Рассмотрим величины, получаемые в результате регрессионного анализа.

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

Множественный R - коэффициент множественной корреляции R - выражает степень зависимости независимых переменных (X) и зависимой переменной (Y) и равен квадратному корню из коэффициента детерминации. В простом линейном регрессионном анализе множественный коэффициент R равен линейному коэффициенту корреляции.

Коэффициенты линейной модели: Y-пересечение выводит значение свободного члена b, а переменная Х1 - коэффициента регрессии а.

Проверить значимость коэффициентов регрессии можно сравнивая попарно значения столбцов Коэффициенты и Стандартная ошибка в таблице результатов, если абсолютные значения коэффициентов больше, чем их стандартные ошибки, то коэффициенты являются значимыми. Об этом также можно судить по значениям показателя Р-значение, которые должно быть меньше заданного уровня значимости б [13].

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



2. Алгоритмы нахождения замкнутых контуров на графе

2.1 Алгоритм Ли

Алгоритм волновой трассировки (волновой алгоритм, алгоритм Ли) - алгоритм поиска пути, основанный на методе поиска в ширину.

Волновой алгоритм в контексте поиска пути в лабиринте был формально предложен Э. Ф. Муром. Ли независимо открыл тот же алгоритм в контексте трассировки печатных плат в 1961 году [4].

Алгоритм применяется для поиска кратчайшего пути между двумя ячейками - источником и приемником дискретного рабочего поля.

Дискретное рабочее поле (ДРП) - это прямоугольник, разбитый на квадратные ячейки одинакового размера. Ячейки ДРП подразделяются на свободные, препятствия, источники и приемники [11]. На рисунке 2.1 представлено ДПР, где зеленым помечены свободные ячейки, красным - препятствия, синим - источник (А) и приемник (В).

Рисунок 2.1 Дискретное рабочее поле

Путь может быть двух видов:

- ортогональный;

- ортогонально-диагональный.

Ортогональный путь состоит из отрезков, параллельных сторонам ДРП. Ортогонально-диагональный путь может содержать еще и диагональные отрезки [8]. Соседи ячейки для таких путей отображены на рисунке 2.2, где синими квадратами обозначена стартовая ячейка, зеленым - ее соседи.

Рисунок 2.2 Соседи ячейки для ортогонального (а) и ортогонально-диагонального (б) путей

Этапы работы алгоритма:

- инициализацию;

- распространение волны;

- восстановление пути.

Во время инициализации на ДПР (двумерной матрице), состоящей из свободных ячеек и препятствий, обозначают источник и приемник, между которыми алгоритм должен найти кратчайший путь, если это возможно.

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

После достижения волной финиша, от финиша прокладывается путь до старта (рисунок 2. 3) и сохраняется в массиве [9].

Рисунок 2. 3 ДПР после выполнения алгоритма

Вычислительная сложность волнового алгоритма трассировки близка к .

Волновой алгоритм - один из основных при автоматизированной трассировке (разводке) печатных плат. Также одно из характерных применений волнового алгоритма - поиск кратчайшего расстояния на карте в стратегических играх [2].

Достоинства алгоритма Ли:

- после завершения работы алгоритмы часть ДПР остается неизученной, что говорит об эффективности алгоритма, а именно - позволяет сократить использование таких ресурсов, как время и оперативная память;

- использование принципа обратной трассировки (когда поиск пути ведется из точки финиша в точку старта) на этапе восстановления пути, позволяет избежать проблем с поиском способов определения тупиков и выхода из «карманов» и циклов, появляющихся в случае прямой трассировки из точки старта в точку финиша.

2.2 Алгоритм Флойда-Уоршалла

Алгоритм Флойда - Уоршелла - динамический алгоритм для нахождения кратчайших расстояний между всеми вершинами взвешенного ориентированного графа.

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

Считается, что этот алгоритм был одновременно опубликован в статьях Роберта Флойда и Стивена Уоршелла в 1962 году, хотя в 1959 году Бернард Рой опубликовал практически такой же алгоритм, но это осталось незамеченным [16].

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

Перед k-ой фазой (k = 1… n) считается, что в матрице расстояний d сохранены длины таких кратчайших путей, которые содержат в качестве внутренних вершин только вершины из множества {1, 2,…, k-1} (вершины графа мы нумеруем, начиная с единицы).

Иными словами, перед k-ой фазой величина равна длине кратчайшего пути из вершины i в вершину j, если этому пути разрешается заходить только в вершины с номерами, меньшими k (начало и конец пути не считаются).

Для того чтобы это свойство выполнилось для первой фазы, достаточно в матрицу расстояний d записать матрицу смежности графа: - стоимости ребра из вершины i в вершину j. Если между какими-то вершинами ребра нет, то следует записать величину «бесконечность». Из вершины в саму себя всегда следует записывать величину 0, это критично для алгоритма.

Пусть теперь мы находимся на k-ой фазе, и хотим пересчитать матрицу d таким образом, чтобы она соответствовала требованиям уже для k+1-ой фазы. Зафиксируем какие-то вершины i и j. У нас возникает два принципиально разных случая [14]:

- кратчайший путь из вершины i в вершину j, которому разрешено дополнительно проходить через вершины , совпадает с кратчайшим путём, которому разрешено проходить через вершины множества . В этом случае величина не изменится при переходе с фазы k на фазу k+1;

- «новый» кратчайший путь стал лучше «старого» пути. Это означает, что «новый» кратчайший путь проходит через вершину k. Сразу отметим, что мы не потеряем общности, рассматривая далее только простые пути (т.е. пути, не проходящие по какой-то вершине дважды). Тогда заметим, что если мы разобьём этот «новый» путь вершиной k на две половинки (одна идущая , а другая - ), то каждая из этих половинок уже не заходит в вершину k. Но тогда получается, что длина каждой из этих половинок была посчитана ещё на k-1-ой фазе или ещё раньше, и нам достаточно взять просто сумму , она и даст длину "нового" кратчайшего пути.

Объединяя эти два случая, получаем, что на k-ой фазе требуется пересчитать длины кратчайших путей между всеми парами вершин i и j следующим образом:

(2.1)

Таким образом, вся работа, которую требуется произвести на k-ой фазе -- это перебрать все пары вершин и пересчитать длину кратчайшего пути между ними. В результате после выполнения n-ой фазы в матрице расстояний будет записана длина кратчайшего пути между i и j, либо , если пути между этими вершинами не существует.

Алгоритм Флойда-Уоршелла имеет сложность по времени и по памяти.

Одним из достоинств этого алгоритма легкость восстановления самих путей между любыми двумя заданными вершинами в виде последовательности вершин [25].

Для этого достаточно кроме матрицы расстояний d поддерживать также матрицу предков p, которая для каждой пары вершин будет содержать номер фазы, на которой было получено кратчайшее расстояние между ними. Понятно, что этот номер фазы является не чем иным, как "средней" вершиной искомого кратчайшего пути, и теперь нам просто надо найти кратчайший путь между вершинами i и , а также между и j. Отсюда получается простой рекурсивный алгоритм восстановления кратчайшего пути [12].

В качестве примера применения алгоритма Флойда-Уоршелла приведены граф (рисунок 2.4) и часть трассировки алгоритма (формулы (2.2)-(2.6)):

,(2.2)

,(2.3)

(2.4)

(2.5)

.(2.6)

Рисунок 2.4 Граф с обозначенными весами ребер между смежными узлами

Алгоритм Флойда -- Уоршелла используется очень широко, начиная от поиска транзитивного замыкания графа, заканчивая генетикой и управлением проектами. Но основное его применение - в различных сетях, в том числе транспортных [17].

2.3 Алгоритм Флери

Алгоритм Флери - алгоритм построения эйлерова цикла. Результат представляется в виде списка ребер графа в той последовательности, в которой они образуют эйлеров цикл [21].

Алгоритм позволяет найти маршрут, проходящий по всем ребрам между узлами ровно по одному разу и возвращающийся в исходную точку. Работает только для эйлерова графа.

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

Суть алгоритма Флёри заключается в том, что для выделения эйлерова цикла в эйлеровом графе G достаточно придерживаться следующих правил:

1) выходим из произвольной вершины данного графа ; каждое пройденное ребро зачеркиваем;

2) никогда не идем по такому ребру , которое в рассматриваемый момент является перешейком, т.е. при удалении которого граф, образованный незачеркнутыми ребрами, распадается на две компоненты связности, имеющие хотя бы по одному ребру.

Перечислим этапы работы алгоритма [27]:

1) задать эйлеров граф G;

2) положить текущий граф равным G, а текущую вершину -- равной произвольной вершине v ? V(G);

3) выбрать произвольное, с учетом ограничения (см. ниже) ребро e текущего графа, инцидентное текущей вершине;

4) назначить текущей вторую вершину, инцидентную e;

5) удалить e из текущего графа и внести в список;

6) если в текущем графе еще остались ребра, вернуться на шаг 2;

7) в результате получим список ребер графа G в той последовательности, в которой они образуют эйлеров цикл.

Ограничение: если степень текущей вершины в текущем графе больше 1, нельзя выбирать ребро, удаление которого из текущего графа увеличит число компонент связности в нем.

Пример поиска эйлерова цикла:

Рисунок 2.5 Эйлеров граф

Для данного эйлерова графа результатом выполнения алгоритма будет:

v1 > v5 > v2 > v6 > v5 > v4 > v6 > v3 > v2 > v1.



3. Практическая часть - Реализация метода для определения замкнутых областей на поверхности четырех и шестиугольной решеток

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

Актуальность работы определяет то, что в настоящее время приходится для каждой формы (поверхности) решать уравнение Дирака и вычислять поправку к закону дисперсии.

В настоящей работе проводилось моделирование движения электрона на поверхности квадратной (рисунок 3.1 а) и гексагональной (рисунок 3.1 б) решеток. Точки пересечения линий называются узлами, на них мы и будем случайным образом помещать электроны. Сами линии будем называть связями или ребрами. В рамках одной из предыдущих научных работ уже исследовалась задача о перколяционном пути в решетке графена [22]. Целью же данной работы было отыскание замкнутых областей, составленных из связей - кластеров, которые иначе называются коралями.

Рисунок 3.1 Корали на квадратной (а) и гексагональной (б) решетках

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

Первым этапом исследования является размещение электронов в узлах прямоугольной решетки. Так как порог перколяции (протекания) для четырехугольной решетки составляет - 0,54, то займем 54% узлов. В случае гексагональной решетки - 0,67, следовательно, число электронов от общего числа узлов нужно выбрать равным 67% и выше. Метод был разработан для квадратной решетки, а затем распространен на графен (смотрите листинг А.1). Первоначальное распределение электронов представлено на рисунках 3.2 (на гексагональной решетке) и 3.3 (на квадратной решетке).

Рисунок 3.2 Первоначальное распределение электронов на квадратной решетке

Примечание - Здесь и далее на рисунках приняты следующие обозначения: белые точки - пустые ячейки без электронов, куда может сесть примесь, зеленые - узлы, уже занятые электронами графена, красным выделены замкнутые контуры.

Рисунок 3.3 Первоначальное распределение электронов на гексагональной решетке

Далее рассматриваем матрицу узлов слева направо сверху вниз, выбираем начальный узел рядом с пустым узлом и «распространяем волну», т.е. помечаем соседние узлы решетки в порядке возрастания. При этом маркируются только те узлы, в которые посажен электрон. На втором этапе происходит проверка, образуются ли замкнутый контур вокруг выбранного пустого узла. Для гексагональной решетки вводим дополнительную матрицу, содержащую информацию о наличии связей между узлами. Кроме того, необходимо хранить информацию об узлах, помеченных уже принадлежащих коралям, а также следить, чтобы внутри замкнутого контура находился хотя бы один узел, не содержащий электрон. Вышеперечисленные действия повторяются до тех пор, пока не будет рассмотрена вся матрица. Наш алгоритм нахождения коралей основывается на волновом алгоритме (алгоритме Ли) [19] с некоторыми модификациями. Данный алгоритм имеет квадратичную сложность. Результат работы алгоритма представлен на рисунках 3.4 - 3.5.

Рисунок 3.4 Распределение электронов после прогонки алгоритма на квадратной решетке

Рисунок 3.5 Распределение электронов после прогонки алгоритма на гексагональной решетке

Полученные результаты позволяют сделать вывод о возможности распространения данного метода на случай гексагональной решетки графена, а в дальнейшем и на случай искривленного графена. Основываясь на этих результатах, построим зависимость периметра замкнутого контура от количества контуров, с такой длиной (рисунки 3.6 - 3.7).

Рисунок 3.6 График зависимости количества замкнутых путей от длины замкнутого пути для разного количества электронов (53% и 55% при пороге перколяции 0.54) для квадратной решетки

Рисунок 3.7 График зависимости количества замкнутых путей от длины замкнутого пути для разного количества электронов (66% и 68% при пороге перколяции 0.67) для гексагональной решетки

В дальнейшем мы будем вычислять волновые функции, которые зависят от величины периметра (т.е. длины пути), через них мы сможем рассчитать различные характеристики примесного графена: восприимчивость, силу тока и т.д. Чтобы мы смогли вычислить данные характеристики для любого числа ячеек решетки и любых длин замкнутых областей, нам необходимо определить характер распределения этих периметров. Для этого мы определили вид степенной зависимости кол-ва путей от периметра, т.е. показатель степени.

Найдем степенную зависимость вида:

Для этого прологарифмируем выражение (3.1):

Сделав замену:

получим линейное уравнение, которое может быть аппроксимировано с помощью метода наименьших квадратов:

Используя программу MS Office Exel, выполним аппроксимацию и регрессионный анализ линейного уравнения (3.4). На рисунке 3.8 показаны результаты регрессионного анализа экспериментальных данных для квадратной решетки, при заполнении электронами 53% узлов.

Рисунок 3.8 Вывод итогов регрессионного анализа экспериментальных данных для квадратной решетки, при заполнении электронами 53% узлов

На рисунке 3.8 Y-пересечение является коэффициентом A, переменная X1 - коэффициентом b, подставим полученные значения в уравнение (3.4) и получим:

Произведем обратную замену:

И выразим отсюда Y:

Таким образом, степенная зависимость для квадратной решетки, при заполнении электронами 53% узлов:

Достоверность полученной аппроксимации (согласно данным регрессионной статистики, рисунок 3.8):

Были проведены аналогичные расчеты для экспериментальных данных для квадратной (заполнение электронами 55% узлов) и гексагональной (заполнение электронами 66% и 68% узлов) решеток (формулы (3.10) - (3.18)).

Для квадратной решетки:

Степенная зависимость для квадратной решетки, при заполнении электронами 55% узлов:

достоверность полученной аппроксимации:

Для гексагональной решетки при заполнении электронами 66% (формула (3.13)) и 68% (формула (3.14))узлов:

Степенная зависимость для гексагональной решетки, при заполнении электронами 66% узлов:

достоверность полученной аппроксимации:

Степенная зависимость для гексагональной решетки, при заполнении электронами 68% узлов:

достоверность полученной аппроксимации:

С помощью этой зависимости мы сможем получить закон распределения и вычислить интересующие нас физические величины. Графики аппроксимации степенной зависимостью представлены на рисунках 3.9-3.10.

Рисунок 3.9 График аппроксимации зависимости количества замкнутых путей от длины замкнутого пути для квадратной решетки: а) 53%; б) 55%

Рисунок 3.10 График аппроксимации зависимости количества замкнутых путей от длины замкнутого пути для гексагональной решетки: а) 66%; б) 68%

Мы выбрали вероятность распределения электронов близкую к пороговой вероятности (при которой образуется стягивающий кластер), т.к. свойство скейлинга выполняется вблизи порога перколяции. И для вероятности далеко от порога перколяции (0.75 например), наша функция не может быть аппроксимирована степенной функцией.

Обратимся теперь к теории скейлинга. В 1982 г. Вильсон получил нобелевскую премию по физике «за теорию критических явлений в связи с фазовыми переходами». Теория скейлинга строится на базе степенной зависимости некоторых свойств, причем показатель степени зависит от размерности пространства и от симметрии системы [20].

Энтропия Реньи может быть найдена по формуле [1]:

где a - постоянная решетки;

L - периметр замкнутого контура (в единицах a);

n - порядок энтропии.

Более высокие значения n, стремясь к бесконечности, дают энтропию Реньи, которая в большей степени определена через рассмотрение только самых высоких вероятностей событий. Более низкие значения n, стремящиеся к нулю, дают энтропию Реньи, которая в большей степени взвешивает все возможные события более равномерно, независимо от их вероятностей.

Формула (3.20) после усреднения дает:

Данный интеграл будет сходиться при условии, что . В нашем случае показатель степени для графена можно положить равным -3, получаем следующее выражение для энтропии Реньи:

Зависимость величины энтропии Реньи от ее порядка представлена на рисунке 3.11.

Рисунок 3.11 Зависимость величины энтропии Реньи от ее порядка

Минимальная проводимость для графена (рисунок 3.12) может быть найдена с помощью функций Грина для двумерных электронов на уровне Ферми:

где R - радиус круга (из-за конформной инвариантности форма границы неважна, можно выбрать окружность);

b - длина ребра.

Рисунок 3.12 Минимальная проводимость графена



Заключение

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

Алгоритм нахождения замкнутых контуров (коралей) был разработан на основе алгоритма Ли.

Построена зависимость количества замкнутых путей от их длины вблизи порога перколяции.

Определен вид степенной функции, который позволит рассчитать физические характеристики искривленного графена с примесями (восприимчивость, силу тока и т.д.), в том числе энтропию Реньи и минимальную проводимость для примесного графена.



Литература

1. Кормен, Т.Х. Алгоритмы: построение и анализ [Текст] / Т.Х. Кормен, Ч.И. Лейзерсон, Р.Л. Ривест, К. Штайн. 2-е ИЗД., пер. с англ. М.: Вильямс, 2010. 1296 с.

2. Кристофидес, Н. Теория графов. Алгоритмический подход [Текст] / Н. Кристофидес. М.: Мир, 1978. 158 с.

3. Морозов, С. В. Тезисы доклада II Международного форума по нанотехнологиям Rusnanotech [Текст] / С. В. Морозов, К. С. Новоселов, А. К. Гейм. М.: Москва, 2009. 790 с.

4. Мозговой, М. Занимательное программирование [Текст] / М. Мозговой. СПб.: Питер, 2004. 208 с.

5. Мюллер, Х. Скейлинг как фундаментальное свойство собственных колебаний вещества и фрактальная структура пространства-времени [Текст] / Х. Мюллер // Основания физики и геометрию - 2008. С. 189-209.

6. Перепелица, В.А. Дискретная оптимизация и моделирование в условиях неопределенности данных [Текст] / В.А. Перепелица, Ф.Б. Тебуева. М.: Академия Естествознания, 2012. 311 с.

7. Полунина, А.А. Моделирование процессов переноса в углеродных наноструктурах на основе явления перколяции [Текст] / А.А. Полунина, Н.Н. Конобеева // Материалы II Международной конференции молодых ученых «Математическое моделирование фрактальных процессов, родственные проблемы анализа и информатики». Нальчик, 28 ноября-1 декабря, 2012. С. 129-132.

8. Радченко, С.Г. Методология регрессионного анализа: монография [Текст] / С.Г. Радченко. К.: Корнийчук, 2011. С. 376.

9. Радченко, С.Г. Устойчивые методы оценивания статистических моделей: монография [Текст] / С.Г. Радченко. К.: Санспарель, 2005. С. 504.

10. Романовский, И. В. Дискретный анализ: учебное пособие для студентов, специализирующихся по прикладной математике и информатике [Текст] / И. В. Романовский. 3-е ИЗД., СПб.: Невский диалект, 2003. 320 с.

11. Тарасевич, Ю.Ю. Перколяция: теория, приложения, алгоритмы [Текст] / Ю.Ю. Тарасевич. М.: Едиториал УРСС, 2012. 112 с.



Приложение A

Листинг программы

Для написания программы использовался язык программирования с++.

Листинг А.1 - Программный код для реализации программы для определения замкнутых областей на поверхности четырех и шестиугольной решеток.

#include <stdlib.h>

#include <iostream>

#include <iomanip>

#include <windows.h>

#include <stdio.h>

#include <time.h>

#include <fstream>

#include <math.h>

#include <strstream>

#define sh4 4 //число узлов-соседей для квадратной решетки

#define sh6 3 //для гексагональной решетки

using namespace std;

HANDLE hStdout = GetStdHandle(STD_OUTPUT_HANDLE);

char cim=223;

int W; // ширина рабочего поля

int H; // высота рабочего поля

const int WALL = -1; // непроходимая ячейка

const int BLANK = -2; // свободная непомеченная ячейка

int len; // локальная длина пути

int count=0;//число коралей

int *length;//массив периметров

int **l_mas;

int dy[4] = {1,0, 0, -1};// смещения, соответствующие соседям

int dx[4] = {0,-1, 1, 0}; // ячейки справа, снизу, слева и сверху

int dx1[3] = {0,-1, 1};// смещения, соответствующие соседям

int dy1[3] = {1,0, 0}; // ячейки справа, сверху, и снизу

int dx2[3] = {0,-1, 1}; // смещения, соответствующие соседям

int dy2[3] = {-1,0, 0}; // ячейки слева, сверху, и снизу

const WORD Red = FOREGROUND_INTENSITY | FOREGROUND_RED;

const WORD Blue = FOREGROUND_INTENSITY | FOREGROUND_BLUE;

const WORD Yellow = FOREGROUND_INTENSITY | FOREGROUND_RED | FOREGROUND_GREEN;

const WORD Red_1 = FOREGROUND_RED;

const WORD Green = FOREGROUND_GREEN;

const WORD Blue_1 = FOREGROUND_BLUE;

const WORD Yellow_1 = FOREGROUND_RED | FOREGROUND_GREEN;

const WORD Purple_1 = FOREGROUND_RED | FOREGROUND_BLUE;

const WORD Aqua_1 = FOREGROUND_GREEN | FOREGROUND_BLUE;

const WORD White = FOREGROUND_RED | FOREGROUND_BLUE | FOREGROUND_GREEN ;

/*функция для вывода на экран квадратной матрицы*/

void print_matrix_cv_4(int **matrix, int m, int n)

{

int key;

for(int i=1;i<m-1;i++)

{

cout<<endl;

for(int j=1;j<n-1;j++)

{

key=matrix[i][j];

switch(key)

{

case -2:

SetConsoleTextAttribute(hStdout, Green);

cout<<setw(2)<<cim;

break;

case -1:

SetConsoleTextAttribute(hStdout, White);

cout<<setw(2)<<cim;

break;

case -3:

SetConsoleTextAttribute(hStdout, White);

cout<<setw(2)<<cim;

break;

case -10:

SetConsoleTextAttribute(hStdout, Red);

cout<<setw(2)<<cim;

break;

case -11:

SetConsoleTextAttribute(hStdout, Yellow);

cout<<setw(2)<<cim;

break;

default: {

SetConsoleTextAttribute(hStdout, Yellow_1);

cout<<setw(2)<<cim;

}

}

}

}

cout<<endl;

SetConsoleTextAttribute(hStdout,White);

}

/*функция для вывода на экран гексагональной матрицы*/

void print_matrix_cv_6(int **matrix, int m, int n) {

int key;

for(int i=1;i<m-1;i++)

{

cout<<endl;

for(int j=1;j<n-1;j++)

{

key=matrix[i][j];

switch(key)

{

case -2:

SetConsoleTextAttribute(hStdout, Green);

if(l_mas[i][j]!=-1)cout<<setw(2)<<""<<setw(2)<<cim;

else cout<<setw(2)<<cim<<setw(2)<<" ";

break;

case -1:

SetConsoleTextAttribute(hStdout, White);

if(l_mas[i][j]!=-1)cout<<setw(2)<<""<<setw(2)<<cim;

else cout<<setw(2)<<cim<<setw(2)<<" ";

break;

case -3:

SetConsoleTextAttribute(hStdout, White);

if(l_mas[i][j]!=-1)cout<<setw(2)<<""<<setw(2)<<cim;

else cout<<setw(2)<<cim<<setw(2)<<" ";

break;

case -10:

SetConsoleTextAttribute(hStdout, Red);

if(l_mas[i][j]!=-1)cout<<setw(2)<<""<<setw(2)<<cim;

else cout<<setw(2)<<cim<<setw(2)<<" ";break;

case -11:

SetConsoleTextAttribute(hStdout, Yellow);

if(l_mas[i][j]!=-1)cout<<setw(2)<<""<<setw(2)<<cim;

else cout<<setw(2)<<cim<<setw(2)<<" ";

break;

default: {

SetConsoleTextAttribute(hStdout, Yellow_1);

if(l_mas[i][j]!=-1)cout<<setw(2)<<""<<setw(2)<<cim;

else cout<<setw(2)<<cim<<setw(2)<<" ";

}

}

}

}

cout<<endl;

SetConsoleTextAttribute(hStdout,White);

}

void print_matrix(int **matrix,int W, int H)

{

for(int i=1;i<W-1;i++)

{

cout<<endl;

for(int j=1;j<H-1;j++)

cout<<setw(3)<<matrix[i][j];

}

cout<<endl;

}

/*функция распространения волны для квадратной матрицы*/

void spread_wave_4(int **matrix, int ax, int ay, int bx, int by)

{

// распространение волны

int d = 0, x, y, k, x1, y1;

matrix[ax][ay] = 0; // стартовая ячейка помечена 0

do {

for ( x = 0; x < W; x++ )

for ( y = 0; y < H; y++ )

if ( matrix[x][y] == d )//ячейка (x, y) помечена числом d

{

// проходим по всем непомеченным соседям

for ( k = 0; k < sh4; k++ )

{

y1 = y + dy[k];

x1 = x + dx[k];

if ( matrix[x1][y1] == BLANK )

matrix[x1][y1] = d + 1;

}

}

d++;

} while(d<W*H);

}

/*функция распространения волны для гексагональной матрицы*/

void spread_wave_6(int **matrix, int ax, int ay, int bx, int by)

{

// распространение волны

int d = 0, x, y, k, x1, y1;

matrix[ax][ay] = 0; // стартовая ячейка помечена 0

do {

for ( x = 0; x < W; x++ )

for ( y = 0; y < H; y++ )

if ( matrix[x][y] == d )//ячейка (x, y) помечена числом d

{

for ( k = 0; k < sh6; k++ )

{

if(l_mas[x][y]==0)

{

x1 = x + dx1[k];

y1 = y + dy1[k];

}

else

{

x1 = x + dx2[k];

y1 = y + dy2[k];

}

if ( matrix[x1][y1] == BLANK )

matrix[x1][y1] = d + 1;

}

}

d++;

} while(d<W*H);

}

/*функция восстановления пути для квадратной матрицы*/

int reconst_path_4(int **matrix, int ax, int ay, int bx, int by)

{

int d, x, y, k, key = 0, l = 0;

//для координат пути

int *label_x = (int*)calloc(H*W, sizeof(int));

int *label_y = (int*)calloc(H*W, sizeof(int));

//вспомогательные матрицы для маркировки

int **matrix_1, **matrix_2;

matrix_1 = (int **)calloc(W, sizeof(int*));

matrix_2 = (int **)calloc(W, sizeof(int*));

for (int y=0; y<W; y++)

{

matrix_1[y] = (int *)calloc(H, sizeof(int));

matrix_2[y] = (int *)calloc(H, sizeof(int));

}

for(int i=0;i<W;i++)

for(int j=0;j<H;j++)

matrix_1[i][j]=matrix[i][j];

// распространение волны

spread_wave_4(matrix_1, ax, ay, bx, by);

//Проход 1//восстановление пути и поиск замкнутых контуров//

for(int i=0;i<W;i++)

for(int j=0;j<H;j++)

matrix_2[i][j]=matrix_1[i][j];

d = matrix_2[bx][by]; //длина кратчайшего пути из (ax,ay) в (bx,by)

x = bx;

y = by;

key = d;

int lb = key;

label_x[0] = ax;

label_y[0] = ay;

while(d > 0)

{

d--;

for (k = 0; k < sh4; k++)

if (matrix_2[x + dx[k]][y + dy[k]] == d)

{

matrix_2[x + dx[k]][y + dy[k]] = -11;

x = x + dx[k];

y = y + dy[k];

lb--;

label_x[lb] = x;

label_y[lb] = y;

break;

}

}

matrix_2[ax][ay] = 0;

//Проход 2//Маркировка//

for(int i=0;i<W;i++)

for(int j=0;j<H;j++)

matrix_1[i][j]=matrix[i][j];

for(int i=0;i<H*W;i++)

matrix_1[label_x[i]][label_y[i]]=matrix_2[label_x[i]][label_y[i]];

spread_wave_4(matrix_1, ax, ay, bx, by);

//Проход 2//восстановление пути и поиск замкнутых контуров//

for(int i=0;i<W;i++)

for(int j=0;j<H;j++)

matrix_2[i][j]=matrix_1[i][j];

len = matrix_2[bx][by];

d = matrix_2[bx][by];

lb = key;

x = bx;

y = by;

while(d > 0)

{

d--;

for (k = 0; k < sh4; k++)

if (matrix_2[x + dx[k]][y + dy[k]] == d)

{

l=0;

if(ax ==(x + dx[k])&&ay==(y + dy[k]))goto next;

for (int t = 0; t < sh4; t++)

//проверка на "слипание" контура

{

int x2 = x + dx[t]+dx[k];

int y2 = y + dy[t]+dy[k];

if(ax != x2 && ay !=y2)

if( matrix_2[x + dx[k] + dx[t]][y + dy[k] + dy[t]]==-11)

{

l++;

matrix_2[x+dx[k]][y+dy[k]]=-3;

}

}

if(l>0)goto M2;

next:

matrix_2[x + dx[k]][y + dy[k]] = -12;

x = x + dx[k];

y = y + dy[k];

lb++;

label_x[lb] = x;

label_y[lb] = y;

break;

M2:

;

}

}

if(label_x[lb] == ax && label_y[lb] == ay)

{

count++;

label_x[key] = bx;

label_y[key] = by;

matrix_2[bx][by] = -12;

for(int i=0;i<H*W;i++)

matrix[label_x[i]][label_y[i]]= matrix_2[label_x[i]] [label_y[i]];

for(int i=0;i<W;i++)

for(int j=0;j<H;j++)

if(matrix[i][j]==-11||matrix[i][j] == -12) matrix[i][j]=-10;

length[count]=key+len;

goto end;

}

else

{

for(int i=0;i<W;i++)

for(int j=0;j<H;j++)

matrix_2[i][j]=matrix[i][j];

for(int i=0;i<H*W;i++)

{

label_x[lb]=0;

label_y[lb]=0;

}

}

end:

for (int i=0; i<W; i++)

{

free(matrix_1[i]);

free(matrix_2[i]);

}

free(matrix_1);

free(matrix_2);

free(label_x);

free(label_y);

return 0;

}

/*функция восстановления пути для гексагональной матрицы*/

int reconst_path_6(int **matrix, int ax, int ay, int bx, int by)

{

int d, x, y, k, x1, y1, x2, y2, key = 0, l = 0;

//для координат пути

int *label_x = (int*)calloc(H*W, sizeof(int));

int *label_y = (int*)calloc(H*W, sizeof(int));

//вспомогательные матрицы для маркировки

int **matrix_1, **matrix_2;

matrix_1 = (int **)calloc(W, sizeof(int*));

matrix_2 = (int **)calloc(W, sizeof(int*));

for (int y=0; y<W; y++)

{

matrix_1[y] = (int *)calloc(H, sizeof(int));

matrix_2[y] = (int *)calloc(H, sizeof(int));

}

for(int i=0;i<W;i++)

for(int j=0;j<H;j++)

matrix_1[i][j]=matrix[i][j];

// распространение волны

spread_wave_6(matrix_1, ax, ay, bx, by);

//Проход 1//восстановление пути и поиск замкнутых контуров//

for(int i=0;i<W;i++)

for(int j=0;j<H;j++)

matrix_2[i][j]=matrix_1[i][j];

d = matrix_2[bx][by]; //длина кратчайшего пути из (ax,ay) в (bx,by)

x = bx;

y = by;

key = d;

int lb = key;

label_x[0] = ax;

label_y[0] = ay;

while(d > 0)

{

d--;

for (k = 0; k < sh6; k++)

{

if(l_mas[x][y]==0)

{

x1 = x + dx1[k];

y1 = y + dy1[k];

}

else

{

x1 = x + dx2[k];

y1 = y + dy2[k];

}

if (matrix_2[x1][y1] == d)

{

matrix_2[x1][y1] = -11;

x = x1;

y = y1;

lb--;

label_x[lb] = x;

label_y[lb] = y;

break;

}

else

{

x1 = x;

y1 = y;

}

}

}

matrix_2[ax][ay] = 0;

//Проход 2//Маркировка//

for(int i=0;i<W;i++)

for(int j=0;j<H;j++)

matrix_1[i][j] = matrix[i][j];

for(int i=0;i<H*W;i++)

matrix_1[label_x[i]][label_y[i]] =matrix_2[label_x[i]][label_y[i]];

spread_wave_6(matrix_1, ax, ay, bx, by);

//Проход 2//восстановление пути и поиск замкнутых контуров//

for(int i=0;i<W;i++)

for(int j=0;j<H;j++)

matrix_2[i][j] = matrix_1[i][j];

len = matrix_2[bx][by];

d = matrix_2[bx][by];

lb = key;

x = bx;

y = by;

while(d > 0)

{

d--;

for (k = 0; k < sh6; k++)

{

if(l_mas[x][y]==0)

{

x1 = x + dx1[k];

y1 = y + dy1[k];

}

else

{

x1 = x + dx2[k];

y1 = y + dy2[k];

}

if (matrix_2[x1][y1] == d)

{

l=0;

if(ax == (x1) && ay == (y1))goto next;

for (int t = 0; t < sh6; t++)

//проверка на "слипание" контура

{

if(l_mas[x1][y1]==0)

{

x2 = x1 + dx1[t];

y2 = y1 + dy1[t];

}

else

{

x2 = x1 + dx2[t];

y2 = y1 + dy2[t];

}

if(ax != x2 && ay !=y2)

if( matrix_2[x2][y2]==-11)

{

l++;

matrix_2[x1][y1] = -3;

}

}

if(l>0)goto M2;

next:

matrix_2[x1][y1] = -12;

x = x1;

y = y1;

lb++;label_x[lb] = x;

label_y[lb] = y;

break;

M2:

;

}

}

}

if(label_x[lb] == ax && label_y[lb] == ay )

{

count++;

label_x[key] = bx;

label_y[key] = by;

matrix_2[bx][by] = -12;

for(int i=0;i<H*W;i++)

matrix[label_x[i]][label_y[i]] = matrix_2[label_x[i]][label_y[i]];

for(int i=0;i<W;i++)

for(int j=0;j<H;j++)

if(matrix[i][j]==-11||matrix[i][j] == -12) matrix[i][j]=-10;

length[count]=key+len;

goto end;

}

else

{

for(int i=0;i<W;i++)

for(int j=0;j<H;j++)

matrix_2[i][j]=matrix[i][j];

for(int i=0;i<H*W;i++)

{

label_x[i]=0;

label_y[i]=0;

}

lb = 0;

}

end:

for (int i=0; i<W; i++)

{

free(matrix_1[i]);

free(matrix_2[i]);

}

free(matrix_1);

free(matrix_2);

free(label_x);

free(label_y);

return 0;

}

int main()

{

srand((unsigned)time(NULL));

double c,p=0;

int menu;

int **matrix;

cout<<"Enter the number of action \n 1 - Start algorithm for square grid \n 2 - Start algorithm for hexagonal grid"<<endl;

cin>>menu;

cout<<"Enter size matrix MxN"<<endl;

cin>>W>>H;

int *lc = (int*)calloc(H*W, sizeof(int));

length = (int*)calloc(H*W, sizeof(int));

matrix = (int **)calloc(W, sizeof(int*));

for (int i=0; i<W; i++)

matrix[i] = (int *)calloc(H, sizeof(int));

/*задаем пороговую вероятность р*/

cout<<"Enter the probability distribution of the electrons =";

cin>>p;

/*генерируем массив*/

for(int i=0;i<W;i++)

for(int j=0;j<H;j++)

if(i==0 || j==0 || i==W-1 || j==H-1)matrix[i][j]=-3;

for(int i=1;i<W-1;i++)

for(int j=1;j<H-1;j++)

{

c=float(rand()%100)/100;

if(c>p)

matrix[i][j]=WALL;

else matrix[i][j]=BLANK;

}

switch(menu)

{

case 1:

{

/*Вывод исходной матрицы*/

print_matrix_cv_4(matrix,W,H);

/*Прогонка алгоритма*/

for(int i=2;i<W-2;i++)

for(int j=2;j<H-2;j++)

if(matrix[i][j]==WALL)

{

if(matrix[i-1][j-1]==BLANK)

if(matrix[i+1][j+1]==BLANK)

reconst_path_4( matrix,i-1, j-1, i+1, j+1);

}

/*Вывод матрицы после выполнения алгоритма*/

print_matrix_cv_4(matrix,W,H);

break;

}

case 2:

{

l_mas = (int **)calloc(W, sizeof(int*));

for (int i=0; i<W; i++)

l_mas [i] = (int *)calloc(H, sizeof(int));

for (int i=0; i<W; i+=2)

for (int j=0; j<H; j+=2)

l_mas[i][j]=-1;

for (int i=1; i<W; i+=2)

for (int j=1; j<H; j+=2)

l_mas[i][j]=-1;

/*Вывод исходной матрицы*/

print_matrix_cv_6(matrix,W,H);

/*Прогонка алгоритма*/

for(int i=2;i<W-2;i++)

for(int j=2;j<H-2;j++)

if(matrix[i][j]==WALL)

{

if(l_mas[i][j]==0)

{

if(matrix[i+dx1[0]][j+dy1[0]] == BLANK && matrix[i+dx1[1]][j+dy1[1]] == BLANK)

reconst_path_6( matrix,i+dx1[0], j+dy1[0], i+dx1[1], j+dy1[1]);

else if( matrix[i+dx1[1]] [j+dy1[1]] == BLANK && matrix[i+dx1[2]][j+dy1[2]] == BLANK)reconst_path_6( matrix,i+dx1[1], j+dy1[1], i+dx1[2], j+dy1[2]);

else if( matrix [i+dx1[0]][j+dy1[0]] == BLANK && matrix[i+dx1[2]][j+dy1[2]] ==BLANK) reconst_path_6( matrix,i+dx1[0], j+dy1[0], i+dx1[2], j+dy1[2]);

}

else

{

if(matrix[i+dx2[0]][j+dy2[0]] == BLANK && matrix[i+dx2[1]][j+dy2[1]] == BLANK)reconst_path_6( matrix,i+dx2[0], j+dy2[0], i+dx2[1], j+dy2[1]);

else if( matrix[i+dx2[1]] [j+dy2[1]] == BLANK && matrix[i+dx2[2]][j+dy2[2]] == BLANK)reconst_path_6( matrix,i+dx2[1], j+dy2[1], i+dx2[2], j+dy2[2]);

else if( matrix[i+dx2[0]] [j+dy2[0]] == BLANK && matrix[i+dx2[2]][j+dy2[2]] == BLANK)reconst_path_6( matrix,i+dx2[0], j+dy2[0], i+dx2[2], j+dy2[2]);

}

}

/*Вывод матрицы после выполнения алгоритма*/

print_matrix_cv_6(matrix,W,H);

free(l_mas);

break;

}

default:

{

cout<<"\n Error: Value incorrect!";

}

}

/*Вывод данных для построения зависимости количества путей от их периметра*/

for(int i=1;i<count+1;i++)

for(int j=8;j<W*H;j++)

if(length[i]==j)lc[j]++;

strstream fname;

if(menu==1)fname<<"for_square_grid-";

if(menu==2)fname<<"for_hexagonal_grid-";

fname<<"P(L)_("<<W-2<<"x"<<H-2<<")_p="<<p<<".txt"<<ends;

ofstream fp(fname.str());

for(int i = 8; i< H*W; i++)

if(lc[i]!=0)fp<<i<<" "<<lc[i]<<endl;

fp.close();

for (int i=0; i<W; i++)

free(matrix[i]);

free(matrix);

free(length);

free(lc);

system("pause");

Размещено на Allbest.ru