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

Листинг 2.26. 
Maze.java (продолжение)
public static void 
main(String[] args) {
Maze m = 
new 
Maze();
System.
out
.println(m);
Node solution1 = GenericSearch.
dfs
(m.start,
m::goalTest, m::successors);
if 
(solution1 == 
null
) {
System.
out
.println("No solution found using depth-first search!");
} 
else 
{
List path1 = GenericSearch.
nodeToPath
(solution1);
m.mark(path1);
System.
out
.println(m);
m.clear(path1);
}
Node solution2 = GenericSearch.
bfs
(m.start,
m::goalTest, m::successors);

---

76
Глава 2.
Задачи поиска
if 
(solution2 == 
null
) {
System.
out
.println("No solution found using breadth-first search!");
} 
else 
{
List path2 = GenericSearch.
nodeToPath
(solution2);
m.mark(path2);
System.
out
.println(m);
m.clear(path2);
}
Node solution3 = GenericSearch.
astar
(m.start,
m::goalTest, m::successors, m::manhattanDistance);
if 
(solution3 == 
null
) {
System.
out
.println("No solution found using A*!");
} 
else 
{
List path3 = GenericSearch.
nodeToPath
(solution3);
m.mark(path3);
System.
out
.println(m);
m.clear(path3);
}
}
Интересно,.что.результат.немного.отличается.от.
bfs()
,.несмотря.на.то.что.и.
bfs()
,.
и.
astar()
.находят.оптимальные.(равные.по.длине).пути..Из-за.своей.эвристики.
astar()
.сразу.проходит.по.диагонали.к.цели..В.итоге.этот.алгоритм.проверяет.
меньше.состояний,.чем.
bfs()
,.что.обеспечивает.более.высокую.производитель-
ность..Если.хотите.в.этом.убедиться,.добавьте.счетчик.состояний.для.каждого.
алгоритма:
S** X X
X**
* X
XX* X
X*
X**X
X ****
*
X * X
**G
2.3. МИССИОНЕРЫ И ЛЮДОЕДЫ
Три.миссионера.и.три.людоеда.находятся.на.западном.берегу.реки..У.них.есть.
лодка,.в.которой.помещаются.два.человека,.и.все.они.должны.переехать.на.вос-
точный.берег.реки..Нельзя,.чтобы.на.любой.стороне.реки.в.какой-то.момент.
оказалось.больше.людоедов,.чем.миссионеров,.иначе.каннибалы.съедят.миссио-
неров..Кроме.того,.в.лодке.всегда.должен.находиться.хотя.бы.один.человек,.чтобы.
пересечь.реку..Какая.последовательность.переправ.позволит.успешно.перевезти.
всех.через.реку?.Иллюстрация.задачи.—.на.рис..2.8.

---

2.3. Миссионеры и людоеды
77
Рис. 2.8.
Миссионеры и каннибалы должны использовать свою единственную лодку, 
чтобы переправить всех через реку с западного берега на восточный. Если людоедов 
в какой-то момент окажется больше, чем миссионеров, они их съедят
2.3.1. Представление задачи
Представим.задачу.с.помощью.структуры,.которая.отслеживает.ситуацию.на.
западном.берегу..Сколько.миссионеров.и.людоедов.здесь.находятся?.Причалена.
ли.к.западному.берегу.лодка?.Получив.эти.знания,.мы.можем.выяснить,.кто.на-
ходится.на.восточном.берегу,.потому.что.все,.кто.не.на.западном.берегу,.находятся.
на.восточном.
Прежде.всего.создадим.небольшую.вспомогательную.переменную.для.отслежи-
вания.максимального.количества.миссионеров.или.людоедов..Затем.определим.
основной.класс.(листинг.2.27).