|
106 б) Выделение сложных, путей с контурами. В рассматриваемом графе задачи имеется один элементарный контур, включая который можно построить пути 1), 2), к), показанные на рисунке 3.5, б. в) Ограничение числа сложных путей достигается заданием фиксированного к (степени цикла). В простейшем случае полагают к = 1, т.е. ограничиваются одним сложным путём с контуром 1) на рисунке 3.5, б. Однако выше указывалось, «*го повторение контура ровно к раз подчиняется геометрическому распределению с параметрами, зависящими от обстоятельств. Во многих практически важных условиях вероятность Р(к < 4) < 0,9, т.е. можно ограничиться четырьмя сложными путями и одним элементарным (при к = 0), т.е. можно ограничиться четырьмя сложными путями и одним элементарным (при к = 0). Рисунок 3.5. Перечисление реализаций по графу на рисунке 3.4. а элементарный путь; б сложные пути со степенью цикла 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. П |