Подсчет гамильтоновых циклов на прямоугольных решетках, цилиндрах и торах методом матрицы переноса тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат физико-математических наук Караваев, Артем Михайлович

• Караваев, Артем Михайлович
• кандидат физико-математических наук
• 2012

Оглавление диссертации кандидат физико-математических наук Караваев, Артем Михайлович

Оглавление

Введение

Терминология и система обозначений

Вспомогательная терминология

Общая схема алгоритма

Состояния и переходы

Список обозначений

1 Обзор литературы

1.1 Подсчет циклов в сеточных графах

1.2 Константа связности

1.3 Вычислительные особенности

метода матрицы переноса

1.4 Особенности распараллеливания

1.5 Явные формулы

и рекуррентные соотношения

1.6 Экстраполяция числовых

последовательностей

2 Метод матрицы переноса

2.1 Общее описание метода

2.2 Применение метода матрицы переноса

к поставленным задачам

2.3 Примеры применения метода

к небольшим графам

2.3.1 Число циклов на решетках х Уп и У4 х Тп

2.3.2 Число циклов на цилиндрах Сз х СРП и С4 х Уп

2.3.3 Число циклов на торах Сз х Сп и С4 х Сп

3 Кодирование состояний в задачах подсчета циклов

3.1 Кодирование состояний

на решетках и цилиндрах

3.1.1 Переходы между состояниями

3.1.2 Метод динамического программирования

3.1.3 Методы распараллеливания

3.1.4 Оптимизация

3.2 Кодирование состояний на торах

3.2.1 Переходы между состояниями

3.2.2 Метод динамического программирования

3.2.3 Количество состояний

3.2.4 Оптимизация

3.3 Выводы к главе 3

4 Предельные свойства в задачах подсчета циклов

4.1 Рекуррентные соотношения

4.1.1 Алгоритм вывода рекуррентных соотношений

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

4.2 Асимптотика последовательностей

4.2.1 Ускорение сходимости

4.3 Асимптотика для циклов на торе

4.3.1 Гипотеза о виде асимптотики

4.4 Выводы к главе 4

Заключение

Список использованных источников

Введение диссертации (часть автореферата) на тему «Подсчет гамильтоновых циклов на прямоугольных решетках, цилиндрах и торах методом матрицы переноса»

Введение

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

В работе рассматриваются три семейства графов: прямоугольные решетки Тт х цилиндры Ст х Уп и торы Ст х Сп (рис. 1).

Рисунок 1 — Примеры сеточных графов. Слева направо: решетка Т4 х цилиндр С8 х и тор Сб х

Любая решетка порождается прямым произведением двух простых цепей Угп и УТ1, первая из которых имеет т вершин, а вторая — п. Будем называть число т шириной решетки (протяженность слева направо), а п - ее длиной (протяженность снизу вверх). Символом Ст х Тп обозначается цилиндр, представляющий собой прямое произведение цикла Ст из т вершин (периметр цилиндра) и цепи Уп из тг вершин (высота, или образующая цилиндра). Тор Ст х Сп является прямым произведением двух циклов Ст и Сп.

Маршрут в графе [1] называется замкнутым, если его начальная вершина совпадает с конечной. Маршрут называется простой цепью, если все его вершины различны. Замкнутая цепь называется циклом, а простая замкнутая цепь — простым циклом. Простой цикл, проходящий через все вершины графа, называется гамилъто-новым. Поскольку работа посвящена только гамильтоновым циклам, будем для краткости называть их просто циклами, если это не порождает неоднозначной интерпретации.

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

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

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

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

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

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

Степень разработанности проблемы. Из обзора ранее выполненных работ следует, что задаче подсчета циклов на решетках посвящена достаточно обширная литература, в которой приводятся разнообразные попытки ее решения. Широко представлены работы как чисто математической, так и физической направленности. Тем не менее, предыдущие авторы далеко не в полной мере задействовали потенциал точных методов, основанных на использовании рекуррентных соотношений. Недостаточно внимания уделялось возможностям получения новых данных с помощью вычислительных кластеров, а также анализу эффективности распараллеливания такого класса алгоритмов. Устранение этих недостатков позволило существенно расширить набор тех графов, для которых задачу подсчета циклов можно считать решенной. В то же время, в результате исследований выяснилось, что наиболее узким местом многих методов являются проблемы, связанные с архитектурой современных кластеров.

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

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

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

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

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

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

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

1. Проанализировать и систематизировать известные результаты, выявив их достоинства и недостатки.

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

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

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

5. Существенно увеличить точность определения константы связности по сравнению с известными методами.

6. Проверить корректность выводов полевой О(п) модели среднего поля, предполагающей сворачивание решетки в тор с последующим сведением дискретной задачи к непрерывной.

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

1. Разработана эффективная схема кодирования состояний для подсчета числа гамильтоновых циклов на прямоугольных решетках Ут х Уп, цилиндрах 6m х и торах Cm х Сп, на основе которой предложен новый параллельный алгоритм.

2. Расширен набор точных значений для количества циклов на решетках, цилиндрах и торах.

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

4. Уточнено значение универсальной константы связности для всех трех рассматриваемых семейств графов: и = 1.472799±0.000003.

5. Показано, что асимптотика количества циклов на торах Gm х Сп при fi —> оо имеет качественно иной вид, нежели на решетках ^т х и цилиндрах Cm х СРП, раздваиваясь при четном m, что свидетельствует о необходимости уточнения основных принципов проведения расчетов в рамках стандартной О(п) модели среднего поля.

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

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

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

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

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

По теме исследования было опубликовано 14 научных работ: 5 научных статей [2-6], 2 из которых ([4,6]) в журналах, рекомендованных ВАК для публикации; 9 трудов и тезисов всероссийских и международных конференций [7-15]. Результаты диссертационной работы докладывались лично автором и обсуждались на международных конференциях по параллельным вычислениям «Высокопроизводительные параллельные вычисления на кластерных системах» (2009) и «Параллельные вычислительные технологии» (дважды, в 2010 и 2011 г.), на международной конференции по вычислительной механике и современным прикладным программным системам (ВМ-СППС '2011), на конференции «Математика, экономика, менеджмент: 100 лет со дня рождения Л. В. Канторовича», на научном семинаре кафедры исследования операций математико-механического факультета СПбГУ под руководством зав. каф. д. ф.-м. н., профессора Н. Н. Петрова, (дважды, в 2010 и 2011 г.), а также на научных семинарах кафедры прикладной математики и кибернетики ПетрГУ.

Диссертация состоит из введения, раздела с терминологией, четырех глав, заключения и списка источников. Общий объем диссертации составляет 145 страниц (включая библиографию из 52 источников). Работа содержит 36 иллюстраций и 21 таблицу.

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

с точки зрения теории сложности, показывается ее связь с физическими моделями, демонстрируется место метода матрицы переноса и возникающих в связи с его применением рекуррентных соотношений, обсуждаются методы экстраполяции числовых последовательностей. Вторая глава посвящена теоретическим основам метода матрицы переноса и связи получаемых этим методом решений с линейными рекуррентными соотношениями. Помимо этого описания, приводятся примеры «ручного» применения метода к задаче подсчета циклов на решетках и цилиндрах с параметром т = 3,4, а также предлагается алгоритм определения всех достижимых состояний, возникающих при построении циклов. В этой же главе выводится явная формула для числа циклов на торах Сз х Сп и выписывается (без вывода) формула для числа циклов на торах С4 х Сп, из которой следует раздвоение асимптотики при п —> оо. Глава 3 содержит наиболее важный результат, полученный в работе: схему кодирования состояний на решетках, цилиндрах и торах, описанную с единых позиций. Также глава содержит описание деталей программной реализации метода матрицы переноса и применяемых при расчетах алгоритмических оптимизаций. Полученные с помощью методов главы 3 данные используются далее в четвертой главе, в которой предложен метод вывода рекуррентных соотношений и исследуются асимптотические свойства моделей. В этой главе применяются методы ускорения сходимости числовых последовательностей для уточнения значения константы связности, а также выполняется анализ числовых последовательностей для случая торов, из которого следует новая гипотеза о виде асимптотики. Заключение дает исчерпывающий анализ полученных результатов, завершающийся выводами и рекомендациями возможных вариантов продолжения работы.

Терминология и система обозначений

Вспомогательная терминология

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

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

Решетку будем изображать на плоскости, нумеруя ее слои снизу вверх и располагая их друг над другом так, чтобы горизонтальные ребра были изображены горизонтально, а вертикальные — вертикально, так, как указано на рис. 2(а).

(а) (б) (в)

Рисунок 2 — Развертка сеточных графов на плоскости вместе с циклами.

Слева направо: решетка У 4 х У6, цилиндр С4 х У6 и тор 64 х С6

Цилиндр может быть получен из решетки путем наложения циклических граничных условий на ее левую и правую границы. Поскольку любая цепь 7т трансформируется в цикл Ст, путем добавления ребра, связывающего концевые вершины цепи, цилиндр допускает представление в виде п копий цикла Ст, связанных друг с другом по тому же принципу, как и в случае решеток. При использовании изложенной выше схемы разметки вершин, добавленные ребра будут для всех слоев к инцидентны вершинам (т, к) и (1,к). Будем называть такие ребра обратными горизонтальными ребрами. Именно они и обеспечивают циклические граничные условия, (рис. 2(6)).

Тор может быть представлен в виде п копий цикла Ст, соединенных по той же самой схеме, что и в случае цилиндра, но с дополнительным условием; слои с номерами 1 и п соединяются друг с другом обратными вертикальными ребрами. Эти ребра инцидентны вершинам с одинаковыми номерами внутри слоя и также как на развертке цилиндра изображаются короткими отрезками (рис. 2(в)).

Разрез сеточного графа по слою к — это разбиение вершин графа на два подмножества так, чтобы вершины слоев с номерами ) ^ к

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

В целях единообразного описания алгоритма полезно ввести разрезы по слоям к = 0 и к = п. Первый из этих разрезов (по несуществующему нулевому слою) отделяет пустое пространство под графом от самого графа, а второй отделяет граф от пустого пространства над ним.

б

5 ¿.

_ . а .

4

3

2 3

- •

4

разрез по слою к=6

разрез по слою к=4

слой к=3

разрез по слою к=0

будущее

ГТ .—»

I ■

I (

—4—

> прошлое

(б)

Рисунок 3 — Слои (уровни) и разрезы в графе Т4 х Уб: (а) Примеры слоев и разрезов; (б) Построенная в прошлом часть «цикла»

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

2

Общая схема алгоритма построения цикла

Построение цикла представляет собой итерационный процесс, на каждой итерации которого линия разреза перемещается от одного уровня к к следующему, причем вначале к = 0. Первая итерация начинается с выбора некоторых горизонтальных ребер на уровне 1, по которым будет проходить цикл. Ребра выбираются произвольно, но так, чтобы они были инцидентны всем вершинам 1-го слоя, иначе условие гамильтоновости окажется нарушенным. Множество выбранных горизонтальных ребер единственным образом определяет набор вертикальных ребер, соединяющих первый слой со вторым. После фиксации вертикальных ребер линия разреза перемещается к слою к = 1 (рис. 4(а)).

12 3 4

(а)

1 2 3 (б)

•---•

2 , »----. 2 , 1---Ч I-1 ---- 2

1 , I-< Н---( 1-1 > 1 . > 1 >----( |-1 1

12 3 4

(в)

3

I

II

4

Рисунок 4 — Этапы построения цикла: (а) начальная итерация; (б) выбор горизонтальных ребер; (в) фиксация вертикальных ребер и перемещение линии разреза на следующий уровень

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

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

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

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

Состояния и переходы

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

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

Рассмотрим изображенную на рис. 5 слева решетку У в х У 8, цикл в ней и разрез по слою к = 5. Прошлое выделено пунктирной рамкой. Расположенная в прошлом часть «цикла» состоит из двух цепей. В будущем изображен один из вариантов соединения этих цепей.

Рисунок 5 — Допустимое состояние, возникающее при построении цикла

на уровне к = 5

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

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

Множество дуг, возможно пустое, закодированное особым образом, будем называть состоянием на решетке. Способ такого представления состояния не зависит от номера слоя. Каждую дугу можно обозначить парой чисел (р, ц), в которой р и q — номера вершин слоя, соединенные этой дугой. Будем предполагать, что всегда выполняется условие р < Я •

Сформулированные в предыдущем разделе правила накладывают ограничения на взаимное расположение дуг в каждом состоянии. Если состояние содержит больше одной дуги, то упорядочив каждую пару дуг (рт, Цт) и (рг, Цг) так, чтобы выполнялось неравенство рт < р2, потребуем выполнения условия р2 > V Ц2 < • С учетом принятого способа изображения, это условие соответствует тому, что либо концы одной дуги находятся «правее» концов другой, либо между ними. Будем считать, что для состояний, содержащих только одну дугу или вообще без дуг, данные условия всегда выполняются. Состояние, удовлетворяющее сформулированным выше требованиям, назовем возможным состоянием, а всю их совокупность — множеством возможных состояний.

Особый случай состояния с пустым множеством дуг соответствует разрезам по слоям к = 0 и к = тг. Для удобства описания алгоритма полезно различать эти ситуации. Состояние, соответствующее значению к = 0 будем называть начальным, а случаю к = п — финальным.

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

ляет разбить множество всех возможных состояний на множество допустимых (достижимых) состояний и множество недопустимых (недостижимых) состояний. Начальное и финальное состояния по определению будем считать допустимыми. Количество допустимых состояний будет обозначаться через М. Для удобства ссылок на конкретное состояние, перенумеруем их произвольным образом числами от 1 до М так, чтобы начальное состояние имело номер 1, а финальное — номер М.

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

Переходом из допустимого состояния в в допустимое состояние 1 назовем шаг в будущее, при котором из состояния б на одном уровне получается состояние \ на следующем уровне сеточного графа. В этом случае будем говорить, что из состояния б можно перейти в состояние 1:. На рис. 6 показаны переходы, возникающие при построении цикла на решетке У в х (см. рис. 5).

Т I •-— •-•----•-• •—•—•-•----• — «

+ +

(а) (б)

Рисунок 6 — Переходы между состояниями, показанными на рис. 5: (а) от слоя к = 2 к слою к = 3; (б) от слоя к = 5 к слою к = б

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

Список обозначений

В работе приняты следующие обозначения с соответствующим

описанием. I

единичная матрица;

символ Кронекера Ьц множество N и {0};

о, \ф)\

е

п

•Ртп X Т'тх

Ст х Сп Т

С, вы

Ак

— граф — простая цепь из п вершин (узлов);

— граф — простой цикл из п вершин (узлов);

— решетка шириной т и высотой п вершин;

— цилиндр из тп вершин по периметру с образующей из п вершин;

— тор с периметрами из т и п вершин;

— матрицы переноса;

— производящие функции;

— один из корней характеристического полинома рекуррентного соотношения. В тех случаях, когда необходимо явно указать зависимость от параметра т, будем писать Л^т);

Л — максимальный по модулю корень характеристиче-

ского полинома. Для указания явной зависимости от тп будем писать Л(т);

[кт) — числовая последовательность щ, Х4,..., хт>...;

хт — элемент последовательности (хт). Значение кон-

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

я — универсальная константа связности

к — НгПгп^оо хт;

(ап) — числовая последовательность а-], а2,..., ап,____Ес-

ли элементы последовательности зависят от параметра т, будем писать (ап(т));

ап — элемент последовательности (ап). Как правило,

обозначает количество циклов в каком-либо сеточном графе;

Мт — количество слов Моцкина порядка т

$ — финальное состояние;

[Ут х Уп] — символ пояснения. Определяет объект перечисления, в контексте которого идут дальнейшие рассуждения. Внутри квадратных скобок указан сеточный граф. Например, запись [Ут х Уп] буквально означает «гамильтоновы циклы на решетке размером тп х п», а запись [Сз х Уп] означает «производящая функция для количества гамиль-тоновых циклов на цилиндре 3 х п»;

Заключение диссертации по теме «Дискретная математика и математическая кибернетика», Караваев, Артем Михайлович

Основные выводы настоящей главы опубликованы в [14,15].

Заключение

Работа проделана в соответствии с поставленной целью, получены следующие основные результаты.

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

Учет выявленных недостатков позволил разработать более эффективную схему кодирования состояний и новый параллельный алгоритм, позволивший рассчитать количество циклов на решетках Ут X Уп и цилиндрах Ст х для т < 22 и п ^ 100. Следствием эффективности предложенной схемы явился тот факт, что задача подсчета циклов на цилиндрах оказалась не более сложной, чем на решетках. Ранее считалось, что цилиндр для расчетов является существенно более сложным графом, чем решетка. Дальнейшее развитие схемы кодирования позволило посчитать число циклов на торах Стх Сп для т ^ 10 ип ^ 500, полностью накрывая результаты работы [38], полученные как точными, так и приближенными методами.

Удобным способом систематизации полученных результатов, который помимо этой функции удобен для анализа данных, является запись решения задачи в виде линейного рекуррентного соотношения. Такие соотношения удалось получить для решеток Ут х СРП при т ^ 14, цилиндров Ст х при т ^ 16 и торов Ст х Сп при т ^ 8. С этой целью был разработан специальный алгоритм, основанный на р-адическом разложении. Алгоритм превзошел по эффективности известные на сегодняшний день инструменты для вывода рекуррентных соотношений.

Полученные рекуррентные соотношения и конечные отрезки последовательностей (ап) позволили с большой точность определить главные члены асимптотики роста последовательностей количества циклов для всех трех рассматриваемых семейств при фиксированном значении параметра т и п —> оо. Эти результаты позволили уточнить значение универсальной константы связности я — 1.472799 ± 0.000003. Предложенная оценка оказывается втрое более точной, чем предыдущая, полученная в работе [28] я = 1.472801 ± 0.000010.

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

Полученные результаты открывают широкие возможности для дальнейшего исследования. Оказывается, что предлагаемые в работе рекомендации полезны для решения аналогичных задач перечислительной комбинаторики, в которых может быть использован метод матрицы переноса. Например, подсчет гамильтоновых цепей на решетках х Тп и цилиндрах Ст х Уп [2,13], подсчет всех простых циклов [11], задача о расстановке шахматных королей [12].

Интересным представляется расширение физических моделей в следующем направлении. Как известно, гамильтоновых циклов на решетках 7т х не существует, если произведение т • п нечетно. В этом случае моделью плотноупакованной макромолекулы может служить так называемый «предгамильтонов цикл» — простой цикл, проходящий по всем вершинам графа, кроме одной. Начальные представления об этой модели дает работа [6], также выполненная в процессе диссертационного исследования.

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

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

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

Логичным продолжением исследования стала бы работа, в которой также систематически проработана методика исследования трехмерных решеток, а также решеток с более сложной структурой: трехвалентных (графен, углеродная нанотрубка), шестивалентных и т. д.

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

Список литературы диссертационного исследования кандидат физико-математических наук Караваев, Артем Михайлович, 2012 год

Список использованных источников

[1] Харари Ф. Теория графов: Пер. с англ / Ф. Харари. — 2-е изд. — М. : Едиториал УРСС, 2003. — 296 с.

[2] Караваев А. М. Усовершенствованный метод матрицы переноса для подсчета гамилътоновых цепей на прямоугольных решетках и цилиндрах [электронный ресурс] / А. М. Караваев // Информационные процессы, 2011. — Т. 11. — №3. — режим доступа: http://www.jip.ru/2011/ll-3-2011.htm, свободный. - С. 336-347.

[3] Караваев А. М. Усовершенствованный метод матрицы переноса для подсчета гамилътоновых циклов на прямоугольных решетках и цилиндрах / А. М. Караваев // Актуальные проблемы гуманитарных и естественных наук, 2011. — №4(27). — С. 16-24.

[4] Караваев А. М. Количество гамилътоновых циклов на торе Сз х Сп / А. М. Караваев // Естественные и технические науки, 2011. — №6(56). — С. 30-32.

[5] Караваев А. М. Кодирование состояний в методе матрицы переноса для подсчета гамилътоновых циклов на прямоугольных решетках, цилиндрах и торах [электронный ресурс] / А. М. Караваев // Информацион-

ные процессы, 2011. — Т. 11. — №4. — режим доступа: http://www.jip.ru/2011/ll-4-2011.htm, свободный. — С. 476499.

[6] Караваев А. М. Подсчет предгамилътоновых циклов на семействах решеточных графов / А. М. Караваев // Ученые записки петрозаводского государственного университета, 2011. — №6(119). - С. 97-102.

[7] Караваев А. М. Практическое сравнение алгоритмов типа backtrack для перечисления простых циклов в графе / А. М. Караваев // Сборник научных трудов по материалам международной научно-практической конференции «Современные направления теоретический и прикладных исследований '2010». — Т. 32. — Одесса : Черноморье, 2010. — С. 9-13.

[8] Караваев А. М. Эффективность распараллеливания явных формул для подсчета коротких циклов в графе : труды [электронный ресурс] /A.M. Караваев, А. Н. Воропаев // Сборник трудов международной научной конференции «Параллельные вычислительные технологии '2010». — г. Уфа : Уфимский государственный авиационный технический ун-т, 2010. — 1 CD-ROM. - С. 486-497.

[9] Караваев А. М. Возможности метода динамического программирования для подсчета числа циклов в графе : тезисы / А. М. Караваев // «Научное творчество молодежи» : XIII Всероссийская научно-практическая конференция, г. Анжеро-Судженск : Томск : Из-во Том. ун-та, 2009. — Ч. 1. — С. 41-43.

[10] Караваев А. М. Эффективность параллельной реализации метода динамического программирования для подсчета количества простых циклов в графе : материалы / А. М. Караваев // «Научное творчество молодежи» : материалы XIV всероссийской научно-практической конференции, г. Анжеро-Судженск. — Томск : Из-во Том. ун-та, 2010. — Ч. 1. — С. 43-46.

[11] Караваев А. М. Количество простых циклов на двумерной квадратной решетке : материалы / А. М. Караваев // «Высокопроизводительные параллельные вычисления на кластерных системах» : материалы IX Международной конференции-семинара. г. Владимир : Владимирский государственный университет, 2009. — С. 202-207

[12] Караваев А. М. Задача о расстановке шахматных королей : материалы / А. М. Караваев // Современные проблемы гуманитарных и естественных наук : материалы II международной научно-практической конференции, г. Москва, 2010. — Т. II. — С. 12-16.

[13] Караваев А. М. Усовершенствованный метод матрицы переноса для подсчета гамильтоновых цепей на прямоугольных решетках и цилиндрах : труды [электронный ресурс] / А. М. Караваев // Сборник трудов международной научной конференции «Параллельные вычислительные технологии '2011» — г. Москва : Московский государственный университет имени М. В. Ломоносова, 2011. - 1 CD-ROM. — С. 695.

[14] Караваев А. М. Подсчет гамильтоновых циклов на семействах торов Cmx Сп. [материалы] / А. М. Караваев, С. Н. Пере-печко // Материалы XVII международной конференции по вы-

числительной механике и современным прикладным программным системам (ВМСППС '2011), 25-31 мая 2011 г., Алушта. — М : Изд-во МАИ-ПРИНТ, 2011. — С. 243-245.

[15] Караваев А. М. О подсчете гамилътоновых циклов в семействах прямоугольных решеток и цилиндров / А. М. Караваев // Материалы международной конференции «Математика, экономика, менеджмент: 100 лет со дня рождения Л. В. Канторовича». - СПб. : ООО «ТАИС», 2012. — С. 47-48.

[16] Гэри М. Вычислительные машины и труднорешаемые задачи / М. Гэри, Д. Джонсон // М. : Мир, 1982.

[17] Thompson G. L. Hamiltonian Tours and Paths in Rectangular Lattice Graphs // Mathematics Magazine, 1977. — Vol. 50. — No. 3. - P. 147-150.

[18] Alon Itai and Christos H. Papadimitriou and Jayme Luiz Szwarcfiter Hamilton Paths in Grid Graphs / A. Itai, С. H. Papadimitriou, J. L. Szwarcfiter. — SIAM J. Comput., 1982. — P. 676-686.

[19] Valiant L. G. The complexity of enumeration and reliability problems / L. G. Valiant // SIAM Journal on Computing, 1979. — Vol. 8. - No. 3. - P. 410-421.

[20] Flum J., The Parameterized Complexity of Counting Problems / J. Flum, M. Grohe // SIAM Journal on Computing. — May 2004. — Vol. 33, No. 4. - P. 892-922.

[21] Cloizeaux J., Polymers in Solution: Their Modelling and Structure. / J. Cloizeaux, G. Jannink. — Oxford : Clarendon Press, 1990. — 928 P.

[22] Madras N. The Self-Avoiding Walk. / N. Madras, G. Slade. -Birkhauser, Boston, 1993.

[23] Schmalz T. G. Compact self-avoiding circuits on two-dimensional lattices / T. G. Schmalz, G. E. Hite, D. J. Klein // Journal of Physics A: Math, and Gen., 1984. — Vol. 17. — P. 445-453.

[24] Hammersley J. M. Percolation processess. II. The connective constant / Proceedings of the Cambridge Philosophical Society, 1957. - Vol. 53. - P. 642-645.

[25] Orland H. An evaluation of the number of Hamiltonian paths /

H. Orland, C. Itzykson, C. de Dominies // Journal de Physique Lettres, 1985. — Vol. 46. - No. 8. — P. L353-L357.

[26] Camacho C.J. Minimum energy compact structures of random sequences of heteropolymers / C. J. Camacho, D. Thirumalai // Physical Review Letters, 1993. - Vol. 71. — No. 15. - P. 2505-2508.

[27] Jensen I. Enumeration of compact self-avoiding walks /

I. Jensen // Computer Physics Communications, 2001. Vol. 142, P. 109-113

[28] Jacobsen J. L. Field theory of compact polymers on the square lattice / J. L. Jacobsen, J. Kondev // Nuclear Physics, 1998. — Vol. B532[FS], - P. 635-688.

[29] Knuth D. E. The Art of Computer Programming. Vol. 4-Fascicle 1: Bitwise tricks & techniques; Binary Decision Diagrams / D. E. Knuth // Addison-Wesley, 2009. 260 P.

[30] The On-Line Encyclopedia of Integer Sequences [Электронный ресурс] / The OEIS Foundation. — Режим доступа: http://oeis.org, свободный. — Яз. англ.

[31] Klein D. J. Asymptotic distributions for self-avoiding walks constrained to strips, cylinders, and tubes / D. J. Klein // Journal of Statistical Physics, 1980. - Vol. 23. — No. 5. — P. 561-586.

[32] Derrida B. Phenomenological renormahsation of the self-avoiding walk in two dimensions / // Journal of Physics A: Math, and Gen., 1981. — Vol. 14. - No. 1. - P. L5-L9.

[33] Stoyan R. Enumeration of Hamiltonian Circuits in Rectangular Grids / R. Stoyan, V. Strehl // Journal of Combinatorial Mathematics and Combinatorial Computing, 1996. — Vol. 21. — P. 109-127.

[34] Kloczkowski A., Transfer matrix method for enumeration and generation of compact self-avoiding walks. I. square lattices / A. Kloczkowski, R. L. Jernigan // Journal of Chemical Physics, 1998. - Vol. 109. - P. 5134-5146.

[35] Faase F. J. On the number of specific spanning subgraphs of the graphs G x Pn / F. J. Faase // Arc Combinatoria, 1998. — Vol. 49 P. 129-154.

[36] Lundow P. H. Compression of transfer matrices / P. H. Lundow // Discrete Mathematics, 2001. — Vol. 231. — P. 321-329.

[37] Jacobsen J. L. Exact enumeration of Hamiltonian circuits, walks and chains in two and three dimensions / J. L. Jacobsen //

Journal of Physics A: Math, and Theor., 2007. - Vol. 40. — P. 1466714678.

[38] Higuchi S. Field theoretic approach to the counting Hamiltonian cycles of graphs / S. Higuchi // Physical Review E, 1998. — Vol. 58. — No. 1. — P. 128-132.

[39] Guttmann A. J. Square Lattice Self-Avoiding Walks and Polygons / A. J. Guttmann, A. R. Conway // Annals of Combinatorics, 2001. — Vol. 5. — Issue. 3. — P. 319-345.

[40] Tosic R. On the number of hamiltonian cycles of P4 x Pn / R. Tosic, O. Bodroza, Y. H. H. Kwong, H. J. Straight // Indian Journal of pure and applied Mathematics, 1990. — V. 21. — No. 5. — P. 403-409.

[41] Kreweras G. Dénombrement des cycles hamiltoniens dans un rectangle quadrillé / G. Kreweras // European Journal of Combinatorics, 1992. - Vol. 13. - No. 6. - P. 473-476.

[42] Kwong Y. H. H. Enumeration of Hamiltonian Cycles in P4 x Pn and P5 x Pn // Arc Combinatoria. - 1992. - Vol.33. - P. 87-96.

[43] Bodroza O. On the Number of Hamiltonian Cycles o/Pm x Pn / O. Bodroza, R. Tosic Review of Research, Faculty of Science, Mathematics Series, 1994. - Vol. 24. - No. 2. - P. 117-136.

[44] Dixon J. D. Exact solution of linear equations using p-adic expansions / Dixon J. D. // Numerische Mathematik, 1982. — Vol. 40. - P. 137-141.

[45] Van Tuyl A. H. Acceleration of convergence of a family of logarithmically convergent sequences / A. H. Van Tuyl //

Mathematics of Computation, 1994. — Vol. 63. - No. 207. — P. 229246.

[46] Gaunt D. S. Asymptotic Analysis of Coeffitients / D. S. Gaunt, A. J. Guttmann // Phase Transitions and Critical Phenomena. — London, NY : Academic Press, 1974. — Vol 3. - P. 181-243.

[47] Wynn P. On a procrustean technique for the numerical transformation of slowly convergent sequences and series / P. Wynn / / Mathematical Proceedings of the Cambridge Philosophical Society, 1956. - Vol. 52. - P. 663-671.

[48] Guttmann A. J. In: Phase Transitions and critical Phenomena. Vol. 13 / Guttmann A. J. // Ed. Domb C., Lebowitz J. L. Eds. London : Academic Press, 1989.

[49] Baker G. A. Essentials of Padi Approximants / G. A. Baker. — London, NY : Academic Press, 1975. — 306 p.

[50] Стенли P. Перечислительная комбинаторика: Пер. с англ / Р. Стенли. — М. : Мир, 1990. — 440 с.

[51] Центр высокопроизводительной обработки данных ЦКП КарНЦ РАН [электронный ресурс]. / © Институт прикладных математических исследований Карельского научного центра РАН, 2009. — Режим доступа: http://cluster.krc.karelia.ru, свободный. — Загл. с экрана. — Яз. русский.

[52] FlowProblem [электронный ресурс] / Copyright с 20082010. — Artem М. Karavaev. — Режим доступа: http://www.flowproblem.ru, свободный. — Яз. англ.