ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 30.06.2024
Просмотров: 102
Скачиваний: 0
2.По множеству Н строим граф Г.
3.Находим множество F0 всех дуг графа Г, имеющих вес, равный
О, и полагаем, что Z = |
F0. |
|
|
|
|
|
|||
4. |
Если F0 = |
0, |
то переходим к пункту 5, иначе к пункту 8. |
||||||
5. |
Находим множество F всех дуг графа Г, имеющих максималь |
||||||||
ный вес. Из множества F выделяем множество F' всех дуг, ведущих |
|||||||||
в вершину у. Объединяем множества Z и F'. Полученное множество |
|||||||||
обозначим через Z . По формуле (6.9) строим множества Z( для |
всех |
||||||||
Xj £ |
X. По формуле (6.10) строим отношения ф,- для |
всех |
хс |
£ |
X. |
||||
Для каждого отношения ф,- вычисляем параметр |
|
y - j . |
|
|
|
||||
6. |
Если F' = |
0, |
то |
переходим к следующему |
пункту, |
иначе |
|||
переходим к пункту 8. |
|
|
|
|
|
|
|||
7. |
Из множества F выбираем множество всех |
тех |
дуг |
({s, |
t), |
||||
.V;), для которых |
у |
отношения ф,- параметр [tt |
^-j |
минимален. |
|||||
Среди выбранных дуг выделяем одну дугу ({s, t), xj) с наименьшим номером /, 1 < : I <: | X |, для которого параметр fe, отношения ф, минимален. Помещаем выделенную дугу в множество Z . По множест ву Z строим множества Zt, отношения ф£ для всех xt и вычисляем
параметры
8.Из множества Н удаляются все те графы Г (s, t, р), для ко торых множество Z покрывает множество R (s, t, р).
9.Если Н = 0,ю конец вычислений, иначе переходим к пунк
ту 10.
10.По множеству Н строим граф Г и переходим к пункту 5. Из описания алгоритма А2 следует, что любое множество Z,
построенное по этому алгоритму, является решением задачи 1, т.е. Z покрывает множество всех дуг графа Г, построенного по множеству
Пусть множество Z есть некоторое решение задачи 1 и не обяза тельно получено по алгоритму А2. Пусть F0 — множество всех дуг исходного графа Г, имеющих вес 0. Очевидна следующая теорема.
Теорема 6.7. Всякое решение Z задачи 1 содержит множество F0.
Пусть множество Z = [гъ rv) получено с помощью алгоритма А2, причем дуги B Z занумерованы в порядке их помещения в мно жество Z алгоритмом (если на некотором шаге алгоритма множество Z пополнилось несколькими дугами, то они занумерованы произ вольно). Напомним, что М (гг) — наибольшее множество дуг ис ходного графа Г, которое покрывается дугой г(.
Теорема 6.8. Для всех і Ф /, 1 < . i, j •< v,
М |
{rL) |
gt M (ri). |
|
|
|
|
Д о к а з а т е л ь с т в о . |
Пусть і Ф j . Предположим, что дуги |
|||||
г/ и Гі помещены в Z на одном и том же шаге работы алгоритма А2. |
||||||
Это возможно в двух случаях: |
1 ) г(, |
г/ £ F0- |
Тогда |
из |
правил по |
|
строения графа Г следует, |
что |
М |
(г,) f] М |
(rj) = |
0 |
и, значит, |
M (rj) g t M (rj). |
2) |
На том |
шаге |
алгоритма, |
когда |
дуги |
rt и Л/ |
|
помещаются в Z, они |
принадлежат множеству |
F' (см. блок 5 алго |
||||||
ритма Л2). Это значит, что дуги г( и |
Г/ ведут |
в |
вершину у. |
Тогда |
||||
из правил построения графа Г следует, что М |
(rj) g£ М |
(г,). Теперь |
||||||
предположим, что дуги г( и г/ помещены в множество Z на разных |
||||||||
шагах алгоритма А2. Пусть /" < ; і. Поскольку |
на том шаге алгорит |
|||||||
ма, когда дуга т{ помещается |
в Z, в графе Г нет |
ни одной дуги из |
||||||
множества М (rj} |
(см. блоки 8, 9, 10, 5), то М |
(rj) с£. М |
{rj). |
Пусть |
||||
|
Рис. 19. |
Граф Г. |
|
Рис. 20. Граф |
Г'. |
|
|||||
теперь і <z j н М (rj) s |
М (rj). |
Из этого предположения |
следует, |
||||||||
что Г/$ F0 и |
что |
|
на том шаге, когда дуга rL помещается |
в Z, ее вес |
|||||||
не меньше веса дуги Г/. Так как дуга г,- все же помещена |
в множест |
||||||||||
во Z после дуги г{, |
то М |
(rj) Ф |
М (rj), |
значит М |
(rj) cz М |
(rj). |
Из |
||||
последнего соотношения следует, что на том шаге, когда дуга |
г, |
||||||||||
помещена в Z, ее вес меньше веса дуги г,-. Противоречие доказывает |
|||||||||||
теорему. |
|
|
Для |
|
всех |
і, 1 < |
і •< v, М |
|
|
|
и |
Следствие |
6.3. |
|
(rj) Cjt M (Zl) |
||||||||
M (Я)фМ |
(rj), |
w e Z ' |
= |
{ r l f |
A U , } . |
|
|
|
|
||
Множество Z, |
построенное по алгоритму А2, по своим функциям |
||||||||||
аналогично множеству конечных переходов, которое рассматрива лось в разделе 6.3.
Последовательное решение задачи I с помощью алгоритма А2 и затем задачи 2 с помощью алгоритма А1 позволяет получить такую эквивалентность л, что для собственного л-расширения автомата А
любая последовательность р £ Р будет (S0 , |
со, ^-разрешающей. |
В общем случае, полученная эквивалентность |
не имеет минималь |
ного числа классов. |
|
В заключение рассмотрим пример. Пусть автомат А задан |
табл. 38 |
|||
и пусть Р = |
{1110, |
10100), -ф (р) = 0 для всех р £ Р, |
со = |
ц, т. е. |
необходимо |
строить |
такую эквивалентность я, чтобы |
собственное |
|
jx-расширение автомата А было Р-диагностируемьш. |
|
|
||
Граф Г, построенный по множеству #„, представлен на рис. 19. Каждой дуге г этого графа приписана отметка х/т (г). Алгоритм А2 строит множество Z за два шага. На первом шаге в Z помещается дуга
|
|
Т а б л и ц а 38 |
|
|
|
Т а б л и ц а 39 |
|||
|
0 |
1 |
0 |
1 |
|
0 |
1 |
0 |
1 |
1 |
9 |
4 |
0 |
0 |
1 |
2 |
4 |
000 |
000 |
2 |
5 |
5 |
1 |
0 |
2 |
5 |
5 |
100 |
000 • |
3 |
4 |
3 |
1 |
1 |
3 |
4 |
3 |
100 |
100- |
4 |
2 |
6 |
0 |
0 |
4 |
2 |
6 |
000 |
000 • |
5 |
4 |
7 |
1 |
0 |
5 |
4 |
7 |
110 |
010 |
6 |
I |
8 |
0 |
1 |
6 |
1 |
8 |
000 |
100 |
7 |
4 |
5 |
0 |
1 |
7 |
4 |
5 |
000 |
100 |
8 |
4 |
2 |
1 |
1 |
8 |
4 |
2 |
100 |
100 |
({4, 5}, 1). После этого строится граф Г', представленный нарис. 20. На втором шаге в Z помещаются дуги ({5, 8}, 0), ({3, 8}, 0), ({3, 5), 6) и полученное множество равноZ = {({4, 5}, 1), ({5, 8), 0), ({3, 8), 0), (J3, 5,}0)}. Это Z покрывает все дуги графа Г. Тогда Z0 = {{5, 8}, {3, 8}, {3, 5}}, и Zx = {{4, 5}}.
Алгоритм А\ дает следующие разбиения:
П о = { 1 , 2 , 3, 4, 6, 7; 5; 8}, 11! = {1,2, 3,4, 6, 7, 8; 5}.
По формуле (6.11) построим разбиение
П = |
{(1,0), (2,0), (3,0), (4,0), (5,0), (6,0), (7,0), (1,1), (2,1), (3,1), (4,1); |
|||
|
|
(6,1), (7,1), (8,1), (5,0), (5,1); (Щ). |
- |
|
Закодируем |
классы |
разбиения П следующим образом: Ki — 00; |
||
/<2 = |
10; Кз |
— 01. |
Тогда собственное я-расширение |
автомата А |
представлено |
табл. |
39. |
|
|
Л И Т Е Р А Т У Р А
1. |
А й з е р м а н |
М. А., |
Г у с е в Л. А., |
Р о з о н о э р Л. И., С м и р н о - |
2. |
в а Л. И., Т а л ь А. А. Логика. Автоматы. Алгоритмы. Физматгиз, М., 1963. |
|||
Б а р а ш к о |
А. С , |
Б о г о м о л о в |
А. М.— Автоматика и вычислитель |
|
|
ная техника, |
1971, 1. |
|
|
3.Б а р а ш к о А. С.— В кн.: Кибернетика (Донецкое отделение). Вып. 1. Изд. Ин-та кибернетики АН УССР, К-, 1970.
4.Б а р а ш к о А. С.— В кн.: Кибернетика (Донецкое отделение). Вып. 1. Изд. Ин-та кибернетики АН УССР, К-, 1968.
5. Б а р а ш к о А. С. — Автоматика и телемеханика, 1970, 5.
6.Б а р а ш к о А. С. — В кн.: Труды I Всесоюзного совещания по техничес кой диагностике. «Наука», М., 1972.
7. |
Б а р з д и н ь Я. М. — В кн.: Проблемы кибернетики. Вып. 21. «Наука», |
|||||||
8. |
М., 1969. |
|
|
|
|
|
|
|
Б е р ж К- Теория графов и ее применения. ИЛ, М., 1962. |
|
|||||||
9. |
Б и р к г о ф Г. |
Теория структур. ИЛ, М., 1952. |
|
|||||
10. |
Б о г о м о л о в |
А. М., |
Г р у н с к и й |
И. С.— Автоматика и телемеханика, |
||||
|
1970, |
5. |
А. М., |
Г р у н с к и й |
И. С.— Кибернетика, 1971, 1. |
|||
П . Б о г о м о л о в |
||||||||
12. |
Б о г о м о л о в |
А. М., |
Т в е р д о х л е б о в |
В. А.— В кн.: Кибернетика |
||||
13. |
(Донецкое отделение). Вып. 1. Изд. Ин-та кибернетики АН УССР, К-, 1967. |
|||||||
Б о г о м о л о в |
А. М., |
Т в е р д о х л е б о в |
В. А.— В |
кн.: Кибернетика |
||||
14. |
(Донецкое отделение). Вып. 2. Изд. Ин-та кибернетики АН УССР, К-, 1968. |
|||||||
Б о р о д я н с к и й |
Ю. М.— Кибернетика, 1965, 6. |
В. И., Т и м о - |
||||||
15. |
В е р з а к о в |
Г. Ф., |
К и н ш т Н. В., |
Р а б и н о в и ч |
||||
|
н е й |
Л. С. Введение в техническую диагностику. «Энергия», М., 1968. |
||||||
16.Г и л л А. Введение в теорию конечных автоматов. «Наука», М., 1966.
17.Г л у ш к о в В. М.— УМН, 1961, 16, 5.
18.Г л у ш к о в В. М. Синтез цифровых автоматов. Физматгиз, М., 1962.
19.Г р у н с к и й И. С.— Автоматика и телемеханика, 1971, 12.
20.Г р у н с к и й 'И. С— Автоматика и телемеханика, 1972, 3.
21.Г р у н с к и й И. С.— В кн.: Теория автоматов. Вып. 2. Изд. Ин-та киберне тики АН УССР, К-, 1969.
22.Г р у н с к и й И. С.— В кн.: Труды I Всесоюзного совещания по технической диагностике. «Наука», М., 1972.
23. |
Г р у н с к и й |
И. С, |
Р у б е н о в и ч |
Ю. А.— Автоматика и телемеханика, |
|||||
24. |
1971, 11. |
|
В. А.— В кн.: |
Проблемы кибернетики. Вып. 11. «Наука», |
|||||
Д у ш с к н й |
|||||||||
25. |
М., 1964. |
Б ь ю н е м а н О . — В кн.: На пути к теоретической биологии. |
|||||||
3 и м а н Э., |
|||||||||
26. |
ИЛ, М., |
1970. |
|
|
|
ИФАК «Теория конечных и вероят |
|||
И в е н |
Ш.— В кн.: Труды симпозиума |
||||||||
27. |
ностных автоматов». «Наука», М., 1965. |
|
синтеза |
цифровых автоматов. |
|||||
К а з н а ч е е в |
В. |
И.— В |
кн.: Проблемы |
||||||
28. |
«Наука»,,М., 1967. |
|
|
|
П. П., |
С о г о м о н я н Е. С. |
|||
К а р и б с к и й |
В. В., П а р х о м е н к о |
||||||||
|
Техническая диагностика объектов контроля. «Энергия», М., 1967. |
||||||||
29. . К о р ш у н о в А. Д.— В кн.: Дискретный анализ. Вып. 10. «Наука», Ново-, сибирск, 1967.
30. К о р ш у н о в А. Д.— ДАН СССР, 1969, 184, 1.
