Противоположностью поиска в глубину, является поиск в ширину, или полный перебор. В соответствии с этим методом вначале обходятся все вершины, находящиеся на одном и том же уровне, а лишь затем выполняется переход на следующий, более низкий уровень. Вот как используется этот метод при поиске цели С:
Чтобы программа поиска маршрута выполняла поиск в ширину, необходимо изменить лишь подпрограмму isflight():
void isflight(char *from, char *to)
{
int d, dist;
char anywhere[20];
while(dist=find(from, anywhere)) {
/* модификация: поиск в ширину */
if(d=match(anywhere, to)) {
push(from, to, dist);
push(anywhere, to, d);
return;
}
}
/* проверить любой авиарейс */
if(dist=find(from, anywhere)) {
push(from, to, dist);
isflight(anywhere, to);
}
else if(tos>0) {
pop(from, to, &dist);
isflight(from, to);
}
}
Как можно видеть, изменено только первое условие. Теперь проверяются все города, в которые можно попасть авиарейсом из пункта вылета, но из которых нет авиарейса в пункт прибытия.
Если этой версией isflight() заменить в программе предыдущую реализацию данной функции, то получится следующее решение:
Нью-Йорк - Торонто - Лос-Анджелес
Расстояние в милях равно 2600.
Это решение является оптимальным. Путь к решению, найденный с помощью поиска в ширину, показан на рис. 25.6.
Анализ поика в ширину
В этом примере поиск в ширину находит первое решение без возврата. Более того, оказывается, что это решение еще и оптимальное. В действительности первые три решения, которые могли бы быть найдены, как раз и являлись бы самыми лучшими маршрутами. Однако этот результат нельзя обобщить на другие случаи, потому что сгенерированный путь зависит от физической организации хранения информации в компьютере. Зато этот пример хорошо показывает радикальное отличие двух методов поиска: в глубину и в ширину.
Недостатки поиска в ширину становятся очевидными, когда цель находится на глубине нескольких слоев. В таком случае для поиска цели приходится затрачивать значительные усилия. В общем, выбирая один из двух методов поиска, в глубину или в ширину, Приходится делать обоснованные догадки о том, где вероятнее всего находится цель.