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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

2
(1)
6
(2)
6 Проверка 4
(2)
, 5
(2)
,
6
(2)
3
(1)
1, 2
(1)
7 Заполнение
"о"
– 3
(1)
, 4
(2)
, 5
(2)
,
6
(2)
1, 2
(1)
8 Раскрытие
3
(1)
2
(3)
, 5
(3)
,
7
(3)
4
(2)
, 5
(2)
, 6
(2)
1, 2
(1)
,
3
(1)
9 Проверка 2
(3)
, 5
(3) *
,
7
(3)
4
(2)
, 5
(2)*
, 6
(2)
1, 2
(1)
,
3
(1)
Коррекция
5
(2)
2
(3)
, 7
(3)
4
(2)
, 5
(3)*
, 6
(2)
1, 2
(1)
,
3
(1)
Проверка 2
(3)*
, 7
(3)
4
(2)
, 5
(3)
, 6
(2)
1, 2
(1)*
Коррекция
2
(3)
7
(3)
4
(2)
, 5
(3)
, 6
(2)
1, 2
(3)*
Заполнение – 4
(2)
, 5
(3)
, 6
(2)
,
7
(3)
1, 2
(3)*
Таким образом, граф (рис. 1.23) преобразуется в дерево (рис. 1.25).
В этом случае, если бы стоимость дуг от вершины 3 к вершине 2 или вершине 5 оказалась бы боль-
ше уже рассчитанного, были бы оставлены те же материнские вершины, новые дуги были бы отброше-
ны, и граф (рис. 1.23) снова превратился бы в дерево.
Рассмотрим теперь пример перебора в глубину на графе с ограниченной глубиной перебора.
Пусть максимальная глубина равна 4. Граф имеет вид, представленный на рис. 1.26. В этом случае
порядок раскрытия вершин будет 1, 2, 5, 6 (табл. 1.4).
уровень
Рис. 1.24 Преобразование фрагмента графа (рис. 1.23)
Рис. 1.25 Преобразование фрагмента графа (рис. 1.23) в дерево
уровень
4
1
2
3
6 5 7
3
1
1
6
2
2 8
1
2
3
1
3
2
4 6 5 7
1
1
6 2
2
8

Страницы