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

if 
(solution1 == 
null
) {
System.
out
.println("No solution found using depth-first search!");
} 
else 
{
List path1 = GenericSearch.
nodeToPath
(solution1);
m.mark(path1);

---

70
Глава 2.
Задачи поиска
System.
out
.println(m);
m.clear(path1);
}
Node solution2 =
GenericSearch.
bfs
(m.start, m::goalTest, m::successors);
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);
}
}
Это.удивительно,.но.мы.можем,.не.меняя.алгоритм,.просто.изменить.структуру.
данных,.к.которой.он.обращается,.и.получить.кардинально.различные.результа-
ты..Далее.показан.результат.вызова.
bfs()
.для.того.же.лабиринта,.для.которого.
ранее.мы.вызывали.
dfs()
..Обратите.внимание.на.то,.что.на.этот.раз.звездочки.
обозначают.более.прямой.путь.к.цели,.чем.в.предыдущем.примере:
S X X
*X
* X
*XX X
* X
* X X
*X
*
* X X
*********G
2.2.5. Поиск по алгоритму A*
Очистка.луковицы.слой.за.слоем,.как.при.поиске.в.ширину,.может.занять.очень.
много.времени..Поиск.по.алгоритму.A*,.подобно.BFS,.стремится.найти.кратчай-
ший.путь.от.начального.к.конечному.состоянию..В.отличие.от.рассмотренной.
ранее.реализации.BFS,.при.поиске.A*.используется.объединение.функции.затрат.
и.эвристической.функции,.что.позволяет.сосредоточить.поиск.на.путях,.которые,.
скорее.всего,.быстро.приведут.к.цели.
Функция.затрат.
g 
(
n
).проверяет.затраты,.необходимые.для.того,.чтобы.добраться.
до.определенного.состояния..В.случае.с.нашим.лабиринтом.это.было.бы.количе-
ство.шагов,.которые.пришлось.бы.пройти,.чтобы.добраться.до.нужного.состояния.
Эвристическая.функция.
h 
(
n
).позволяет.оценить.затраты,.необходимые.для.того,.
чтобы.из.заданного.состояния.достичь.целевого.состояния..Можно.доказать,.что.

---

2.2. Прохождение лабиринта
71
если.
h 
(
n
).—.
допустимая эвристическая функция
,.то.найденный.конечный.путь.
будет.оптимальным..Допустимая.эвристическая.функция.—.это.функция,.которая.
никогда.не.переоценивает.затраты.на.достижение.цели..На.двумерной.плоскости.
пример.такой.эвристической.функции.—.расстояние.по.прямой.линии,.поскольку.
прямая.линия.—.всегда.кратчайший.путь
1
.
Общие.затраты.для.любого.рассматриваемого.состояния.определяются.функ-
цией.
f 
(
n
),.которая.является.простым.объединением.
g 
(
n
).и.
h 
(
n
)..В.сущности,.
f 
(
n
).=.
g 
(
n
).+.
h 
(
n
)..При.выборе.следующего.рассматриваемого.состояния.из.об-
ласти.поиска.алгоритм.A*.выбирает.состояние.с.наименьшим.
f 
(
n
)..Именно.этим.
он.отличается.от.алгоритмов.BFS.и.DFS.