BC/NW 2009; №2 (15):10.4

ПОЛИГОН СТРУКТУРНОЙ ИНФОРМАТИКИ

Кохов В.А., Ткаченко С.В.

(ГОУВПО «Московский энергетический институт (технический университет)», Россия)

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

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

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

Для проведения исследований была разработана программная система «Полигон для исследования вычислительной эффективности», входящий в состав АСНИ «Мастерская граф-моделей» (www.graphmodel.ru). При создании системы была поставлена цель создать среду, в которой решатели задач могли бы быть использованы как для решения практических и теоретических задач, так и для проведения исследований по анализу их вычислительной эффективности. Обычно программы, решающие задачи на графах, реализуются в виде отдельных приложений. Такие программы, либо имеют свой интерфейс пользователя (ИП), либо не имеют его, читая и записывая данные в файлы.

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

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

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

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

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

- подготовка графов, используемых как входные данные;

- выбор и упорядочение входных данных для исследования;

- запуск списка решателей на выбранном наборе входных данных;

- запрос у пользователя параметров запуска решателей;

- измерение времени решения задач;

- запись времени и результатов решения в базу данных (БД);

- анализ и сравнение вычислительной эффективности работы решателей.

Система реализована как приложение для Microsoft Windows, решатели задач – как динамически загружаемые библиотеки (DLL), взаимодействующие с системой по специально разработанному программному интерфейсу. Возможно также подключение модулей-приложений через специальный решатель-«перемычку». Система работает с графами, организованными в специальные базы. Разработка решателей задач сильно упрощается, так как из них вынесены все функции организации диалога с пользователем, работы с файлами или БД, демонстрации и анализа результатов. Перенесение их в основную систему не только упрощает решатели, но и дает возможность совершенствовать эти функции, не теряя совместимости старых решателей с новыми. Помимо основных модулей, решающих задачи на графах, в состав системы входят и служебные, подготавливающие данные для экспериментов. К ним относятся модули импорта графов из файлов различных форматов, модули конструктивного перечисления семейств графов, генерации семейств средних по сложности графов и случайных графов, модули порождения одних семейств графов на основе других. Эти модули реализованы по тем же правилам, что и основные решатели задач. Небольшие базы можно подготовить с помощью визуального редактора, входящего в состав «Полигона».

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

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

В ходе эксперимента решатели запускаются последовательно на всех графах базы, либо на парах графов, составленных заданным способом (например, все возможные пары (все (i, j), где i≠j), все возможные пары из неповторяющихся графов (все (i, j), где i<j), пары из графов с нечетными и четными номерами; всего 15 вариантов). Для запуска составляется набор решателей задач и задаются их параметры. Предварительное задание параметров всех решателей удобно для проведения длительных (многочасовых) экспериментов, для которых присутствие человека за компьютером не требуется вплоть до момента их завершения. Эту информацию (набор решателей + параметры) можно сохранить для последующего запуска на другом наборе входных данных.

Список задач, решатели которых исследуются в «Полигоне», включает: (1) для одного графа на входе: определение численных индексов (включая индексы структурной сложности); построение векторных и матричных моделей, характеризующих сложность графа; нахождение канонического представления графа, нахождение прорисовки (способа размещения вершин на плоскости или в трехмерном пространстве) по заданным правилам; вычисление характеристик симметрии; вычисления количественных значений мер сходства или различия расположения фрагментов в графе; (2) для двух графов на входе: распознавание изоморфизма; изоморфного вложения; максимального изоморфного пересечения (нахождение максимального общего фрагмента, являющегося частичным или порожденным подграфом); вычисление количественных значений мер сходства и различия графов.

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

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

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

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

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

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

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

Полигон используется в учебном процессе и научных исследованиях студентов и аспирантов МЭИ (ТУ) [2,3].

Литература

1. Кохов В.А. Концептуальные и математические модели сложности графов. М.: Издательство МЭИ, 2002. – 160 с.

2. Кохов В.А., Ткаченко С.В. Решатель базовых задач структурной информатики. М.: Издательство МЭИ, 2006. – 192 с.

3. Кохов В.А., Ткаченко С.В. Исследование алгоритмов структурной информатики с помощью ППП «ПОЛИГОН-СТРИН». М.: Издательство МЭИ, 2005. – 68 с.