Поиск в ширину

Слепой поиск

Одна из самых очевидных стратегий поиска называется поиском в ширину. Поиск начинается с корневой вершины, определяются все последователи корневой вершины, затем все последователи каждого из последователей корневой вершины, далее все последователи каждого из последователей, найденных на предыдущем шаге, и т.д. до тех пор, пока не будут найдены все вершины, соответствующие целевым состояниям. Согласно этой стратегии, вершины глубиной k ищутся после того, как будут найдены все вершины глубиной k-1. На рис. 4. 1 показана последовательность нахождения вершин при поиске в ширину и при числе последователей каждой вершины, равном 2.

При поиске в ширину сначала рассматриваются все пути, длина которых равна 1, затем длиной 2 и т.д. Очевидно, что поиск в ширину удовлетворяет критерию полноты и минимальности, поскольку в процессе этого поиска рассматриваются все пути, ведущие из начальной вершины (состояния) во все остальные.

Оценим время и память, затрачиваемые в процессе поиска в ширину. Будем полагать, что число последователей каждой вершины равно l. Тогда в начале поиска в ширину мы имеем одну начальную вершину, затем l последователей, потом l² последователей и т.д. В общем случае при глубине дерева поиска, равной к, число вершин, изучаемых в процессе поиска, равно 1 + l+ l ²+ l ³+...+ l ^k. При конкретных значениях l и k по этой формуле можно вычислить максимальное число вершин дерева поиска, которое может быть получено в процессе поиска в ширину. Естественно, решение можно найти раньше, чем будут найдены все последователи.

Однако для некоторых задач эта величина может быть достигнута. Обычно вместо этой формулы употребляют ее обозначение в виде O(l ^k), которое называют экспоненциальной оценкой сложности.

Рис. 4.1. Деревья поиска в ширину при l=2: нулевая вершина (дерево

глубиной k=0), дерево после нахождения последователей нулевой вершины

(дерево глубиной k = 1), дерево после нахождения последователей первой

вершины, дерево после нахождения последователей второй вершины

(дерево глубиной k = 2)

Если полагать, что получение каждого последователя требует одной единицы времени, то O(l^k) является оценкой сложности по времени. В процессе поиска в ширину каждая вершина дерева должна сохраняться до получения требуемого решения. Если полагать, что для этого сохранения требуется единица памяти, то та же формула является одновременно и оценкой сложности по памяти для поиска в ширину.

			Таблица 4.1
Глубина дерева	Количество вершин	Требуемое для поиска время	Требуемая для поиска память
		1 миллисекунда	100 байт
		0,1 секунды	11 килобайт
	11.111	11 секунд	1 мегабайт
	10^6	18 минут	111 мегабайт
	10^8	31 час	11 гигабайт
	10^10	128 дней	1 терабайт
	10^12	35 лет	111 терабайт
	10^14	3500 лет	11111 терабайт

Посмотрим, что это будут за величины при l=10 для различных значений k (табл. 4.1). Предполагается, что 1000 вершин-последователей могут быть получены за 1 с, и что одна вершина требует 100 байт памяти. Эти значения соответствуют средним затратам времени и памяти, требуемым для решения многих иллюстративных задач типа головоломок. Из табл. 4.1 можно сделать два важных вывода. Во-первых, рост требований к памяти для решения задач поиском в ширину гораздо более серьезная проблема, чем рост требований времени решения тех же задач.

Так, например, вполне приемлемо подождать решения задачи в течение 18 мин при l = 6, но необходимость наличия 111 Мбайт памяти для решения таких сравнительно простых задач кажется слишком высокой ценой.

Во-вторых, для задач, в которых l > 10, помимо катастрофического увеличения требований к памяти, наблюдается стремительный рост временных затрат, не позволяющий решать реальные задачи с помощью поиска в ширину даже на современных мощных компьютерах. Это приводит к следующему заключению: Стратегии поиска, еющие экспоненциальные оценки сложности решения задач по времени и памяти, в частности стратегия поиска в ширину, нельзя использовать i решения задач большой размерности, т.е. задач, у которых 1 > 10.

Дата добавления: 2014-12-27