?Жадный алгоритм поиска? использует списки сохраненных состояний: список open отслеживает текущее состояние поиска, а в closed записываются уже проверенные состояния. На каждом шаге в список open записываются состояния с учетом эвристической оценки его ?близости к цели?, т.е. на каждом шаге рассматриваются наиболее перспективные состояния из списка open. Алгоритм:
Function Best;
Begin
Open:= [Start];
Closed:=[];
While open <> [] do `оставшиеся состояния
Begin
Удалить первое состояние Х из списка open;
If X=goal/ return путь от Start к X
Else
Begin
Сгенерировать потомок Х;
For каждого потомка Х do
Case
Потомок не содержится в списке open или closed;
Begin
Присвоить потомку эвристическое значение;
Добавить потомок в список open
End;
Потомок уже содержится в списке open:
If потомок был достигнут по кратчайшему пути
Then записать это состояние в список open
Потомок уже содержится в списке closed:
If потомок был достигнут по кратчайшему пути then
Begin
Удалить состояние и списка closed;
Добавить потомок в список open
End;
End; `конец case
Поместить Х в список closed;
Переупорядочить состояния в списке open
В соответствии с эвристикой (лучший слева)
End;
Return FAIL ` список OPEN пуст
End.
На каждой итерации функция Best удаляет первый элемент из списка open. Достигнув цели, алгоритм возвращает путь, который ведет к решению.
Но мне непонятно, если мы задаем список городов, то где задавать эвристические оценки. И вообще как этот алгоритм реализовать на Lisp (может использовать рекурсию, но я все равно не в силах это сделать). Помогите пожалуйста!!!!!!!