Файл: Алферова, З. В. Математическое обеспечение экономических расчетов с использованием теории графов.pdf

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

Был рассмотрен синтез составного алгоритма. Рассмотрим об­ ратную задачу — получение алгоритма для отдельного случая из составного алгоритма. Предположим, что дан алгоритм, приведен­ ный на рис. 20, и что нужно получить подходящий алгоритм для случая р = 1. Это может быть сделано просто выделением правиль­

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

В алгоритме, приведенном на рис. 20, единственный правиль­ ный путь, который не содержит р , — это

XiX2ppiXiP3Xi ».

х,

Рис. 20. Составной алгоритм

Правильные циклы, которые не содержат р , — это

PPix2 ;•

рхАрзХг .

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

§ 4. 3. АЛГОРИТМ СИНТЕЗА, ОСНОВАННЫЙ

НА ИСПОЛЬЗОВАНИИ ГРАФОВ

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

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

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

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

Ш

Отчет о реализации в транспортном отделе составляется с раз­

чет составляется в разрезе поставщиков. По каждому поставщику перечисляется соответствующая номенклатура оборудования с указанием количества и стоимости. По каждой группе оборудова­ ния подводится общий итог.

Отчет о реализации в отделе оборудования составляется в раз­ резе предприятий и номенклатуры оборудования. Графы алгорит­ мов этих задач представлены на рис. 21 и 22.

• Множество реализаций алгоритма в отделе оборудования пред­

Множество реализаций алгоритма в транспортном отделе пред­ ставляется логической функцией вида:

юнкции, а знак X — операции конъюнкции.

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

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

Введение этих понятий позволяет свести процесс синтеза ал­ горитмов к процессу поиска равных подпутей на графах, что рав-