ВУЗ:
Составители:
Рубрика:
Рис. 1.17 Алгоритм перебора вглубь
Рассмотренный алгоритм значительно эффективнее метода перебора вширь. Действительно для нахож-
дения оптимального пути 1-4-3-2-1 потребовалось раскрыть всего 8 вершин, построить же 13 вершин.
В этом алгоритме движение идет вдоль одного пути до конечной вершины, определяется стоимость
этого пути. Затем раскрываются другие пути. При этом движение вдоль следующего пути ведется до
тех пор, пока накопленные затраты не превысят уже достигнутых.
Для того, чтобы предотвратить слишком длительное движение вглубь в то время, как путь может
оказаться неперспективным, данный алгоритм дополняется некоторой предельной глубиной γ
пр
.
уровень
Рис. 1.18 Метод перебора в глубину
2
2
124
1
2
3
5
3
5
3
4
3
3
4
4
5
8
4
5
С = 11
2
С = 9
1
2
15
5
8
8 3
12 13 14
123
142
143
123
1243
1432
12341
14321
4
1
1
2
2 2
6
3
3
2
7
Страницы
- « первая
- ‹ предыдущая
- …
- 12
- 13
- 14
- 15
- 16
- …
- следующая ›
- последняя »
