Функции предшествования

Этот интересный метод придумал Р.Флойд – автор многих остроумных решений в программировании. Вместо матрицы строятся две специальные функции f и g, такие что:

1. Если S_i∙*> S_j Þ f(S_i) > g(S_j).

2. Если S_i <* S_j Þ f(S_i) < g(S_j).

3. Если S_i =* S_j Þ f(S_i) = g(S_j).

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

Построение функций предшествования:

0. Строится матрица предшествования и начальные значения функций принимаются равными единице: f(S_i) = g(S_j) = 1.

1. Матрица просматривается по строкам в поисках отношений ∙*> и, если

f(S_i) > g(S_j), то идем дальше, если же S_i *> S_j, а f(S_i) ≤ g(S_j), то увеличиваем значение f(S_i) - f(S_i) = g(S_j) + 1.

2. Матрица просматривается по столбцам в поисках отношений <*∙ и, если

f(S_i) < g(S_j), то идем дальше, если же S_i <* S_j, а f(S_i) ³ g(S_j), то увеличиваем значение g(S_j) - g(S_j) = f(S_i) + 1.

3. Матрица просматривается в поисках отношений =* и, если f(S_i) = g(S_j), то идем дальше, если S_i =* S_j, а f(S_i) ¹ g(S_j), то выравниваем значения функций путем увеличения меньшего из значений до большего - f(S_i) = g(S_j) = max[f(S_i), g(S_j) ].

4. Возвращение к первому пункту.

Повторять до тех пор, пока рост функций не прекратится (или когда значение одной из функций не превысит 2*n, где n - размерность матрицы - в этом случае алгоритм не сходится).

Пример.

На основе матрицы предшествования в соответствии с описанным алгоритмом построим функции предшествования.

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

4 4 3 2 2 3 2 1 1 1 1 1

g(S_j)

f(S_i)

	A	B	C	D	E
A		∙>	<∙	∙>	∙
B		∙
C	<∙
D	∙>
E		∙		∙>

3 2 1 4 3 1 6 5 3 2 1 2 1

В результате получим числовые значения (табличных) функций для всех символов.

	A	B	C	D	E
f
g

Однако, этот метод не свободен от недостатков:

1. Алгоритм не всегда сходится (не всегда приводит.к построению функций).

2. При переходе к функциям происходит «незаконное доопределение» матрицы. То есть как бы появляются отношения предшествования между парами символов, для которых в исходной матрице отношение отсутствовало.