ВУЗ:
Составители:
Рубрика:
Если она уже появлялась, т.е. содержится в списках "о" или "з", производится коррекция уже полу-
ченных результатов, приходится возвращаться к предыдущим вершинам, чего никогда не бывает при
работе с деревьями, и корректировать, если нужно стрелку (указание материнской вершины), глубину
вершины, ее оценку.
Для примера рассмотрим метод слепого поиска вширь. Пусть фрагмент графа имеет вид, изобра-
женный на рис. 1. 23. В табл. 1.3 приведены этапы алгоритма, представленного на рис. 1.14, дополнен-
ного блоками проверки списков "о" и "з" и отбрасыванием тех вершин, которые уже есть в списке.
На первом этапе в список "о" перемещается вершина 1.
На втором этапе вершина 1 перемещается в список "з" и раскрывается, т.е. определяются ее дочер-
ние вершины 2 и 3.
уровень
Рис. 1.23 Фрагмент графа полного перебора (перебора вширь)
На третьем этапе проверяется, не находятся ли вершины 2 и 3 уже в списке "о" или "з".
На четвертом этапе вершины 2
(1)
и 3
(1)
, где индекс (1) указывает, что их материнской вершиной яв-
ляется вершина 1, помещаются в список "о".
Действия этапов 5, 6, 7 аналогичны действию этапов 1, 3, 4.
На этапе 8 раскрывается вершина 3
(1)
, первая из списка "о", ее дочерними вершинами являются 2
(3)
,
5
(3)
, 7
(3)
, где индекс (3) указывает, что их материнской вершиной является вершина 3.
Однако, на этапе 9 блок проверки обнаруживает, что вершина 5 уже находится в списке "о", при
этом ее материнской вершиной является вершина 2. Кроме того, блок проверки находит, что цена дуги
2-5 больше, чем цена дуги 3-5. В связи с этим блок коррекции меняет для вершины 5 материнскую вер-
шину. Вместо вершины 5
(2)
в список "о" записывается вершина 5
(3)
.
Фрагмент графа (рис. 1.23) приобретает вид, представленный на рис. 1.24.
Вершины 2
(3)
, 7
(3)
не содержатся в списке "о". Далее следует проверить, содержатся или нет верши-
ны 2
(3)
, 7
(3)
в списке "з".
Оказывается, что вершина 2 находится в списке "з". Указатель (стрелка) направлен (табл. 1.3) на
вершину 1. Затраты на дуге 1-2 при этом составляют 3 единицы. Так как на дуге 3-2 затраты меньше
(всего лишь 1 единица), алгоритм изменяет направление стрелки вершины 2. Теперь материнской вер-
шиной для нее становится вершина 3 (табл. 1.3).
Фрагмент графа приобретает вид, представленный на рис. 1.25, вместо графа на рис. 1.24.
1.3 Этапы раскрытия графа
Дочерние Вершины
Этап Действие
вершины Список "о"
Список
"з"
1 Заполнение
"о"
– 1 –
2 Раскрытие 1 2
(1)
, 3
(1)
– 1
3 Проверка 2
(1)
, 3
(1)
– 1
4 Заполнение
"о"
– 2
(1)
, 3
(1)
1
5 Раскрытие 4
(
2
)
, 5
(
2
)
, 3
(1)
1, 2
(1)
1
2 3
4 5 6 7
3
1
6
5
1
2
8
1
2
3
Страницы
- « первая
- ‹ предыдущая
- …
- 19
- 20
- 21
- 22
- 23
- …
- следующая ›
- последняя »
