Функциональное программирование




Поиск на лиспе. Функционалы. Свойства символов - часть 3


Если состояние безопасно, оно будет возвращено без изменений.

(defun safe (state)
(cond ((and (equal (goat-side state) (wolf-side state))
(not (equal (farmer-side state) (wolf-side state)))) nil)
((and (equal (goat-side state) (cabbage-side state))
(not (equal (farmer-side state) (goat-side state)))) nil)
(t state)))

(defun path (state goal)
(cond ((equal state goal))
(t (or (path (farmer-takes-self state) goal)))
(path (farmer-take-wolf state) goal)
(path (farmer-take-goat state) goal)
(path (farmer-take-cabbage state) goal))

Эта версия функции path является простым переводом и содержит несколько ошибок, которые надо исправить. В частности, отметим использование формы OR для управления выполнением ее аргументов.

Напомним,что OR выполняет свои аргументы до тех пор, пока один из них не вернет не-nil величину. Когда это случается, OR завершается без выполнения других аргументов и возвращает это не-nil, как результат.

Таким образом, OR используется не только как логический оператор, но также обеспечивает способ управления поиском пути. OR используется здесь вместо cond, потому что величина, которая тестируется, и величина, которая возвращается в случае не-nil, одна и та же.

Одна проблема с этим определением заключается в том,что функция перемещения может вернуть значение nil, если перемещение не может быть сделано, когда оно ведет не к безопасному состоянию, чтобы предотвратить

path от попытки генерировать дочерние состояния от состояния

nil, она ( path), должна сначала проверять, является ли текущее состояние nil, если да, то path должна вернуть nil.

Другая проблема,которая возникает в реализации path, заключается в возможности возникновения петель в пространстве состояний. Если данную реализацию path запустить, фермер будет ездить взад-вперед между двумя берегами бесконечно, то есть алгоритм приведет к бесконечным переходам между двумя одинаковыми состояниями.

Чтобы предотвратить это, в path надо ввести третий параметр, been-list, список всех состояний, которые уже были достигнуты.




Содержание  Назад  Вперед