Page 86 - 4128

a 1
1
2

1
а 2 а 5
1
2
1
3

2
а 3 а
4

Рисунок 4.6 – Граф-схема автомата

Евристичний алгоритм складається з наступних
кроків:

1 Будуємо матрицю Т , що складається зі всіх пар
номерів (i, j), для яких р(i, j)  0 (тобто в автоматі є перехід з аi в
аj або навпаки) і i<j. Для кожної пари в матриці Т вказуємо її
вагу р(i, j), співпадаючу з вагою ребра сполучаючого аi і аj.

i j p(i,j)
1 2 2
1 3 1
T = 1 5 1
2 3 3
2 4 1
2 5 1
3 4 2
3 5 2

85