Software & Systems

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

Для создания алгоритмов, позволяющих получать решения комбинаторных задач без полного перебора всех возможных вариантов интерес представляет предложенная профессором В.А. Горбатовым теория характеризацион-ного анализа, которая опирается на идею поиска причин, сказывающихся на осуществимости проводимых преобразований. Эти причины проявляются в виде так называемых запрещенных фигур [3]. Поиск оптимального решения сводится к построению минимального покрытия семантической таблицы, в образовании которой участвуют запрещенные фигуры, присутствующие в модели реализуемого преобразования. Данная процедура принципиально содержит перебор, но он на много порядков менее трудоемок, чем процесс генерации всех возможных вариантов при поиске минимального решения [1].

Однако характеризационный подход трудно применим при проведении преобразований, когда число запрещенных фигур, а также их сложность резко возрастают с ростом размерности задачи. Примером таких преобразований являются вложения одних графов в другие, обладающие заданными структурными свойствами. Вложением графа G= < V(G),U(G)> в граф R— называется отображение их носителей f: F(G)-» V(R) такое, что при этом имеет место соответствие сигнатур V. .(д. ,д.)е U{G)=> (Д-Э(), Д-& ))sU(R). К вложению графов сводится, в частности, целый ряд практических задач обработки информации и управления в автоматизированных системах проектирования и производства в приборостроении, таких как проектирование многослойных печатных плат, размещение проводников по слоям, создание быстродействующих управляющих устройств, расчет оптимального (с точки зрения загрузки оборудования) запуска изделий в производство, эффективное распределение ресурсов и т.п. В случае, когда при решении конкретной задачи непосредственное вложение G—*R оказывается невозможным, его необходимо преобразовать к виду, вложимому в граф R. При этом получение оптимального решения требует проведения преобразований минимальным образом.

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

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

Таким образом, решение конкретной задачи вложения G—*R состоит из следующих основных этапов.

-    Построение множества запрещенных фигур вложения G-*R или его описание с помощью процедур, основанных на их гомоморфизме.

-    Выделение на основе1 анализа влияния запре щенных фигур вложения на свойства носителя и сигнатуры графа объективных причин вложе ния на уровне элементов носителя и сигнатуры графа G.

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

-    Реализация приближенного семантического алгоритма вложения графов большой размер ности (число вершин больше 100) оптималь ным (с точки зрения временных затрат) обра зом на основе аппарата дифференцирования графов.

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

Рассмотрим применение предложенного подхода к решению задачи раскраски вершин графа.

При решении задачи раскраски графа на ЭВМ основное значение приобретает критерий соцветности вершин графа. В настоящее время широкое распространение получили предложенные А.П. Ершовым эвристические критерии соцветности, основанные на учете пересечений окрестностей вершин графа. Исследования структуры запрещенных фигур раскраски вершин квазиполных графов позволили сформулировать более точный семантический критерий соцветности вершин, основанный на понятии порожденного цикла графа. Порожденным циклом графа G= < V,U> называют цикл G , V

Структура квазиполных графов позволяет сделать вывод о том, что любой квазиполный граф квазиплотности к>Ъ есть сочетание специального вида семейства порожденных циклов нечетной длины [5].

Для раскраски произвольного графа G строится таблица, каждой строке которой взаимно однозначно соответствует порожденный цикл нечетной длины графа, столбцу - вершина графа, и элемент (/, J) таблицы равен 1 тогда и только тогда, когда j-x вершина входит в 1-й цикл,'и О-в противном случае. Каждую пару вершин й; и -й графа можно охарактеризовать значением Р(О( ,-й) = ш /(о^ + ы ), где w , ы -частоты собственных вхождений вершин -й и 4,-и - частота совместного вхождения этих вершин в таблицу порожденных циклов нечетной длины графа. Приведенное отношение определяет степень связности данных вершин относительно их собственного и совместного вхождений а порожденные циклы нечетной длины графа. Чем меньше эта связность, тем больше вероятность соцветности вершин -Й и -ft . На основании этого при раскраске графа в качестве соцветных вершин будем выбирать те пары несмежных вершин -Q\ и -в графа, которым соответствует минимальное значение отношения. В качестве претендентов на соцвет-ность рассматриваются пары вершин ■& и ■& , расстояние между которыми равно двум. При этом, когда выражение /*(д ,д ) принимает минимальное значение на нескольких парах вершин, в качестве соцветных выбирается та пара, порожденные циклы нечетной длины которой в наибольшей степени пересекаются по ребрам графа

Вычисляем значение P(-Q.,-&) на парах не-;межных вершин графа, расстояние между ко-горым равно двум.

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

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

Реализация разработанных методов и алгоритмов на IBM PC/AT дала возможность представить процесс вычислений в виде двухкон-турной структуры. Структура программного обеспечения, включающая в себя при выполнении каждого вида вложения два взаимодействующих семантических контура (один для целенаправленного порождения вариантов, другой для оценки порожденных вариантов), позволяет проводить эффективное усечение вариантов решений и обеспечивает высокое быстродействие проводимых преобразований на ЭВМ.

Использование разработанных программных средств при решении прикладных комбинаторных задач позволило повысить в среднем в

2 раза как размерность решаемых задач, так и точность решения, получаемого за заданное время счета на ЭВМ.

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

Список литературы

1.      Горбатов В.А. Основы дискретной математики. - М.: Высшая школа, 1986. - 312 с.

2.      Горбатов В.А., Смирнов М.И., Хлытчиев И.С. Логичес кое управление распределенными системами. - М.: Энер- гоатомиздат, 1991. - 336 с.

3.      Горбатов В.А. Теория частично упорядоченных систем. - М.: Советское радио, 1976. - 336 с.

4.      Жуков В.В., Смирнов М.И. Программные средства ав томатизации приборостроительного производства изде лий радиоэлектронной аппаратуры. // Программные про дукты и системы. - 1990. - №2. - С. 79-84.

5.      Smirnov M.I. Software Invariables Para La Solution De Problemas Combinados De Sapr Y Sistemas Flexibles. Sequndo Congreso International De Informatica "Informa- tiea' 90", Resumenes Tomo II, La Habana, 1990, p. 348-349.