Содержание к диссертации
Введение
ГЛАВА 1. Состояние проблеммы и обзор методов автоматизированного проектирования 8
1.1.Моделирование систем управления 8
1.2. Методы автоматизированного проектирования систем логического управления 13
ГЛАВА 2 Нахождение размещения по стандартной составляющей 18
2.1. Нахождение изоморфного вложения графоида заданного автомата в декартово произведение графоидов заданного и стандартного автоматов 18
2.2. Расширение носителя графоида заданного автомата 27
2.3. Формирование подмножеств соцветных вершин на основе функционально несвязных пар состояний автомата 33
ГЛАВА 3. Построение графа условий соцветности вершин графоида заданного автомата и нахождение размещения его состояний по компонентам разложения 48
3.1. Нахождение системы ограничений на размещение состояний автомата 48
3.2. Нахождение нестандартной компоненты разложения 63
ГЛАВА 4. Разработка системы автоматизированного проектирования абстрактного этапа реализации устройств управления на стандартных составляющих и её имитационное моделирование 77
4.1. Состав и функционирование системы проектирования 77
4.2. Имитационная модель системы проектирования 80
4.3. Примеры решения задач проектирования с использованием разработанной САПР 109
Заключение 124
Литература
- Методы автоматизированного проектирования систем логического управления
- Расширение носителя графоида заданного автомата
- Нахождение нестандартной компоненты разложения
- Имитационная модель системы проектирования
Введение к работе
Большой класс технических систем с сосредоточенными параметрами образуют логико-вычислительные системы - системы, функционирование которых описывается средствами логического управления и могут представляться функциями на графах.
Создание САПР систем логического управления (СЛУ) сопряжено с необходимостью решения большого класса оптимизационных задач, часто комбинаторной сложности, что порождает проблему уменьшения их размерности декомпозицией. При решении этой и других проблем разработки САПР СЛУ наиболее эффективной моделью последних является их конечно-автоматное представление. Проблемы разработки и оптимизации автоматных моделей систем управления, в том числе декомпозиционной теории их синтеза широко освящены в работах как отечественных, так и зарубежных ученных.
Настоящая работа посвящена разработке методов и алгоритмов проектирования СЛУ в виде параллельно функционирующих стандартных блоков (компонентных автоматов). Параллельная работа компонентных автоматов обеспечивает высокое быстродействие системы. Стандартность компонент и их интегральное исполнение способствует повышению надёжности. Блочное представление проектируемой системы позволяет уменьшить размерность оптимизационных задач, решаемых при их проектировании. Автономность блоков позволяет уменьшать функциональную связность автоматов, что наряду с отсутствием межблочных связей, также способствует повышению надёжности. Обеспечение этих свойств для систем реальной сложности приводит к необходимости решения уже на абстрактном этапе синтеза ряда задач, решение которых возможно только в рамках САПР, что предопределяет актуальность выполненных исследований.
Целью работы является разработка методов и алгоритмов, позволяющих представить функционирование системы логического управления, заданное графоидом, в виде мультипликативной композиции графоидов стан-
дартных компонент. Поставленная цель достигается решением следующих задач:
разработка метода нахождения размещения состояний заданного автомата по стандартной компоненте разложения.
разработка метода построения нестандартной компоненты разложения, обеспечивающей эквивалентность её совместного параллельного функционирования с найденными стандартными компонентами функционированию заданного автомата.
разработка алгоритмов реализации предложенных методов.
анализ целесообразности использования известного метода, основанного на раскраске графа функциональной связности состояний - графа сцепления, для построения нестандартной компоненты разложения.
разработка системы автоматизированного проектирования абстрактного этапа реализации устройств управления на стандартных составляющих
Методы исследования. В работе использовались методы теории множеств, алгебры разбиений, теории графов, теории автоматов. Научная новизна:
разработан метод размещения состояний заданного автомата по стандартной компоненте разложения, использующий изоморфное вложение его графоида в декартово произведение графоидов заданного и стандартного автоматов.
сформулирована и доказана теорема существования размещения состояний заданного автомата по стандартной компоненте разложения.
предложен способ использования декартова произведения графоидов заданного и стандартного автоматов для нахождения эквивалентного расширения носителя графоида заданного автомата, позволяющего построить размещение по стандартной компоненте разложения.
формализован процесс формирования системы ограничений на размещение состояний автомата. В основу формализации положен граф условий соцветности вершин, полученный путём преобразования квадрата графои-да заданного автомата.
предложен новый подход к решению задачи сужения сигнатуры графа сцепления, основанный на использовании графа условий соцветности вершин.
разработан метод построения нестандартной компоненты разложения последовательным формированием подмножеств состояний, для которых возможно одинаковое размещение по искомой компоненте. При этом на каждом шаге отсеиваются бесперспективные варианты.
Обоснованность и достоверность научных положений, выводов и рекомендаций подтверждается соответствием результатов работы внедренной САПР результатам проведенного имитационного моделирования.
Практическая значимость. Предложен эффективный инструментарий абстрактной декомпозиции СЛУ для её реализации на стандартных компонентах в виде совокупности алгоритмов и программных модулей.
Результаты работы внедрены: на НПК «Югцветметавтоматика» при разработке АСУ процессом обжига электродного производства на ОАО «Новочеркасский электродный завод», что позволило получить экономический эффект в размере 570000 руб. в год. Основные научные и практические результаты используются в учебном процессе СКГМИ(ГТУ) при чтении лекций и проведении практических занятий по дисциплинам «Дискретная математика» и «Теоретические основы построения САПР».
Апробация работы. Основные результаты проведённых в диссертации исследований докладывались на межкафедральном научном семинаре «Декомпозиционная теория синтеза систем логического управления», на ежегодных научно-технических конференциях СКГМИ (ГТУ) (2004-2007 гг.), Международной научно-практической конференции «Системный анализ в проектировании и управлении» (Санкт-Петербургский государственный политех-
нический университет), V-й Международной конференции «Устойчивое развитие горных территорий: проблемы и перспективы интеграции науки и образования», г. Владикавказ.
Связь с государственными программами. Основные исследования выполнялись в рамках аналитической ведомственной целевой программы «Развитие научного потенциала высшей школы» (2006 - 2008 г.)
Публикации. Основное содержание диссертационной работы опубликовано в 5-ти печатных работах.
Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, списка использованной литературы из 87 наименований и 2 приложений. Общий объем диссертации 132 страницы, включая 49 рисунков и 4 таблицы.
Методы автоматизированного проектирования систем логического управления
Целью абстрактной декомпозиции является уменьшение размерности оптимизационных задач, решаемых на последующих этапах синтеза и ослабление функциональной связности состояний, что способствует повышению надёжности проектируемых СЛУ.
Первые работы, посвященные абстрактной декомпозиции автоматов, были опубликованы в начале 60-х годов Дж. Хартманисом [48-50]. В них автор предложил специальный вид разбиений на множестве состояний автомата - разбиений со свойством подстановки (СП-разбиений) и указал возможность их применения для декомпозиции автоматов. Эти идеи получили дальнейшее развитие в работах Дж. Хартманиса и Р. Стирнса и воплощены в созданной ими абстрактной математической системе - алгебре пар. Если в рамках алгебры пар не удаётся получить желаемую реализацию то предлагается использовать вместо СП-разбиений системы множеств, являющиеся расширением СП-разбиений допущением в них блоков с непустым пересечением. Такое обобщение позволяет находить разложение автомата за чсёт введения избыточных состояний. Алгебра пар получила развитие в трудах японских ученных Набуеки, Тадаши, Нориоши [57], предложивших её расширение до алгебры троек, четвёрок, ... п-ок. На использовании свойств разбиений основан и ряд методов решения частных задач декомпозиции. Так, Ноли предлагает [58, 59] использовать униформные СП-разбиения, которые содержат во всех блоках равное число состояний. Их нахождение связано с анализом всех автономных автоматов по буквам входного алфавита. Необходимость содержательного анализа существенно ограничивает практическую применимость метода. Кохави бал предложен [60, 61] метод преобразования заданного автомата к виду, когда на множестве его состояний найдётся хотя бы одно СП разбиение, что позволит разделить его на два подавтомата. Изучив свойства одного подкласса класса автоматов с СП-разбиением, О.П. Кузнецов ввёл понятие СП-связки [62], и показал возможность с его помощью строить декомпозицию с разделением входов.
Большой цикл исследований по проблемам, связанным с декомпозицией автоматов, был выполнен во второй половине 60-х годов в Таганрогском радиотехническом институте под руководством А.Н. Мелихова. В основу разработанных методов и алгоритмов положено нахождение подстановок множества состояний автомата, приводящих матрицу смежности соответствующего графа к специальному виду - к правильной клеточной матрице (ПКМ). Однако в реальном проектировании эти синтаксические процедуры не давали решения задачи декомпозиции, так как для практических систем не существует, как правило, бесповторной реализации и хотя бы две компоненты описываются автоматными операторами, имеющими общий аргумент. Кроме того, нахождение подстановок, приводящих матрицу к ПКМ, требует перебора пар разбиений, что так же ограничивает возможности их практического применения.
Принципиально иной подход к решению задачи декомпозиции был предложен в начале 70-х годов [15,16, 63-68]. Он состоит в выявлении и учёте структур автоматного графоида, называемых запрещёнными фигурами, ограничивающих его разложимость. Для решения задачи предложен аппарат раскраски вершин графа спектром красок (многокомпонентной раскраски). Было замечено, что при произвольном размещении заданного автомата в компонентах его разложения, в последних могут возникнуть недетерминированные переходы, т.е. нарушения автоматности. Это случается, если два состояния, для которых определён переход по одному и тому же входному вектору размещены в некоторой компоненте одинаково, а состояния в которые осуществляется переход - различно.
Для исключения возможных нарушений автоматности в компонентах разложения и формализации процесса нахождения параллельной декомпози ции абстрактных автоматов был предложен вспомогательный неориентированный граф, называемый графом сцепления, на множестве вершин которого определена операция раскраски спектром красок. Носитель графа сцепления совпадает с носителем графоида заданного автомата, а сигнатура определяется отношением смежности и пара вершин принадлежит отношению, т.е. смежны, если они являются началами одинаково взвешенных дуг, исключение составляют три случая: 1. обе дуги имеют общий конец, 2. обе дуги являются петлями, 3. обе дуги образованы одними и теми же вершинами.
В каждом из этих случаев совместное размещение описанных вершин не приведёт к возникновению недетерминированностей в компонентном автомате, независимо от размещения остальных вершин графоида.
Операция многокомпонентной раскраски графа сцепления состоит в присвоении каждой вершине спектра красок так, чтобы ни один спектр не повторился и никакие две смежные вершины не были соцветны ни в одной из соответствующих разрядов.
Найденная раскраска переносится на графоид заданного автомата, и, ассоциируя каждую краску в некотором разряде спектра с состоянием соответствующего компонентного автомата, строятся компоненты разложения.
Формирование спектров красок вершин может осуществляться параллельно или последовательно. При параллельном формировании спектров сначала строятся все спектры, которые возможны для заданных мощностей множеств красок по компонентам спектра, затем они распределяются по вершинам графа зацепления с соблюдением правил раскраски. Очевидная комбинаторность такого способа формирования спектра ограничивает его применимость автоматами небольшой мощности множества состояний. Последовательное формирование спектра красок сводится к многократному повторению раскраски графа заданным числом красок.
Расширение носителя графоида заданного автомата
Если искомое разбиение ж на множестве вершин графоида А не существует, то с помощью декартова произведения G=AxB, можно определить, существует ли такое расширение носителя А, которое позволит построить подстановочное разбиение, соответствующее заданной компоненте. Для этого требуется найти, если он существует, такой подграф G" графа G, что: (VZ/„6Z"fc „ ), (15) [VXk є ХЖш \ziaXk = zjp\zia є Z" - zJfi є Г), (16) (vz/aez )(x; 0 xz; 0), (и) где Z" - множество вершин G". Пусть С существует. Тогда, исходя из (5) и (15) получим: (s,Xk = 8j - (Vz,e єZ%aXk = zJ&(SjXk = 0- (Vz„ єZ"\ziaXk = 0)). (18)
Из (18) следует, что для любого і Z; flZ"- есть класс эквивалентных состояний G". Заменяя множество вершин Z, Г) Z" одной вершиной, обозначенной s,., в силу (15) и (16) получим графоид Л. Следовательно G" шА эквивалентны и подмножество вершин графоида G", принадлежащих Z,. П Z соот ветствует вершине st графоидаЛ. Обозначив вершины этого подмножества через st ,s] ,... получимграфоид А эквивалентный А.
Т.к. С является подграфом декартова произведения G = А х В, то очевидно, что на множестве его вершин, а, следовательно, и вершин А , существует СП-разбиение соответствующее В, которое строится в соответствии с ( ! » )- ( ! є5в). (19)
Для нахождения подграфа С воспользуемся следующими соображениями. Если одна из вершин zla (zla eZ,) графа G, принадлежит подграфу G", то, в силу (16) подграфу G" принадлежат все вершины, принадлежащие путям, для которых zla является началом и никакие другие вершины не принадлежат G". Если хотя бы для одной из указанных вершин не выполняется (15) или (17), то zla Z". Таким образом, достаточно перебрать к )V\ = \S,\ вариантов, чтобы найти G" или убедиться, что G" не существует.
Отметим, что хотя условие (17) и является необходимым для всех вершин G" (в случае его не выполнения вершина окажется не достижимой), его требуется проверять только для вершины zla, взятой за основу построений, т.к. она выбирается произвольно. Остальные вершины выбираются на основе (16), они принадлежат окрестности единичного радиуса уже выбранных вершин, и для них автоматически выполняется условие (17).
Очевидно, что расширение носителя графой да А, может привести к увеличению максимального числа состояний в одном блоке разбиения ж, а следовательно к увеличению числа состояний во второй (искомой) компоненте разложения. Поэтому при нахождении G" следует параллельно производить размещение состояний А в блоках разбиения ж и прекращать процесс при превышении максимальным числом состояний в одном блоке заданного ограничения q,.
На основе вышеизложенного предлагается алгоритм нахождения эквивалентного расширения носителя графоида автомата А и построения разбиения ЇЇ: 1. к:=1 2. Из подмножества Zl выбираем вершину zlK (тем самым, поставив её во взаимнооднозначное соответствие начальному состоянию А - Sj). 3. Если для zlK выполняются условия (15) и (17), то переходим к следующему пункту, в противном случае к п. 10. 4. В соответствии с (19) размещаем состояние s, ВЇ-М блоке строящегося разбиения. 5. Выбираем все не выбранные ранее вершины окрестности единичного радиуса zlK. 6. Если для выбранных вершин выполняется (15), то переходим к следующему пункту, в противном случае к п. 10. 7. Для каждой выбранной вершины zja размещаем соответствующее состояние s] (/ равняется числу выбранных на данном этапе вершин подмножества Z, уменьшенному на единицу) в блоке Sa и проверяем условие Sa q,. Если условие выполняется, то переходим к следующему пункту, в противном случае к п. 10. 8. Выбираем все, не выбранные ранее, вершины окрестности единичного радиуса вершин, выбранных на предыдущем этапе. 9. Если в пункте 8 не было выбрано ни одной вершины, то переходим к п. 11, в противном случае к п. 6. 10. Если к q, то к:=к + 1 и переходим к п. 2, в противном случае делаем вывод, что искомое расширение носителя не существует, и переходим к П.11. 11. Конец.
Нахождение нестандартной компоненты разложения
В нашем случае, когда раскраска по первой компоненте задана, число подмножеств, которые могут быть блоками искомого разбиения, сокращается за счёт исключения подмножеств, в которых содержится два и более состояния соцветных в первой компоненте, т.к. для однозначной идентификации состояний автомата, состояния, соцветные в первой компоненте, не могут быть со-цветны во второй компоненте, если число компонент равно двум.
Кроме того, невозможность соцветнои раскраски пар вершин, соцветных в первой компоненте, исключает возможность соцветнои раскраски пар вершин, соответствующих вершинам графа D , из которых существуют пути в вершины, соответствующие парам, соцветным в первой компоненте. И, если таковые найдутся, это ещё больше сократит число подмножеств, которые могут быть блоками СП-разбиения.
В случае, если число компонент больше двух, и описываемый метод применяется для определения размещения по последней компоненте разложения, вершины графа D , соответствующие парам состояний, размещённым со вместно во всех компонентах разложения, взвешиваются нулями. В результате их совместное размещение в последней компоненте разложения исключается.
Формирование множества Q можно условно разделить на три взаимосвязанных процесса: формирование подмножеств множества S мощности от 1 до г q; определение ограничений (классов соцветности), порождаемых со-цветностью вершин сформированных подмножеств; формирование множества Q Для оптимизации процесса формирования подмножеств множества S воспользуемся следующими соображениями.
Одноэлементные подмножества множества состояний автомата могут быть блоками СП-разбиения без каких-либо условий.
Подмножества мощности два требуется рассматривать только те, которым соответствуют вершины графа D , не взвешенные нулями. После того как для этих пар будут определены порождаемые их соцветностью классы соцветности, те из них, соцветная раскраска которых окажется невозможна, удаляются из формируемого списка подмножеств.
Классы соцветности, порождаемые каждой парой, обязательно включают класс соцветности, содержащий эту пару. Если мощность этого класса соцветности больше 2-х, то множество подмножеств этого класса соцветности, содержащих эту пару, есть множество подмножеств, соцветная раскраска элементов которых порождает те же классы соцветности, что и соцветность рассматриваемой пары. То есть определение ограничений для описанных подмножеств не требуется. Однако эти подмножества могут участвовать в формировании подмножеств большей мощности, поэтому они заносятся в формируемый список с соответствующей пометкой.
Для подмножеств мощности три S3a = {s Sj b}, необходимым условием возможности соцветной раскраски их элементов, является возможность соцвет-ной раскраски каждой из трёх пар вершин: { ,Jy-}, {srsk} и {s,, }. Т.е. тройки, для которых в формируемом списке не найдётся соответствующих трёх пар, следует исключить из рассмотрения, как заведомо бесперспективные. После того, как для остальных троек будут найдены порождаемые их соцветностью классы соцветности, список подмножеств корректируется аналогично описанному выше.
Таким образом, формирование списка подмножеств множества S, используемого для определения возможности совместного размещения всевозможных сочетаний состояний автомата, предлагается проводить поэтапно, используя на каждом этапе результаты, полученные на предыдущих этапах и корректируя список в соответствии с результатами анализа возможности соцвет-ной раскраски элементов сформированных подмножеств. На каждом г-ном этапе рассматриваются только те подмножества мощности г [S ), возможность со-цветной раскраски элементов которых не была определена ранее, и для которых в формируемом списке найдётся г подмножеств мощности г -1 [Sj ), таких, что Sj є S-.
Для оптимизации процесса поиска подмножеств Sj є S., может быть использован тот факт, что при упорядоченности списка подмножеств и элементов подмножеств в порядке возрастания индексов первый элемент (г-7)-го из г искомых подмножеств Srj совпадает с первым элементом подмножества S , и одного - со вторым. Кроме того, искомые подмножества отличаются друг от друга только одним элементом. То есть границы поиска могут быть ограничены.
После каждого этапа, как уже было сказано, выполняется определение с помощью предложенного в 3.1. алгоритма, классов соцветности порождаемых соцветностью элементов подмножеств. При определении классов соцветности порождаемых соцветностью пар состояний следует начинать с пар, соответствующих вершинам графа D , не являющимся началами дуг, далее рассматривать вершины, отображающиеся в уже рассмотренные, и так далее.
Имитационная модель системы проектирования
Для оценки эффективности разработанной подсистемы, анализа её характеристик, правильного сопряжения отдельных блоков друг с другом была разработана имитационная модель представленная на рис. 4.2.
Работа модели начинается с генерации случайного графа (графоида автомата А). Из стандартного набора компонент выбирается графоид автомата В. Компоненты стандартного набора могут, либо автоматически перебираться по порядку, либо выбираться проектировщиком, на его усмотрение. Далее в соответствующем модуле выполняется размещение состояний А по В. Если размещение найдено, то результат сохраняется в предназначенном для этого массиве. После перебора всех компонент стандартного набора или же по запросу проектировщика осуществляется анализ результатов размещения по стандартным компонентам. Анализ включает определение максимального числа состояний, совместно размещённых во всех рассматриваемых компонентах, и нахождение множества пар состояний, совместно размещённых во всех рассматриваемых компонентах.
Выбор стандартных компонент, для которых будут определяться эти характеристики, из числа компонент, по которым найдено размещение, осуществляется или проектировщиком, или задаётся число t стандартных компонент, и автоматически перебираются все возможные сочетания по t компонент.
Далее строится G и выполняется его минимальная раскраска. Если хроматическое число hyG J не превышает, заданного проектировщиком, ограничения q на число состояний в нестандартной компоненте разложения, то в соответствии с полученной раскраской Gclf строится искомая компонента разложения. В противном случае в зависимости от величины превышения hip ) на q проектировщик выбирает направление дальнейшей работы модели: модуль «Сужение сигнатуры G » или модуль «Формирование множества Q». В процессе работы каждого их этих модулей вызывается модуль «Нахождение системы ограничений на размещение состояний автомата» поэтому и в том и в другом случае предварительно выполняется «Построение графа условий со-цветности вершин».
После «Сужения сигнатуры G » выполняется «Минимальная раскраска G ». После «Построения множества Q» выполняется «Построение вспомогательного графа G» и «Нахождение максимально полного подграфа G минимальной мощности».
Полученная раскраска G или найденный подграф графа G задаёт размещение состояний А по нестандартной компоненте, в соответствии с которым она и строится в модуле «Построение нестандартной компоненты».
Если число красок G или мощность подграфа графа G превышает ограничение q, то выбирается следующее сочетание стандартных компонент.
В результате имитационного моделирования обнаружилась предпочтительность метода, основанного на формировании и анализе множества Q для нахождения размещения состояний автомата по нестандартной компоненте. Так как в трёх случаях из пяти, когда искомое решение существовало, посредством построения Gclf и сужения его сигнатуры оно не было найдено, и возникала необходимость прибегнуть к формированию множества Q. Поэтому из модели были исключены соответствующие модули. Полученная после внесения изменений модель представлена на рис.4.3.
В процессе работы модели на вход модуля с генератора случайных графов поступает таблица переходов графоида А = ( ,,5, eS,F), из стандартного набора автоматов поступает графоид очередного автомата B = (X,V,P). Таблицы переходов представлены двумерными целочисленными массивами А(пь т), В(п2, т), где п, = Щ, п2 = F, т = \Х\. /-я строка массива А взаимнооднозначно соответствует і-му состоянию автомата Л. Элемент A(i,j) равен номеру строки, соответствующей состоянию, в которое переходит автомат из /-го состояния поу-му входному вектору. а-я строка массива В взаимнооднозначно соответствует а-ыу состоянию автомата В. Элемент B(ccj) равен номеру строки, соответствующей состоянию, в которое переходит автомат из а-то состояния по/-му входному вектору.
Результатом нахождения декартова произведения автомата А на автомат В является таблица переходов автомата G = AxB, G = (X,V,vn eV,U) - двумерный целочисленный массив Gfa, m), щ=щ- щ. В массив G добавляется дополнительный т+1 -й столбец, который используется для пометки выбора вершин графоида в процессе нахождения подграфа G . Элемент G(i,m + 1) равен 1, если соответствующая вершина выбрана, и 0 в противном случае.
Каждому состоянию автомата взаимнооднозначно соответствует пара состояний - первое принадлежит автомату А, второе - автомату В (zia - Si, vj. По номеру строки е массива G определяются номера / и а соответствующих ей строк массивов А и В: i = INT((e-l)/n,) + l а = е-(і- 1) П,.
В соответствии с изложенным в п. 2.1, для построения размещения по стандартной компоненте достаточно перебрать = вариантов, то есть « варианта, соответствующих первым щ строкам массива G. С этой целью в алгоритме организован цикл по переменной к=1...П2.
Для каждого к - го варианта создается целочисленный динамический массив С, который используется для записи номеров выбранных строк массива G (выбранных вершин графоида G). В работе с массивом используются две переменные: г - номер последнего элемента массива, Г] - номер рассматриваемого элемента массива.
Для каждого выбранного состояния требуется проверить условие (15) и, если оно выполняется, то выбрать все невыбранные вершины окрестности единичного радиуса рассматриваемой вершины.
Проверка условия (15) и выбор описанных вершин осуществляется в цикле по переменной /= 1...т. Последовательно перебираются элементы е-той строки массива G (е = С(г])), и / - той строки массива Л (/ = ШТ((е-1)/ п/)+/). Если A(i,j) 0 (переход из / - того состояния автомата Anof- тому входному вектору определен), и G(e,f)&0, то проверяемое условие на этом этапе не нарушается.
В этом случае осуществляется выбор состояния, в которое переходит автомат G из е-того состояния по /-тому входному вектору (G(G(e,j), m + 1) = 1), если оно не выбрано (G(G(e,j),m+ 1) = 0), в массив С добавляется соответствующий элемент (r = r + l,C(r) = G(e,f)) и рассматривается следующее значение/ Если A(i,j) = 0, то G(e,f) = 0 по определению декартова произведения. В этом случае сразу осуществляется переход к рассмотрению следующего значения/ Если A(i,j) 0 И G(e,j) = 0, то нарушается условие (15). В этом случае все полученные на к-том этапе результаты (последняя строка массива RES) удаляются, массив С удаляется, и рассматривается следующее значение к (следующая вершина подмножества Si).
