|
105 со всегда тождественно ложное условие, символизирующее возвращение в исходное состояние (т.е. прекращение работы). л 2. Перечисление реализаций алгоритма. Алгоритм является вероятностным, если в его графе имеется хотя бы одно разветвление (т.е. из одной вершины выходит более одной дуги в другие вершины). Вершину, служащую началом разветвления, принято рассматривать как логический оператор, который принимает значения, имеющие смысл частоты исходящих дуг. Однако непосредственно из графа алгоритма, построенного в предыдущей операции, не следует никакой информации о частоте исходящих дуг. Такую информацию можно получить, основываясь на том очевидном обстоятельстве, что частота есть функция исходов опыта. Но исходы опыта можно перечислить априори как возможные реализации общего алгоритма, полученные по комбинациям логических действий. Процедура перечисления реализаций алгоритма, записанного в символической форме, рассмотрена в работе [42]. Здесь рассмотрим способ перечисления прямо на графе. * Каждая реализация есть путь в графе от вх к вых. Сколько таких путей, столько и реализаций. В [52] дана классификация путей в графе алгоритма, согласно которой выделяются нуги: элементарный (без контуров) и сложный (с контурами), в том числе сложные пути с невложенными контурами и с вложением контуров. Число путей в графе с одним контуром может быть бесконечно большим, если не указано правило выхода из контура (это правило может быть и вероятностным). Таким образом, для перечисления реализаций вероятностного алгоритма задачи необходимо: выделить из графа элементарные пути; выделить сложные пути с контурами, невложенными и вложенными; указать правила выхода из контуров. а) Выделение элементарных путей. Из графа простой задачи на рисунке 3.4 выделяется лишь один элементарный путь, он показан на рисунке 3.5, а. |
107 Поскольку на уровне алгоритма задачи все задачи рассматриваем изолированно, то неизвестную (с точки зрения рассматриваемой задачи) вершину графа другой задачи, из которой исходит дуга, входящая в вершину «1», условимся обозначать вх. Также условимся неизвестную вершину графа другой какой-то задачи, в которую будет входить дуга, исходящая из «нашей» вершины «2», обозначать всегда вых. $х и вых надписываются над «зависающими» дугами графа алгоритмизуемой задачи, как на рисунке 3.4, и в дальнейшем (на этапе синтеза) послужат для соединения алгоритмов задач друг с другом. Г. Полученные элементы графа объединяются в граф Бержа, изображающий в обычной форме алгоритм задачи, как показано на рисунке 3.4. Если записать эту форму символически, то получим 1 2 2 1 Ф,Т"Ф"з""2"Ч1ч©4, где 1 \\изменение достигнуто , и тогда задача решена, С[ = <( [0 изменение не достигнуто, переход обратно к "3 {о всегда тождественно ложное условие, символизирующее возвращение в исходное состояние (т.е. прекращение работы). 2. Перечисление реализаций алгоритма. Алгоритм является вероятностным, если в его графе имеется хотя бы одно разветвление (т.е. из одной вершины выходит более одной дуги в другие вершины). Вершину, служащую началом разветвления, принято рассматривать как логический оператор, коI торый принимает значения, имеющие смысл частоты исходящих дуг. Однако непосредственно из графа алгоритма, построенного в предыдущей операции, не следует никакой информации о частоте исходящих дуг. Такую информацию можно получить, основываясь на том очевидном обстоятельстве, что частота есть функция исходов опыта. Но исходы опыта можно перечислить априори как возможные реализации общего алгоритма, полученные по комбинациям логических действий. 108 Процедура перечисления реализаций алгоритма, записанного в символической форме, рассмотрена в работе / 42 /. Здесь рассмотрим способ перечисления прямо на графе. Каждая реализация есть путь в графе от вх к вых. Сколько таких путей, столько и реализаций. В / 52 /дана классификация путей в графе алгоритма, согласно которой выделяются пути: элементарный (без контуров) и сложный (с контурами), в том числе сложные пути с невложенными контурами и с вложением контуров. Число путей в графе с одним контуром может быть бесконечно большим, если не указано правило выхода из контура (это правило может быть и вероятностным). Таким образом, для перечисления реализаций вероятностного алгоритма задачи необходимо: выделить из графа элементарные пути; выделить сложные пути с контурами, невложенными и вложенными; указать правила выхода из контуров. I Рис. 3.5. Перечисление реализаций по графу на рисунке 3.4. а элементарный путь; 6 сложные пути со степенью цикла 1,2,,.., к 109 а) Выделение элементарных путей. Из графа простой задачи на рисунке 3.4 выделяется лишь один элементарный путь, он показан на рисунке 3.5, а. б) Выделение сложных путей с контурами. В рассматриваемом графе задачи имеется один элементарный контур, включая который можно построить пути 1), 2),..., к), показанные на рисунке 3.5, б. в) Ограничение числа сложных путей достигается заданием фиксированного к (степени цикла). В простейшем случае полагают к = 1, т.е. ограничиваются одним сложным путем с контуром 1) на рисунке 3.5, б. Однако выше указывалось, что повторение контура ровно к раз подчиняется геометрическому распределению с параметрами, зависящими от обстоятельств. Во многих практически важных условиях вероятность Р(к < 4) < 0,9, т.е. можно ограничиться четырьмя сложными путями и одним элементарным (при к = 0), т.е. можно ограничиться четырьмя сложными путями и одним элементарным (при к = 0). Заканчивая описание операции 2, следует указать, что в простых задачах, графы которых имеют простые и сложные контуры, а также в сложных задачах перечисление реализации осуществляется по тому же принципу. 3. Взвешивание реализаций. Заключается в умножении .ртой реализации на ее вероятность Р}> причем для п реализаций Таким образом, задача состоит в определении множества вероятностей Ру Здесь могут быть выделены два случая: а) всякая информация о значениях отсутствует, тогда перечисленные реализации считаются равновероятностными каждая из п реализаций имеет вероятность 1 / п : б) степень контура (цикла) к фиксирована и имеются приближенные ( но достаточно правдоподобные) оценки для Ру В частности, для алгоритмов, связанных с непрерывным регулированием параметра и с отсчетом по прибору в условиях, когда требуется высокая надежность отсчета, оценки вероятностей реализации с циклом к-ой степени приведены в таблице 3.2. П |