Форвард-цепочка под первым поиском в Лиспе - PullRequest
Новая
       62

Форвард-цепочка под первым поиском в Лиспе

0 голосов
/ 01 января 2019

Я пытаюсь найти проблему при поиске проблемы стека над потоком, алогритм ясен, но рекурсивный вызов сделан в условии if, поэтому я не могу понять, почему все идет плохо 

(defparameter BF '(B C) )
(defparameter BR '((R1(B D E) F )(R2( D G) A )(R3(C F) A )(R4(C) D)
                     (R5(D ) E )(R6(A) H ) (R7(B ) X) (R8(X C) A ) ))
(defun chain_av (BF BR F)
(loop 
    (unless (member F BF)
      (dolist (R  BR)
        (when (actionable  R BF)
          (remove R BR)
          (append BF (conclusion-part R)))
      (if (member F BF) (return "yes")
        (or(chain_av BF BR F) (return nil)))))))


(defun conclusion-part( r)
(caddr r)
)
(write (chain_av BF BR 'H ))
    (defun actionable (r facts)
        (let ((ok t))
            (dolist (p (cadr r) ok)
                (if (not (member p facts))
                    (setq ok nil)))
                ok))

и я до сих пор не уверен, действительно ли это ниже первого поиска, и должен доказать это, имея переменную, которая отслеживает элементы, которые были когда-либо, и спасибо заранее

1 Ответ

0 голосов
/ 02 января 2019

Вот несколько общих замечаний о некоторых ошибках в вашем коде, а также советы о том, как реализовать прямую цепочку.

Форматирование кода

Важно правильно отформатировать код, иначе выили ваши коллеги не смогут легко прочитать его обратно.См., Например, https://lisp -lang.org / style-guide / : 

(defun conclusion-part( r)
(caddr r)
)

Выше приведены скобки в своих строках, что не очень идиоматично.Кроме того, в Common Lisp есть функция с именем THIRD, которую легче понять, чем CADDR для большинства людей.Сделайте отступ правильно и поставьте скобки в конце.Используйте редактор, такой как Emacs, который может автоматически создавать отступы для кода: это помогает идентифицировать случаи, когда то, что вы пишете, отличается от того, что вы намеревались написать, потому что автоиндентирование следует структуре списка и может помочь обнаружить неуместные скобки. 

(defun conclusion-part (rule)
  (third rule))

Функции доступа

То, что вы сделали хорошо, - это определение функции доступа conclusion-part для доступа к части вашей правила специальной структуры данных.Наличие определенного набора методов доступа, которые не привязаны к конкретной реализации, помогает и дает хорошую возможность для введения значимых имен.Вы должны сделать то же самое для всех частей правила (вы используете CADR непосредственно в другом месте, которое не так чисто).

Например (не стесняйтесь, чтобы найти лучшие имена): 

(defun rule-name (rule) (first rule))
(defun rule-antecedent (rule) (second rule))
(defun rule-consequent (rule) (cddr rule))

Обратите внимание, что rule-consequent - это мое переписывание conclusion-part, за исключением того, что оно всегда возвращает список с одним элементом (понимаете почему?).Это полезно позже, когда вы вызываете append, и это согласуется с rule-antecedent, который возвращает список.

Функциональность правил

Функции, которые возвращают либо true, либо false, называются предикатами ипо соглашению с -p в Лиспе (и -? на Схеме).Вы можете или не можете следовать этому правилу, но, пожалуйста, введите более значимые имена переменных.Вот как вы могли бы переписать это: 

(defun actionablep (rule facts)
  (dolist (term (rule-antecedent rule) t)
    (unless (member term facts)
      (return nil))))

Поскольку вы уже знаете loop, вы также можете написать: 

(defun actionablep (rule facts)
  (loop
    :for term :in (rule-antecedent rule)
    :always (member term facts)))

Прямая цепочка

Есть некоторыепроблемы здесь тоже:

  • вы не используете возвращаемое значение REMOVE или APPEND, которые являются гарантированными функциямичтобы не изменять их аргументы (в отличие от DELETE и NCONC, и даже для этих функций имеет значение только возвращаемое значение, возможность, которая предоставляется для изменения существующего хранилища, определяется реализацией и предназначена только для эффективного повторного использования памяти).

  • В какую-то ветку вы хотите вернуть "yes", в другую nil;CL может быть динамически типизирован, но здесь нет необходимости возвращать строковое значение.

  • A return форма существует только в самом внутреннем блоке nil.В вашем случае это означает, что вы возвращаетесь из неявного блока, установленного DOLIST, а не из LOOP.Вы могли бы назвать свой loop, но это на самом деле не обязательно здесь, вы можете написать все это без return.В более общем смысле вы можете использовать чисто функциональный подход.

Подсказка

Я написал forward-chaining функцию и отследил ее;в REPL: 

CL-USER> (trace forward-chaining)

Вот как я тестировал свою реализацию: 

(forward-chaining '(B C)
                  '((R1 (B D E) F)
                    (R2 (D G) A)
                    (R3 (C F) A)
                    (R4 (C) D)
                    (R5 (D) E)
                    (R6 (A) H)
                    (R7 (B) X)
                    (R8 (X C) A))
                  'H)

Я тестирую код с SBCL, фактический вывод может отличаться в вашей реализации на Лиспе: 

  0: (FORWARD-CHAINING (B C) ((R1 (B D E) F) (R2 (D G) A) (R3 (C F) A) (R4 (C) D) (R5 (D) E) (R6 (A) H) (R7 (B) X) (R8 (X C) A)) H)
    1: (FORWARD-CHAINING (B C D) ((R1 (B D E) F) (R2 (D G) A) (R3 (C F) A) (R5 (D) E) (R6 (A) H) (R7 (B) X) (R8 (X C) A)) H)
      2: (FORWARD-CHAINING (B C D E) ((R1 (B D E) F) (R2 (D G) A) (R3 (C F) A) (R6 (A) H) (R7 (B) X) (R8 (X C) A)) H)
        3: (FORWARD-CHAINING (B C D E F) ((R2 (D G) A) (R3 (C F) A) (R6 (A) H) (R7 (B) X) (R8 (X C) A)) H)
          4: (FORWARD-CHAINING (B C D E F A) ((R2 (D G) A) (R6 (A) H) (R7 (B) X) (R8 (X C) A)) H)
            5: (FORWARD-CHAINING (B C D E F A H) ((R2 (D G) A) (R7 (B) X) (R8 (X C) A)) H)
            5: FORWARD-CHAINING returned (H)
          4: FORWARD-CHAINING returned (H)
        3: FORWARD-CHAINING returned (H)
      2: FORWARD-CHAINING returned (H)
    1: FORWARD-CHAINING returned (H)
  0: FORWARD-CHAINING returned (H)

Основная структура программы: 

(defun forward-chaining (rules facts goal)
  (or ...
      (loop 
        for ... in ...
        thereis (and (actionablep ... ...)
                     (forward-chaining ... ... ...)))))

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

Порядок, в котором вы посещаете правила, определяет, является ли ваша стратегия первой в глубине (всегда следуйте последнему пробованному правилу и переходите от него, используя список правил в качестве стека), или в ширину (применяйте все активируемые правиладля данного факта, используя список правил в качестве очереди).Я не знаю, откуда взялся термин "под" первым поиском, я не нашел серьезных ссылок на него (есть одна статья, в которой упоминается Leiserson & Schardl 2010 , когда речь идет о под первый поиск, но ссылка на статью не упоминает об этом, только в ширину , что хорошо известно).

...