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

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

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

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

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

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

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

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

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

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

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

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

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