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

Листинг 2.16. 
GenericSearch.java (продолжение)
public static class 
Node 
implements 
Comparable> {
final 
T state;
Node parent;
double 
cost;
double 
heuristic;
// для dfs и bfs мы не будем использовать свойства cost и heuristic
Node(T state, Node parent) {
this
.state = state;
this
.parent = parent;
}

---

64
Глава 2.
Задачи поиска
// для astar мы будем использовать свойства cost и heuristic
Node(T state, Node parent, 
double 
cost, 
double 
heuristic) {
this
.state = state;
this
.parent = parent;
this
.cost = cost;
this
.heuristic = heuristic;
}
@Override
public int 
compareTo(Node other) {
Double mine = cost + heuristic;
Double theirs = other.cost + other.heuristic;
return 
mine.compareTo(theirs);
}
}
СОВЕТ
В.данном.случае.compareTo().вызывает.compareTo().для.другого.типа..Это.обычная.
закономерность.
ПРИМЕЧАНИЕ
Если.объект.Node.не.имеет.свойства.parent,.в.качестве.указателя.будем.использовать.
null.
В.процессе.поиска.в.глубину.нужно.отслеживать.две.структуры.данных:.стек.
рассматриваемых.состояний.(мест),.который.мы.назовем.
frontier
,.и.набор.уже.
просмотренных.состояний.—.
explored
..До.тех.пор,.пока.в.
frontier
.остаются.
состояния,.DFS.будет.продолжать.проверять,.являются.ли.они.целью.поиска.
(найдя.искомое.состояние,.DFS.остановит.поиск.и.возвратит.его),.и.добавлять.
их.наследников.в.
frontier
..Также.алгоритм.будет.помечать.все.просмотренные.
состояния.как.
explored
,.чтобы.поиск.не.ходил.по.кругу.и.уже.изученные.состо-
яния.не.становились.наследниками..Если.
frontier
.окажется.пустым,.это.будет.
означать,.что.объектов.для.поиска.не.осталось.(листинг.2.17).