|
определены и единственны начальный и конечный узлы. Обозначим их w.H и W.T соответственно. Узел графа реализации будем обозначать буквой «х» (х е w). x.v узел МГЕРТ-сети, которому соответствует узел графа реализации (x.v е V). x.Prs, x.DFs — значения вещественных и стохастических параметров узла графа реализации. Будем обозначать w={x} — граф реализации, состоящий из единственного узла х. Тогда w.H = w.T = х. Введем операции построения графа реализации: w = M(wi, w2) новый граф реализации сети, являющийся объединением графов Wj и w2дугой из w2.H в Wj.T. Частным случаем данной операции будем считать М(х, w) = М({х}, w) и M(w, х) = M(w, {х}). w = M (wb W, w2) новый граф реализации сети, являющийся объединением дугами конечного узла Wi.T со всеми начальными узлами Wj.H (Wj е W) и объединением дугами конечных узлов Wj.T с начальным узлом w2.H. 3.2.Обратный алгоритм расчета МГЕРТ-сети Общая идея обратного алгоритма расчета МГЕРТ-сети заключается в следующем: обход графа МГЕРТ-сети ведется от выбранного стока к источнику; обход ведется с помощью рекурсивного алгоритма; для каждого узла, имеющего EOR-вход, запускается столько же рекурсивных вызовов процедур (ветвей обхода), сколько дуг входит в данный узел; для каждого узла i, имеющего 10Rили AND-вход, запускается рекурсивный вызовов процедуры расчета узла j, являющегося детерминированным источником узла i, затем рассчитываются все пути 67 |
единственны начальный и конечный узлы. Обозначим их w.H и w.T соответственно. Узел графа реализации будем обозначать буквой «х» (х е w). x.v узел МГ-сети, которому соответствует узел графа реализации (x.v е V). x.Prs, x.DFs значения вещественных и стохастических параметров узла графа реализации. Будем обозначать w={x} граф реализации, состоящий из единственного узла х. Тогда w.H = w.T = х. Введем операции построения графа реализации: w = M(W, w2) новый граф реализации сети, являющийся объединением графов W и w2 дугой из w2.H в W.T. Частным случаем данной операции будем считать М(х, w) = М({х}, w) и M(w, х) = M(w, {х}). w = M(wb W, w2) новый граф реализации сети, являющийся объединением дугами конечного узла Wi.T со всеми начальными узлами Wj.H (wj е W) и объединением дугами конечных узлов Wj.T с начальным узлом w2.H. В блок-схемах, представленных в Приложениях 1-5, индексы переменных будем отображать в квадратных скобках, т.к. MS Visio не позволяет использовать надстрочные и подстрочные индексы. 3.2 Обратный алгоритм расчета МГ-сети Общая идея обратного алгоритма расчета МГ-сети заключается в следующем: обход графа МГ-сети ведется от выбранного стока к источнику; обход ведется с помощью рекурсивного алгоритма; для каждого узла, имеющего EOR-вход, запускается столько же рекурсивных вызовов процедур (ветвей обхода), сколько дуг входит в данный узел; для каждого узла i, имеющего IORили AND-вход, запускается рекурсивный вызовов процедуры расчета узла j, являющегося 57 детерминированным источником узла i, затем рассчитываются все пути от j к i и, используя найденные пути, строятся все реализации, завершаемые узлом i; расчет вещественных и стохастических переменных производится при «выходе» алгоритма из рекурсии. Блок-схема алгоритма представлена в Приложениях 1-3. Результатом работы главной процедуры «ОРасчитатьСеть» являются множества реализаций для каждого из стоков, обработка которых будет представлена в пятом параграфе. 3.3 Прямой алгоритм расчета МГ-сети Общая идея прямого алгоритма расчета МГ-сети заключается в следующем: обход графа МГ-сети ведется от источника к стокам; обход ведется с помощью рекурсивного алгоритма; для каждого узла, имеющего стохастический выход, запускается столько же рекурсивных вызовов процедур (ветвей обхода), сколько дуг выходит из данного узла; для каждого узла i, имеющего детерминированный выход, рассчитываются все пути от i к j, и, используя найденные пути, строятся все реализации, завершаемые узлом j, где j детерминированный сток узла i; расчет вещественных и стохастических переменных производится при «углублении» алгоритма рекурсии. Блок-схема алгоритма представлена в Приложениях 3-5. Результатом работы главной процедуры «ПРасчитатьСеть» являяются множества реализаций, обработка которых будет представлена в четвертом параграфе. Следует отметить, что для использования прямого алгоритма расчета МГсети необходимо выполнение 0 5 ’. 58 |