Методы исследования операций при принятии решений. Бодров В.И - 23 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

Рис. 1.26 Фрагмент графа, раскрываемого перебором в глубину
На этапе 14 должна была бы раскрываться вершина 7, как имеющая наибольшую глубину, но так
как ее глубина превышает предельный уровень, равный 4, то она не раскрывается.
На этапе 14 вместо вершины 7 раскрывается самая глубокая вершина, уровень которой не превы-
шает максимального. Это вершина, стоящая первой в списке "о", т.е. 3
(1)
. Ее дочерними вершинами, как
это следует из рис. 1.26, будут вершины 6, 8, 4.
Следующим этапом после раскрытия вершины 3
(1)
(табл. 1.4) будет проверка и коррекция списков
"о" и "з".
1.4 Порядок раскрытия графа в глубину
Вершины
Эта
п
Действие
Дочерние
вершины
Список
"о"
Список "з"
1 Заполнение
"о"
– 1 –
2 Раскрытие 1 2
(1)
, 3
(1)
,
4
(1)
– 1
3 Проверка 2
(1)
, 3
(1)
,
4
(1)
– 1
4 Заполнение
"о"
– 2
(1)
, 3
(1)
,
4
(1)
1
5 Раскрытие
2
(1)
5
(2)
3
(1)
, 4
(1)
1, 2
(1)
6 Проверка 5
(2)
3
(1)
, 4
(1)
1, 2
(1)
7 Заполнение
"о"
– 5
(2)
, 3
(1)
,
4
(1)
1, 2
(1)
8 Раскрытие
5
(2)
6
(5)
3
(1)
, 4
(1)
1, 2
(1)
, 5
(2)
9 Проверка 6
(5)
3
(1)
, 4
(1)
1, 2
(1)
, 5
(2)
10 Заполнение
"о"
– 6
(5)
, 3
(1)
,
4
(1)
1, 2
(1)
, 5
(2)
11 Раскрытие
6
(5)
7
(6)
3
(1)
, 4
(1)
1, 2
(1)
, 5
(2)
, 6
(5)
12 Проверка 7
(6)
3
(1)
, 4
(1)
1, 2
(1)
, 5
(2)
, 6
(5)
13 Заполнение – 7
(6)
, 3
(1)
, 1, 2
(1)
, 5
(2)
, 6
(5)
2 3
5 8
4
6
7
3
3
4
6
8
2
2
6
1
2
3
4
5
1

Страницы