Software & Systems

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

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

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

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

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

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

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

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

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

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

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

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

·     запись времени и результатов решения в БД;

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

Система реализована как приложение для Microsoft Windows, решатели задач – как динамически загружаемые библиотеки (DLL), взаимодействующие с системой по специально разработанному программному интерфейсу. Возможно также подключение модулей-приложений через специальный решатель-перемычку. Система работает с графовыми моделями, организованными в специальные базы.

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

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

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

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

В ходе эксперимента решатели запускаются последовательно на всех графах базы либо на парах графов, составленных заданным способом (например, все возможные пары (все (i, j), где i≠j), все возможные пары из неповторяющихся графов (все (i, j), где i

Список задач, решатели которых исследуются в Полигоне, включает:

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

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

Среди решателей имеются как авторские разработки, так и известные программные реализации, адаптированные для работы в Полигоне.

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

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

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

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

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

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

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

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

При определении оценок решалась задача поиска всех изоморфных вложений фрагмента-цикла с числом вершин 20 в регулярные графы степени 3 для трех уровней сложности графов (рис. 2а – для графов с низким уровнем сложности, рис. 2б – со средним, рис. 2в – с высоким). Исследования проводились на ЭВМ типа IBM PC (Pentium-4-3400 и 1 Гб оперативной памяти). Время решения задачи измерялось в миллисекундах (на графиках (рис. 2) ось времени – в тысячах миллисекунд).

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

Примечание: Н, СР, В – низкий, средний и высокий уровни сложности графа соответственно.

Экспериментальные исследования показали, что алгоритмы 3 и VF2 существенно эффективнее решают задачу, чем алгоритм VF в классе регулярных графов степени 3.

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

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

Литература

1.   Кохов В.А., Незнанов А.А., Ткаченко С.В. Структурная информатика – новый актуальный раздел информатики для изучения в школе и университете // 1-е Всеросс. совещ. НМС по информатике: Актуальные проблемы информатики в современном российском образовании. М.: МАКС-ПРЕСС, 2004. С. 250–276.

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

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

4.   Cordella L.P., Foggia P., Sansone C., Vento M. An Improved Algorithm for Matching Large Graphs, Proc. of the 3rd IAPR-TC-15 International Workshop on Graph-based Representation, Italy, 2001.

5.   Алгоритмы и программы решения задач на графах и сетях / М.И. Нечепуренко [и др.]. Новосибирск: Наука, 1990.