Студопедия.Орг Главная | Случайная страница | Контакты | Мы поможем в написании вашей работы!  
 

Дерево достижимости



Алго­ритм построения дерева достижимости

Каждая вершина дерева достижимости связывается с расширенной маркировкой μ: в расширенной маркировке число фишек в позиции может быть либо неотрица­тельным целым, либо ω. Каждая вершина классифицируется как граничная вершина, терминальная вершина, дублирующая вершина, или как внутренняя вершина. Граничными являются вершины, которые еще не обработаны алгоритмом; алгоритм пре­вратит их в терминальные, дублирующие или внутренние вершины.

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

Пусть x – любая граничная вершина с маркировкой μ[x], которую необходимо обрабо­тать.

1. Если в дереве имеется другая вершина y, не являющаяся гра­ничной, и с ней связана та же маркировка, μ[x] = μ[у], то вер­шина x - дублирующая.

2. Если для маркировки μ[х] ни один из переходов не разрешен
(т. е. δ(μ[х],tj) не определено для всех tj € Т), то х - терминаль­ная вершина.

3. Для всякого перехода tj € Т, разрешенного в μ[х] (т. е. δ(μ[х],tj) определено), создать новую вершину z дерева дости­жимости. Маркировка μ[z], связанная с этой вершиной, определя­ется для каждой позиции pi следующим образом:

а) Если μi[x] = ω, то μi[z] = ω.

б) Если на пути от корневой вершины к х существует вершина
у с μ[у] < μ[δ(μ[х],tj)] и μi[у] < μi[δ(μ[х],tj)], то μi[z] = ω.

в) В противном случае μi[у] = μi[δ(μ[х],tj)].

Дуга, помеченная tj, направлена от вершины х к вершине z. Вершина х переопределяется как внутренняя, вершина z стано­вится граничной.

Когда все вершины дерева - терминальные, дублирующие или внутренние, алгоритм останавливается.





Дата публикования: 2015-01-23; Прочитано: 319 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!



studopedia.org - Студопедия.Орг - 2014-2024 год. Студопедия не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования (0.005 с)...