Главная  Кибернетика 

[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [ 17 ] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88]

2.10] ЭЛЕМЕНТАРНЫЕ ПУТИ 59

контур) является разомкнутым (замкнутым) путем, который не проходит ни через одно состояние более одного раза. Отсюда имеем:

Лемма 2.4. В автомате с п состояниями длина элементарного пути не может быть больше п-1, а длина элементарного контура не может быть больш,е п.

Путь, не являющийся элементарным, называется избыточным. В следующем параграфе будут рассмотрены некоторые задачи, в которых представляют интерес только элементарные пути. В случае, когда это имеет место, все члены niiUii ... у которых не все индексы /, 1,

/д, J различны, могут быть исключены из матрицы

переходов k-то порядка [Ж]*; получаемая при таком исключении матрица обозначается так: [Ж]*. Элемент (/, J) матрицы [Ж](*) представляет собой множество всех элементарных путей длины k, ведущих из в Оу в автомате Ж. Матрица [Ж]*" записывается в виде [М ] и является матрицей [Ж], в которой все диагональные элементы исключены (т. е. все диагональные элементы заменены нулями).

Лемма 2.5. [Ж] [Ж]* содержит все элементарные пути, содержащиеся в [Ж]*

Доказательство. Процесс умножения [Ж] на [Ж]*, как следует из (2.21), эквивалентен увеличению длины Л каждого пути, представленного в [Ж]*, до длины k-\-l посредством присоединения к концу пути одной из дуг, представленных в матрице [Ж]. Если путь из k дуг матрицы [Ж]* или присоединенная дуга избыточны, то результирующий путь длины k-\-l также должен быть избыточным. Следовательно, произведение [Ж] [Ж]*, где [Ж] образуется путем вычеркивания из [Ж] всех избыточных путей длины 1 и [Ж]** образуется путем вычеркивания из [Ж]** всех избыточных путей Длины k, должно содержать все элементарные пути, содержащиеся в [Ж] [Ж]*. Так как [Ж] [Ж]* = [Ж]*+\ то лемма доказана.

Лемма 2.5 означает, что в процессе построения [Ж]*"*" из [Ж] все избыточные пути можно исключать по мере их



появления в любой промежуточной матрице, так как это исключение никакого влияния на образование элементарных путей не оказывает. Этот результат позволяет предложить

упрощенный метод получения [Ж]* значительно менее трудоемкий, чем метод, по которому сперва получают [М]" и затем исключают из [Ж]* все избыточные пути.

Алгоритм 2.4. Дана [Ж], надо построить [Ж]" для /> 1. (1) Строим [Ж1, заменяя все диагональные элементы

в [Ж] нулями. Полагаем k=l. (2) Строим [Ж] [Ж]*. В произведении матриц заменяем каждый член, представляющий избыточный путь, нулем. Пусть результирующая матрица будет [Ж]*"". (3) (а) Если /г + 1 то увеличиваем Л на 1 и возвращаемся к (2). (б) Если k-\-l=l, то

[Жf=lЖ]".

Матрицы (2.26)-(2.29) иллюстрируют применение алгоритма 2.4 для построения [А1], [Alf по матрице [А1], представленной выражением (2.24)

[AlT и [Alf

"0

"45

(2.26)

/,(2

Я13Я32

113134

Я2Яз

Яз,Я,2

3445

Я45Я5,

Я41Я12

Я4Яз

ЯбЯ,,

Я5,Я12

ЯбЯ1з

(2.27)



- 0

Я1зЯз4Я45~

Я21Я13Я34

Я34Я45Я51

Яз4Я4Я2

Я4ЯзЯз2 4-Я45Я5Я2

Я45Я51Я13

Я51Я13Я32 + Я54Я41Я12

Я54Я4,Я,з

Я51Я,зЯз4

[AlT =

"0

л21л,злз4л45

"34"45"5l"l2

л45л5л,злз2

%4"4l"l3"32

(2.28)

(2.29)

Можно заметить, что, в то время как число ненулевых членов в [УИ]* имеет тенденцию расти по экспоненте с ростом k, число членов в [Ж]* имеет тенденцию оставаться постоянным до определенного значения величины k и уменьшаться для больших значений k. Действительно, из леммы 2.4 можно заключить, что если М является автоматом с п состояниями, то [Ж]* для всех kn состоит полностью из нулевых членов.

2.11. Определение минимальных путей и полных контуров

Для многих задач, представляющих практический интерес, с генерированием каждого входного символа связана некоторая стоимость, определяемая тем, что переход автомата из одного состояния в другое влечет за собой определенные затраты, пропорциональные числу дуг, которые необходимо при этом пройти. Для того чтобы уменьшить общую стоимость, в этих случаях желательно определить наикратчайший или минимальный путь между двумя состояниями.

Лемма 2.6. Минимальный путь, ведущий из состояния о,- в Oj, если он существует, должен быть элементарным путем.



[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [ 17 ] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88]

0.0011