Синтез экспериментов методами динамического программирования

Синтез синхронизирующей последовательности

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

Построение ГСА осуществляется рекурсивно. Вначале в число его вершин включается вершина $$S_0$$, соответствующая множеству допустимых начальных состояний автомата. Вершину $$S_0$$ поместим на вертикальную прямую, называемую далее линией уровня, и присвоим ей номер 1. Определим далее подмножества $$S_i^{(2)}=\sigma(S_), x_i), i=\overline{S_0, x_i}$$, и все полученные попарно различные подмножества, отличные от $$S_0$$, также включим в число вершин графа. Ясно, что $$|S_i^{(2)}| \le |S_0|$$. Упорядочим множества $$S_i^{(2)}$$ по мощности и будем располагать соответствующие им вершины графа на второй, третьей и т. д. линиях уровня по следующему принципу: на 2-ю линию уровня поместим все те вершины $$|S_i^{(2)}|=|S_0|-1$$, у которых $$S_i^{(2)}$$, на 3-ю линию - все те вершины, у которых $$|S^{(2)}|=|S_0|-2$$ и т. д. Затем вершина $$S_0$$ соединяется с каждой вершиной $$S_{i_0}^{(2)}$$ дугой с символом $$x \in X,$$ если $$S_{i_0}^{(2)}=\sigma (S_0, x)$$. В частности, если существует $$x \in X$$, такой, что $$\sigma (S_0, x)= S_0$$, то у вершины $$S_0$$ проводится петля с символом $$x$$. Пусть $$S_1^{(2)}, \dots , S_a^{(2)}$$ - все попарно различные вершины, появившиеся в графе на втором шаге. Определим теперь подмножества $$S_i^{(3)}=\sigma (S_I^2, x_j)$$ для всех $$x_j \in X$$ и для всех $$S_I^{(2)}, i= \overline {1,a}$$. Все полученные попарно различные подмножества, отличные от появившихся на втором шаге, также включим в число вершин графа. Затем упорядочиваем их по мощности, размещаем их на соответствующих линиях уровня, как это описано выше, и соединяем все вершины $$S_i^{(2)}$$ с вершинами $$S_i^{(3)}$$ соответствующими дугами по ранее определенному правилу. В силу того что $$|S_i^{(3)} \le |S_i^{(2)}|$$, все упомянутые дуги либо связывают между собой вершины, находящиеся на одной и той же линии уровня (в случае, когда $$|S_{i_0}^{(2)}|=|S_{j_0}^{(3)}|$$ ), либо идут от вершин $$S_i^{(2)}$$ к вершинам $$S_i^{(3)}$$, находящимся на линиях уровня с большими номерами (в случае, когда $$|S_{i_0}^{(2)}| > |S_{j_0}^{(3)}|$$ ).

Описанный процесс продолжается далее аналогичным образом до тех пор, пока на очередном шаге построения ГСА будут отсутствовать вершины, отличные от тех, что уже появились в графе на предшествующих шагах. Понятно, что построение ГСА обязательно завершится, поскольку число всевозможных подмножеств множества S состояний автомата конечно, причем число линий уровня ГСА не превосходит величины $$n=|s|$$.

В полученном графе осуществим параллельный перенос всех линий уровня вправо так, чтобы 1-я из них оказалась между вершинами 1-го и 2-го уровней, 2-я - между вершинами 2-го и 3-го уровней и т. д. В результате такого переноса смещенные линии уровня будут пересекаться дугами, соединяющими между собой вершины $$i$$ -го и $$(i+1) $$ -го уровней $$(i=1, 2, \dots ) $$. Все упомянутые точки пересечения будем также считать вершинами графа промежуточными и каким-либо образом их перенумеруем. Именем каждой из появившихся промежуточных вершин будем считать присвоенный ей при упомянутой нумерации номер.

Удалим из этого графа все петли и поставим в соответствие каждой дуге графа число, трактуемое как длина дуги, равное весу помеченного ею входного символа. С каждой парой дуг графа $$(s_1, l_1)(l_1, s_1)$$ (здесь $$l_1$$ - номер некоторой промежуточной вершины), полученной из дуги $$(s_1,s_2)$$ с пометкой $$x_l$$ за счет переноса линий уровня, поступим следующим образом. Дугу $$(s_1, l_1)$$ пометим пустым $$( \varnothing)$$ символом и поставим ей в соответствие число 0, а дуге $$(l_1, s_2)$$ оставим пометку $$x_i$$ дуги $$(s_1, s_2)$$ и поставим ей в соответствие число, равное весу символа $$x_l$$. Полученный в результате граф будем называть ГСА.

Из самого способа построения ГСА вытекает, что заданный автомат будет иметь СП тогда и только тогда, когда в соответствующем ему ГСА имеются вершины, помеченные символами одноэлементных подмножеств множества $$S$$ состояний автомата. При этом последовательность входных символов, соответствующая пути по ГСА из вершины $$S_0$$ в одну из одноэлементных вершин, очевидно, будет являться СП.

Для иллюстрации на рис.2.1 изображен граф синхронизации автомата, заданного табл. 1.1. Граф построен в предположении, что $$S_0=\{1,2,3,4,5\}$$.

Далее покажем, что рассматриваемая нами задача синтеза СП может быть сведена к задаче выбора наискорейшего пути, решаемой методом динамического программирования [15] из теории оптимального управления. Последняя задача решается поэтапно с помощью процесса перемещения с одной опорной прямой на соседнюю. В нашем случае роль таких опорных прямых играют линии уровня, введенные нами при построении ГСА. Напомним, что из содержательного смысла задачи о выборе наискорейшего пути сетка дорог, ведущая из начального в конечный пункт, имеет некоторые особенности. Так, во-первых, в ней не должно быть петель, поскольку движение по ним не приближает нас к конечному пункту, а, во-вторых, все дуги, соответствующие участкам дорог от пунктов, расположенных на $$i$$ -й опорной прямой, должны либо вести к пунктам на $$(i+1 )$$ -й опорной прямой, либо соединять между собой пункты на i-й опорной прямой, но не должно быть "обратных" дуг.

Понятно, что если веса дуг в ГСА интерпретировать как время движения по ним, а сам ГСА как сеть дорог, то задача о синтезе СП минимального веса эквивалентна задаче о выборе наискорейшего пути из вершины $$S_0$$ ГСА в одну из одноэлементных вершин того же графа. Действительно, ГСА удовлетворяет по построению всем требованиям, предъявляемым к сети дорог в упомянутой задаче. В качестве примера рассмотрим применение метода динамического программирования к построению минимальной по весу СП, переводящей автомат, заданный табл. 1.1, в конечное состояние 4, предполагая что $$w(\alpha)=1, w(\beta)=2, w(\gamma)=3$$, а множество допустимых начальных состояний есть $$S_0=\{1,2,3,4,5\}$$.

Вначале введем две дополнительные линии уровня: нулевую, на которой будет располагаться вершина $$S_0$$ ГСА, и $$\mu$$ -ю, на которой будут располагаться вершины ГСА, лежащие правее линии уровня с номером $$\mu-1$$, где $$\mu -1$$ есть максимальный номер уровня, появившийся в процессе построения ГСА, описанном выше. В рассматриваемом примере максимальный номер уровня, появившийся при построении ГСА на рис.2.1, равен 4, поэтому на 5-й линии уровня будут расположены все одноэлементные вершины $$\{1\}, \{2\}, \{3\}, \{4\}, \{5\}$$, а на нулевом - вершина $$\{1,2,3,4,5\}$$.

Напомним, что в методе динамического программирования каждый шаг представляет собой перемещение с одной из опорных прямых (линии уровня) на соседнюю, более близкую к конечному пункту (в нашем примере к вершине $$\{1,2,3,4,5\}$$ ). При этом, как обычно, предполагается, что движение от шага к шагу допускается только в положительном направлении (от вершины $$\{4\}$$ к вершине $$\{1,2,3,4,5\}$$ ). Иными словами, после того как некоторый шаг пройден, возвращение обратно, в ту же полосу между двумя линиями уровня, не допускается.

В соответствии с числом линий уровня на рис.2.1 процесс перемещения из вершины $$\{4\}$$ в вершину $$\{1,2,3,4,5\}$$ разделим на пять шагов и начнем построение оптимального пути с последнего пятого шага.

Наметим на четвертой линии уровня все возможные пункты (вершины) нашего движения в момент окончания предпоследнего четвертого шага. В нашем примере такими вершинами будут вершины $$\{12'\}, \13'\}, \{14'\}, \{15'\}$$. Далее находим оптимальные по времени пути из этих вершин в вершину $$\{4\}$$. Заметим, что для поиска таких путей можно применить, например, известные алгоритмы Флойда и Данцига поиска всех кратчайших путей в ориентированном графе [34].

После завершения этого шага переходим к планированию четвертого шага. Для каждой из вершин $$\{12'\}, \13'\}, \{14'\}, \{15'\}$$ теперь необходимо найти оптимальное управление, т. е. такой путь с 3-й линии уровня на 4-ю, который совместно с уже оптимизированным последним шагом дает возможность достигнуть вершины $$\{4\}$$ за минимальное время.

Чтобы найти это условное оптимальное управление, для каждой вершины на 3-й линии уровня необходимо перебрать всевозможные способы перехода на 4-ю линию уровня и время, которое требуется на этот переход, сложить с минимальным временем последнего шага. Из всех возможных путей выбирается тот, для которого это суммарное время минимально, и соответствующий путь отмечается. Понятно, что и на этом шаге для поиска кратчайших путей между соответствующими вершинами ГСА 3-й и 4-й линий уровня можно применить алгоритмы Флойда и Данцига.

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

Ему соответствует последовательность входных сигналов $$\varnothing \varnothing \varnothing \gamma \alpha \varnothing \gamma $$. Если исключить из нее пустые сигналы, то получится искомая минимальная по весу СП $$\gamma \alpha \gamma $$, переводящая заданный автомат из любого состояния в одно и то же конечное состояние 4.

Выбирая далее в качестве конечной вершины пути все остальные одноэлементные вершины ГСА, находящиеся на 5-й линии уровня, найдем описанным выше образом минимальные по весу СП, переводящие автомат в эти конечные состояния. Заметим, что в общем случае не все такие пути могут существовать, что говорит о невозможности перевода автомата в соответствующее конечное состояние, если он стартует из любого состояния множества $$S_0$$. Наконец, выбрав из всех построенных условно оптимальных по весу СП минимальную, получим искомую СП. Легко убедиться, что в нашем примере такой минимальной по весу СП будет $$\gamma \alpha \gamma $$, построенная выше.

Синтез установочной последовательности

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

ГУА - это ориентированный граф, каждая вершина которого отмечается $$A$$ -группой $$\sigma$$ -множеств. Отметка вершины используется в качестве ее имени. Если $$A$$ -группа, которой отмечена некоторая вершина $$S_1$$ ГУА, под воздействием входного сигнала $$x \in X$$ переходит в $$A$$ -группу, которой отмечена вершина $$S_2$$, то в ГУА из $$S_1$$ в $$S_2$$ проводится дуга, на которой ставится входной сигнал $$x$$. Правила преобразования одной $$A$$ -группы в другую под воздействием входного сигнала $$x$$ остаются такими же, как они определены выше.

Построение ГУА осуществляется рекурсивно и по существу совпадает с процессом построения установочного дерева из [18].

Вначале в число вершин графа включается вершина $$S_0$$, где $$S_0$$ - множество допустимых начальных состояний. Вершину $$S_0$$ поместим на вертикальную прямую и назовем ее линией 1-го уровня. Далее строим все $$A$$ -группы, в которые переходит $$A$$ -группа $$S_0$$ под воздействием всех символов входного алфавита $$X$$, включаем их в число вершин ГУА и помещаем на линию уровня с номером 2. Из вершины $$S_0$$ в вершины второго уровня проводим по упомянутому правилу дуги, помеченные соответствующими входными символами. Процесс построения ГУА продолжается далее аналогичным образом (как и в случае установочного дерева). При этом если на очередном шаге построения появилась вершина, соответствующая однородной $$A$$ -группе, то такая вершина считается листом, т. е. при продолжении процесса построения ГУА из нее не будет больше исходить никаких дуг.

У каждой вершины $$S_i$$ ГУА установим флажок (на рисунке он, как и ранее, изображается в виде квадрата); в него записывается число, равное сумме весов входных символов последовательности, которая ведет из $$S_0$$ в $$S_i$$. Теперь введем некоторые дополнительные правила, используемые при построении ГУА:

Понятно, что описанный процесс построения ГУА всегда завершается за конечное число шагов. Проиллюстрируем построение ГУА для автомата, заданного табл. 1.1, считая, что $$S_0=\{1,2,3,4,5\}, w(\alpha )=1, w(\beta)=2, w(\gamma)=3$$. Обратимся к рис.2.2, на котором изображен соответствующий ГУА. На третьем шаге построения ГУА, как это видно из рисунка, возникло 9 вершин, среди которых вершины $$\{1,2,3,2,3\}, \{1,4,2,2,4\}, \{4,5,4,4,4\}, \{5,5,4,2,4,5\}$$ не являются однородными, а остальные - однородные. Последние именно по этой причине становятся листьями. Заметим, что вершина $$\{1,1,3,3,5\}$$ среди однородных имеет минимальное значение флажка, равное 3. Теперь перейдем к четвертому шагу. Так, самая верхняя вершина 3-го уровня $$\{1,2,3,2,3\}$$ под воздействием сигнала $$\alpha $$ переходит в вершину, помеченную такой же $$A$$ -группой. Поскольку она является непосредственным преемником вершины с такой же $$A$$ -группой, по правилу 1 она удаляется из ГУА. Аналогичная ситуация имеет место для вершины $$\{5,5,4,4,5\}$$ (самая нижняя на 3-м уровне) при построении вершины 4-го уровня, в которую она переходит под воздействием входного символа $$\gamma$$.

Легко убедиться, что при построении остальных вершин 4-го уровня в их флажках будут стоять числа, большие 3, но тогда по правилу 2 они все должны быть удалены из ГУА. Таким образом, граф ГУА содержит только три уровня.

Из самого способа построения ГУА вытекает, что последовательность входных символов, соответствующая пути по ГУА из вершины $$S_0$$ в одну из однородных вершин, будет являться УП для заданного автомата.

Покажем теперь, что задача синтеза минимальной по весу УП всегда может быть сведена к задаче выбора наискорейшего пути, как это было и в случае СП.

Роль опорных прямых здесь выполняют линии уровня, а сам ГУА можно интерпретировать как сеть дорог, удовлетворяющую необходимым требованиям для упомянутой задачи, поскольку в нем, во-первых, отсутствуют петли, а, во-вторых, все дуги направлены от вершин $$i$$ -го уровня к вершинам $$(i+1)$$ -го уровня, т. е. отсутствуют "обратные" дуги.

Понятно, что если положить время движения по дуге равным весу входного символа, которым она помечена, то задача синтеза УП минимального веса сводится к задаче о выборе наискорейшего пути из вершины $$S_0$$ в однородные вершины ГУА. Отсюда вытекает, что для решения рассматриваемой нами задачи можно применить метод динамического программирования.

Вместе с тем заметим, что ГУА представляет собой дерево, а в дереве, как известно, если между некоторой парой его вершин путь существует, то он единственен. Следовательно, применительно к ГУА задача поиска пути из вершины $$S_0$$ в некоторую однородную вершину превращается в тривиальную задачу. Более того, для каждой однородной вершины в ее флажке записано число, равное времени, затрачиваемому на путь в нее из $$S_0$$.

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

Так, в ГУА на рис.2.2 имеется 5 однородных вершин, среди которых минимальное число во флажке, равное 3, имеет вершина $$\{1,1,5,3,3\}$$. Поскольку пути по ГУА из вершины $$S_0$$ в нее соответствует входная последовательность $$\beta , \alpha $$, то она и является минимальной по весу УП.

Синтез диагностической последовательности

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

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

Вершины ГДА, которые отмечены $$A$$ -группами, содержащими кратные (только простые) $$\sigma$$ -множества, будем называть кратными (простыми).

Построение ГДА аналогично построению диагностического дерева автомата, описанному в [18], но при этом вводятся несколько иные, чем в [18], правила, по которым вершина $$S$$ (по терминологии [18] - ветвь) $$k$$ -го уровня становится листом.

Вершина $$S$$ $$k$$ -го уровня ГДА становится листом, если:

Легко показать, что введенные правила обрыва ветвей гарантируют построение ГДА за конечное число шагов.

Проиллюстрируем предложенный способ построения ГДА на примере автомата, таблица переходов-выходов которого отличается от табл. 1.1 только содержимым левой верхней клетки: под воздействием сигнала $$\alpha$$ автомат из состояния 1 переходит опять в состояние 1, но при этом его выходной сигнал равен 1, а не 0, как в табл. 1.1. Предполагается, что множество допустимых начальных состояний есть $$S_0=\{1,2,3,4,5\}$$, а $$w(\alpha)=1, w(\beta)=20, w(\gamma)=30$$.

На рис.2.3 изображен ГДА для этого автомата. Проиллюстрируем теперь, как работают введенные правила завершения. Так, на третьем шаге построения ГДА появляется вершина $$\{4,5,4,5\}$$ со значением флажка, равным 60, в которую ведет дуга, помеченная входным символом $$\gamma$$, из вершины $$\{4,5,4,5\}$$ второго уровня со значением флажка, равным 30. Тогда, в силу пункта 3 правил завершения, вершина $$\{4,5,4,5\}$$ 3-го уровня удаляется. Далее: среди вершин 4-го уровня, появившихся в процессе построения ГДА, имеется простая вершина $$\{1,2,4,2\}$$ со значением флажка, равным 22. Легко убедиться, что на 5-м шаге построения ГДА у всех появляющихся вершин значения флажков будут больше 22, но тогда в силу пункта 4 правил завершения все эти вершины должны быть удалены из ГДА. Таким образом, ГДА для нашего примера будет содержать только четыре уровня. Отметим также, что вершина $$\{1,1,2,2\}$$ второго уровня является оконечной в силу пункта 2 правил завершения, вершины $$\{1,1,2,2\}, \{3,5,3,5\}$$ второго уровня и вершина $$\{1,2,4,2\}$$ третьего уровня становятся оконечными в силу пункта 1 правил завершения.

Из способа построения ГДА вытекает, что последовательность входных символов, соответствующая пути по ГДА из вершины $$S_0$$ в одну из простых вершин, будет являться ДП для заданного автомата.

Отметим, что поиск упомянутых путей представляет собой тривиальную задачу, поскольку ГДА является деревом, и потому каждый такой путь единственен. Понятно, что построение ДП с минимальным весом сводится к следующему. Среди всех простых вершин ГДА отыскивается вершина $$S$$ с минимальным значением флажка. Затем в этом графе находится единственный путь из $$S_0$$ в $$S$$, которому соответствует определенная последовательность входных символов. Построенная таким образом входная последовательность и является искомой ДП, минимальной по весу.

Так, в ГДА на рис.2.3имеется 3 простых вершины, из которых у вершины $$\{1,2,4,2\}$$ четвертого уровня значение флажка минимально и равно 22. Поскольку пути по ГДА из вершины $$S_0$$ в эту вершину соответствует входная последовательность $$\alpha , \alpha, \beta$$, то она и является минимальной по весу ДП. Заметим, кстати, что минимальной ДП в классическом смысле для этого примера будет являться входная последовательность $$\gamma, \beta $$, соответствующая пути по ГДА из вершины $$S_0$$ в вершину $$\{1,2,1,2\}$$ третьего уровня.

Вопросы и упражнения