Искусственный интеллект

6.2.2. Монотонный поиск в ширину Поиск в ширину обеспечивает нахождение целевого состояния, находящегося на минимальной глубине дерева поиска. Однако минимальность цены пути при этом не гарантируется. Монотонный поиск в ширину является некоторой модификацией поиска в ширину, заключающейся в том, что в процессе поиска в ширину всякий раз, когда определяется очередная вершина-последователь, одновременно вычисляется цена пути, ведущего в эту вершину. Эта цена пути Таблица 6.1 Глубина дерева Количество вершин Требуемое для поиска время Требуемая для поиска память 0 1 1 миллисекунда 100 байт 2 111 0,1 секунды 11 килобайт 4 11.111 11 секунд 1 мегабайт 6 106 18 минут 111 мегабайт 8 108 31 час 11 гигабайт 10 1010 128 дней 1 терабайт 12 Ю'2 35 лет 111 терабайт