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

new 
PriorityQueue<>();
frontier.offer(
new 
Node<>(initial, 
null
, 0.0,
heuristic.applyAsDouble(initial)));
// explored — то, что мы уже просмотрели
Map explored = 
new 
HashMap<>();
explored.put(initial, 0.0);
// продолжаем, пока есть что просматривать
while 
(!frontier.isEmpty()) {
Node currentNode = frontier.poll();
T currentState = currentNode.state;
// если цель найдена, мы закончили
if 
(goalTest.test(currentState)) {
return 
currentNode;
}
// проверяем, в какую из неисследованных ячеек направиться
for 
(T child : successors.apply(currentState)) {

---

2.2. Прохождение лабиринта
75
// 1 — для сетки, для более сложных приложений
// здесь должна быть функция затрат
double 
newCost = currentNode.cost + 1;
if 
(!explored.containsKey(child) || explored.get(child) > newCost) {
explored.put(child, newCost);
frontier.offer(
new 
Node<>(child, currentNode, newCost,
heuristic.applyAsDouble(child)));
}
}
}
return null
; // все проверили, пути к целевой точке не нашли
}
Поздравляю!.Если.вы.завершили.этот.путь,.то.узнали.не.только.о.том,.как.пройти.
по.лабиринту,.но.и.о.некоторых.общих.функциях.поиска,.которые.сможете.приме-
нять.во.всевозможных.поисковых.приложениях..Алгоритмы.DFS.и.BFS.подходят.
для.множества.небольших.наборов.данных.и.пространств.состояний,.где.произ-
водительность.не.очень.важна..В.некоторых.ситуациях.DFS.превосходит.BFS,.
но.преимущество.BFS.заключается.в.том,.что.этот.алгоритм.всегда.гарантирует.
оптимальный.путь..Интересно,.что.у.BFS.и.DFS.почти.идентичные.реализации,.
различающиеся.только.применением.очереди.вместо.стека.в.качестве.области.
поиска..Чуть.более.сложный.поиск.A*.в.сочетании.с.хорошей.последовательной.
допустимой.эвристикой.не.только.обеспечивает.оптимальный.путь,.но.и.намного.
превосходит.BFS.по.производительности..А.поскольку.все.три.функции.были.
реализованы.в.параметризованном.виде,.их.можно.использовать.практически.
в.любом.пространстве.поиска.
Вперед.—.попробуйте.применить.
astar()
.к.тому.же.лабиринту,.что.был.задей-
ствован.в.разделе.тестирования.в.файле.
Maze.java
.(листинг.2.26).