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

74
Глава 2.
Задачи поиска
будут.оптимальными,.поскольку.манхэттенское.расстояние.допустимо.(никогда.
не.превышает.реальное.расстояние).для.лабиринтов,.в.которых.разрешены.только.
четыре.направления.движения.
Алгоритм А*
Чтобы.перейти.от.поиска.BFS.к.поиску.A*,.нужно.внести.в.код.пару.незна-
чительных.изменений..Прежде.всего.изменить.область.поиска.с.очереди.на.
очередь.с.приоритетом..Таким.образом,.в.области.поиска.появятся.узлы.с.наи-
меньшим.
f 
(
n
)..Затем.нужно.заменить.исследуемый.набор.на.
HashMap
..
HashMap
.
позволит.отслеживать.наименьшие.затраты.
g 
(
n
).для.каждого.узла,.который.
мы.можем.посетить..Теперь,.когда.используется.эвристическая.функция,.мо-
жет.оказаться,.что.некоторые.узлы.будут.проверены.дважды,.если.эвристика.
окажется.несовместимой..Если.узел,.найденный.в.новом.направлении,.требует.
меньших.затрат,.чем.тогда,.когда.мы.его.посетили.в.прошлый.раз,.то.мы.пред-
почтем.новый.маршрут.
Для.простоты.функция.
astar()
.не.принимает.в.качестве.параметра.функцию.
вычисления.затрат..Вместо.этого.мы.считаем,.что.затраты.для.каждого.шага.
в.лабиринте.равны.1..Каждому.новому.узлу.назначаются.затраты,.основанные.
на.этой.простой.формуле,.а.также.эвристический.показатель,.вычисленный.
с.использованием.новой.функции.
heuristic()
,.передаваемой.функции.поис-
ка.в..качестве.параметра..За.исключением.этих.изменений,.функция.
astar()
.
очень.похожа.на.
bfs()
.(листинг.2.25)..Откройте.их.в.соседних.окнах.для.
сравнения.
Листинг 2.25. 
GenericSearch.java
public static 
Node astar(T initial, Predicate goalTest, 
Function> successors, ToDoubleFunction heuristic) {
// frontier — то, куда мы хотим двигаться
PriorityQueue> frontier =