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

139 6. Стратегии поиска Посмотрим, что это будут за величины при / = 10 для различных значений к (табл. 6.1). Предполагается, что 1000 вершин-последователей могут быть получены за 1 с, и что одна вершина требует 100 байт памяти. Эти значения соответствуют средним затратам времени и памяти, требуемым для решения многих иллюстративных задач типа головоломок. Из табл. 6.1 можно сделать два важных вывода. Во-первых, рост требований к памяти для решения задач поиском в ширину гораздо более серьезная проблема, чем рост требований ко времени решения тех же задач. Так, например, вполне приемлемо подождать решения задачи в течение 18 мин при / = 6, но необходимость наличия 111 Мбайт памяти для решения таких сравнительно простых задач кажется слишком высокой ценой. Во-вторых, для задач, в которых / > 10, помимо катастрофического увеличения требований к памяти, наблюдается стремительный рост временных затрат, не позволяющий решать реальные задачи с помощью поиска в ширину даже на современных мощных компьютерах. Это приводит к следующему заключению: Стратегии поиска, имеющие экспоненциальные оценки сложности решения задач по времени или памяти, в частности стратегия поиска в ширину, нельзя использовать для решения задач большой размерности, т.е. задач, у которых 1 > 10.