ВУЗ:
Составители:
Рубрика:
"о" 4
(1)
14 Раскрытие
3
(1)
6
(3)
, 8
(3)
,
4
(3)
7
(6)
, 4
(1)
1, 2
(1)
, 5
(2)
, 6
(5)
,
3
(1)
а Проверка
"о"
6
(3)
, 8
(3)
,
4
(3)*
7
(6)
, 4
(1)*
1, 2
(1)
, 5
(2)
, 6
(5)
,
3
(1)
б Коррекция
"о"
6
(3)
, 8
(3)
7
(6)
, 4
(3)*
1, 2
(1)
, 5
(2)
, 6
(5)
,
3
(1)
15
в
Проверка "з" 6
(3)*
, 8
(3)
7
(6)
, 4
(3)
1, 2
(1)
, 5
(2)
, 6
(5)*
,
3
(1)
г Коррекция
"з"
8
(3)
7
(6)
, 4
(3)
1, 2
(1)
, 5
(2)
, 6
(5)
,
3
(1)
д Заполнение
"о"
– 7
(6)
, 8
(3)
,
4
(3)
1, 2
(1)
, 5
(2)
, 6
(5)
,
3
(1)
Вначале проверяется, не содержится ли какая-нибудь дочерняя вершина (6
(3)
, 8
(3)
, 4
(3)
) в списке "о".
Оказывается, что в этом списке есть вершина 4. Далее проверяется, что лучше: 4
(3)
или 4
(1)
.
Двигаясь по стрелкам от дочерних вершин к материнским, получают путь 4-3-1 и второй путь 4-1,
ясно, что эти пути создают цикл 4-3-1-4. Причем затраты на пути 4-3-1 меньше (равны), чем на пути 4-1,
которые равны 6.
Поэтому выгодно считать предком вершины 4 не вершину 1, а вершину 3. В этом случае список "о"
корректируется (этап 15, б табл. 1.4), и граф на рис. 1.26 трансформируется в граф, представленный на
рис. 1.27.
Затем на этапе 15, в проверяется, не содержится ли одна из оставшихся вершин 6
(3)
или 8
(3)
в списке
"з".
Оказывается, в списке "з" есть вершина 6
(5)
, а среди дочерних вершин 6
(3)
. Следуя от потомков к
предкам, получают два пути, составляющие вместе цикл. Один путь 6-3-1, второй – 6-5-2-1. При этом
путь 6-3-1 стоит 5 единиц, а путь 6-5-2-1 – 13 единиц. Путь 6-3-1 выгоднее и на этапе 15, г предок вер-
шины 6 заменяется.
Вершина 8
(3)
не находится ни в списке "о", ни в списке "з", и поэтому вносится в список "о". При
этом граф, изображенный на рис. 1.27, преобразуется в граф, представленный на рис. 1.28.
уровень
Рис. 1.27 Преобразованный граф (рис. 1.26)
уровень
1
2 3
5 8 4
6
7
3
3
4
6
8
2
2
6
1
2
3
4
5
1
2 3
5 6
8
4
3
3
4
2
2
6
1
2
3
Страницы
- « первая
- ‹ предыдущая
- …
- 22
- 23
- 24
- 25
- 26
- …
- следующая ›
- последняя »
