Противоположностью поиска в глубину, является поиск в ширину, или полный перебор. В соответствии с этим методом вначале обходятся все вершины, находящиеся на одном и том же уровне, а лишь затем выполняется переход на следующий, более низкий уровень. Вот как используется этот метод при поиске цели С:
Страница №6 |
Чтобы программа поиска маршрута выполняла поиск в ширину, необходимо изменить лишь подпрограмму 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.
Страница №7 |
В этом примере поиск в ширину находит первое решение без возврата. Более того, оказывается, что это решение еще и оптимальное. В действительности первые три решения, которые могли бы быть найдены, как раз и являлись бы самыми лучшими маршрутами. Однако этот результат нельзя обобщить на другие случаи, потому что сгенерированный путь зависит от физической организации хранения информации в компьютере. Зато этот пример хорошо показывает радикальное отличие двух методов поиска: в глубину и в ширину.
Недостатки поиска в ширину становятся очевидными, когда цель находится на глубине нескольких слоев. В таком случае для поиска цели приходится затрачивать значительные усилия. В общем, выбирая один из двух методов поиска, в глубину или в ширину, Приходится делать обоснованные догадки о том, где вероятнее всего находится цель.