Консалтология Общая теория консалтинга (стр. 47 )

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

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

Основное правило отсева бесперспективных вариан­тов — монотонная рекурсивность, идейно родственная критерию оптимальности динамического программирования.

Пусть имеются множество W={w} вариантов рекомендаций и множество опытов П={πα}. Каждый вариант wW опи­сывается некоторым множеством признаков. Задача состоит в определении подмножества W* W, инвариантно­го относительно любого πα и содержащего оптимальную рекомендацию w0W*. Для определения подмножества W* не­обходимо поставить опыты по анализу и оценке свойств элементов wW. Исходы опытов позволяют отбросить не­перспективные варианты w, которые не имеют общих ча­стей с элементами подмножества W*, и сделать заключе­ние о целесообразности постановки последующих опытов с целью определения элементов, входящих в подмножест­во W*.

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

через Р(Х). В этом множестве выделено некоторое под­множество допустимых последовательностей W(X) P(X), в свою очередь во множестве W(X) выделено подмноже­ство W0(X) W(X) полных допустимых последовательно­стей. Пусть задана последовательность р. Последователь­ность

называют l-м начальным отрезком последовательности р, а последовательность

называют q-м конечным отрезком. Если q=l+1, то соот­ветствующие части последовательности р называют сопря­женными. Рассмотрим две допустимые последовательности р1 и р2. В p1 выделены l1-й начальный отрезок p и (l1 + 1)-й конечный отрезок p, в р2 выделены l2-й на­чальный отрезок р и (l2+1)-й конечный отрезок р. Если функционал Ф, определенный на множестве W(X), обладает тем свойством, что из

следует Ф(р1)<Ф(р2), то его называют монотонно-рекур­сивным.

Вариант w0 W*, характеризующийся максимальным значением функционала Ф, определяется согласно обоб­щенному принципу оптимальности: если заданы монотон­но-рекурсивный функционал Ф и две допустимые последо­вательности p1 и р2, причем

то последовательности, у которых начальным является от­резок р1 будут неперспективными и не входят в подмно­жество W*. Здесь Р(рi) — множество конечных отрезков, сопряженных с последовательностью рi.

Таким образом, схема последовательного выбора опти­мального варианта сводится к следующим повторяющимся процедурам:

1. Множество вариантов рекомендаций W разбивают на не­сколько подмножеств, каждое из которых обладает специ­фическими свойствами.

2. На основании обобщенного принципа оптимальности отсеивают те варианты wW, значение функционала Ф для которых заведомо не может быть максимальным.

3. Последовательно формируются и анализируются не отсеянные ранее варианты рекомендаций.

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

Далее операции п. 2, 3 и 4 циклически повторяются. Ес­ли на каком-то этапе процесса формирования рекомендаций не останется ни одной последовательности, требующей своего развития до получения полной последовательности, то процесс завер­шен и в качестве рекомендации берется одна из рассмотренных полных допустимых последовательностей с наибольшим значением функционала Ф(р).

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

Последовательные алгоритмы структурного синтеза. Последовательные алгоритмы синтеза относятся к классу

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

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

При иерархической организации конструкции ЭВА под компоновкой понимают определение состава типовых кон­струкций каждого уровня. Задача компоновки обычно ре­шается «снизу — вверх», т. е. известные схемы i—1-го уров­ня необходимо распределить по конструкциям i-гo уровня. Так, например, на самом низшем уровне элементами могут выступать корпуса элементов, а конструкциями (блока­ми)— типовые элементы замены, связанные друг с дру­гом путем разъемных соединений.

В качестве критериев оптимальности при решении за­дач компоновки наиболее часто используют критерии либо минимума суммарного числа Ni типов модулей

где хij — число модулей j-го типа i-го уровня схемы, либо минимума межблочных соединений

где Rik — число внешних связей каждого модуля i-гo уровня.

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

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

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

Сформулируем описанный алгоритм в терминах теории графов. Пусть задан граф схемы G=(X, U), который не­обходимо разбить на l частей G1, G2,..., Gl с числом вершин в каждом соответственно

Первоначально в графе G определяют вершину хi Х с наибольшей локальной степенью ρ(хi) [напомним, что локальной степенью ρ(хi) вершины хi Х называют число ребер, инцидентных этой вершине графа]. Если таких вер­шин несколько, то предпочтение отдается той, которая име­ет большее число кратных ребер. Вершина хi и все смеж­ные с ней вершины включаются в граф G1. Обозначим это множество вершин через Г хi. Если |Г хi |= n1 то G1 обра­зован, если же |Г хi |> n1, то из графа G1 удаляют верши­ны, связанные с остающимися вершинами графа G мень­шим числом ребер. Когда |Г хi |<n, то выбирают вершину xj Г хi |, удовлетворяющую условию