Computer Science на языке Java 2022 Дэвид Копец Классические задачи Computer Science на языке Java 2022 ббк

68
Глава 2.
Задачи поиска
Чтобы.понять,.почему.поиск.в.глубину.иногда.возвращает.результат.быстрее,.
чем.поиск.в.ширину,.представьте.себе,.что.вы.ищете.метку.на.определенном.слое.
луковицы..Тот,.кто.использует.стратегию.поиска.в.глубину,.вонзит.нож.в.центр.лу-
ковицы.и.исследует.случайно.вырезанные.куски..Если.отмеченный.слой.окажется.
рядом.с.вырезанным.куском,.есть.вероятность,.что.он.будет.найден.быстрее,.чем.
с.помощью.стратегии.поиска.в.ширину,.при.которой.нужно.кропотливо.очищать.
луковицу,.снимая.по.одному.слою.за.раз.
Чтобы.получить.более.полное.представление.о.том,.почему.при.поиске.в.ширину.
всегда.определяется.кратчайший.путь,.если.только.он.существует,.попробуйте.
найти.железнодорожный.маршрут.между.Бостоном.и.Нью-Йорком.с.наимень-
шим.количеством.остановок..Если.вы.будете.продолжать.двигаться.в.выбранном.
направлении.и.возвращаться.назад,.когда.попали.в.тупик.(как.при.поиске.в.глу-
бину),.то.можете.сначала.найти.маршрут.до.Сиэтла,.прежде.чем.попасть.обратно.
в.Нью-Йорк..Однако.при.поиске.в.ширину.вы.сначала.проверите.все.станции,.
находящиеся.в.одной.остановке.от.Бостона..Затем.—.все.станции,.находящиеся.
в.двух.остановках.от.Бостона..Затем.—.в.трех.остановках.от.Бостона..Так.будет.
продолжаться.до.тех.пор,.пока.вы.не.доберетесь.до.Нью-Йорка..Поэтому,.найдя.
Нью-Йорк,.поймете,.что.определили.маршрут.с.наименьшим.количеством.стан-
ций,.поскольку.уже.проверили.все.станции,.находящиеся.на.меньшем.расстоянии.
от.Бостона,.и.ни.одна.из.них.не.была.Нью-Йорком.
Очереди
Для.реализации.алгоритма.BFS.нужна.структура.данных,.известная.как.
оче-
редь
..Если.стек.—.это.структура.LIFO,.то.очередь.—.структура.FIFO..Очередь.
встречается.нам.и.в.обычной.жизни.—.например,.цепочка.людей,.ожидающих.
у.входа.в.туалет..Кто.раньше.занял.очередь,.тот.первым.туда.идет..Очередь.как.
минимум.имеет.те.же.методы.
push()
.и.
pop()
,.что.и.стек..В.сущности,.различие.
между.стеком.и.очередью.заключается.в.том,.что.очередь.удаляет.элементы.из.
списка.на.конце,.противоположном.тому,.куда.она.их.вставляет..Это.гаранти-
рует,.что.самые.старые.элементы.(элементы,.«ожидающие».дольше.всех).всегда.
удаляются.первыми.
ПРИМЕЧАНИЕ
Как.ни.странно,.но.в.стандартной.библиотеке.Java.нет.класса.Queue,.однако.есть.класс.
Stack..Вместо.этого.в.Java.есть.интерфейс.Queue,.реализующий.несколько.классов.
стандартной.библиотеки.Java,.включая.LinkedList..Еще.больше.сбивает.с.толку.то,.
что.в.интерфейсе.Queue.стандартной.библиотеки.Java.метод.push().называется.offer(),.
а.метод.pop().—.poll().
Алгоритм BFS
Удивительно,.но.алгоритм.поиска.в.ширину.идентичен.алгоритму.поиска.в.глу-
бину,.только.область.поиска.не.стек,.а.очередь..Такое.изменение.области.поиска.

---

2.2. Прохождение лабиринта
69
меняет.последовательность.просмотра.состояний.и.гарантирует,.что.первыми.
будут.просмотрены.состояния,.ближайшие.к.начальному.(листинг.2.21).