4.4.5 · Поиск по рекурсивным правилам

Рекурсивные правила и видимая граница поиска

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

Вопрос для размышления

Как рекурсивное раскрытие правил может корректно завершаться, если данные могут содержать цикл?

Разделение прямого предложения parent и рекурсивного предложения ancestor
Перенос видимой границы ожидающих субъектов через поиск
Использование одной явной единицы работы для каждого раскрытия границы
Отличие полного результата от результата, усеченного по границе
Наблюдение повторяющихся ответов при поиске по циклическим данным без удаления дубликатов

Первая программа задает для ancestor два предложения в процедурной форме. Каждый child текущего человека является прямым ответом, и каждый child также помещается в frontier, чтобы то же правило могло искать на одно поколение дальше. Поскольку факты конечны и ацикличны, frontier становится пустым до исчерпания бюджета работы в десять единиц, а результат помечается как complete.

Вторая программа использует цикл из трех человек. Раскрытие ada достигает ben, ben достигает cy, а cy снова достигает ada. Вычислитель тратит ровно одну единицу работы на каждый извлеченный элемент frontier и возвращает truncated с оставшимся frontier, когда бюджет достигает нуля. Эта модель урока для поиска в ширину охватывает раскрытие parent, явный frontier, повторяющиеся ответы и статус complete или truncated.

Код SICP1,284 из 1,048,576 байт UTF-8

(begin
  ; ancestor(from, to) <- parent(from, to)
  ; ancestor(from, to) <- parent(from, middle), ancestor(middle, to)
  (define facts
    '((parent ada ben)
      (parent ada eli)
      (parent ben cy)
      (parent cy dia)
      (parent eli fox)))
  (define (children-of person remaining answers)
    (if (null? remaining)
        (reverse answers)
        (let ((fact (car remaining)))
          (children-of
            person
            (cdr remaining)
            (if (and (eq? (car fact) 'parent)
                     (eq? (cadr fact) person))
                (cons (caddr fact) answers)
                answers)))))
  (define (bounded-ancestor-search start work-limit)
    (define (search frontier remaining-work answers)
      (cond ((null? frontier)
             (list 'complete answers frontier remaining-work))
            ((= remaining-work 0)
             (list 'truncated answers frontier remaining-work))
            (else
             (let* ((person (car frontier))
                    (children (children-of person facts '())))
               (search
                 (append (cdr frontier) children)
                 (- remaining-work 1)
                 (append answers children))))))
    (search (list start) work-limit '()))
  (bounded-ancestor-search 'ada 10))

(begin
  ; ancestor(from, to) <- parent(from, to)
  ; ancestor(from, to) <- parent(from, middle), ancestor(middle, to)
  (define facts
    '((parent ada ben)
      (parent ada eli)
      (parent ben cy)
      (parent cy dia)
      (parent eli fox)))
  (define (children-of person remaining answers)
    (if (null? remaining)
        (reverse answers)
        (let ((fact (car remaining)))
          (children-of
            person
            (cdr remaining)
            (if (and (eq? (car fact) 'parent)
                     (eq? (cadr fact) person))
                (cons (caddr fact) answers)
                answers)))))
  (define (bounded-ancestor-search start work-limit)
    (define (search frontier remaining-work answers)
      (cond ((null? frontier)
             (list 'complete answers frontier remaining-work))
            ((= remaining-work 0)
             (list 'truncated answers frontier remaining-work))
            (else
             (let* ((person (car frontier))
                    (children (children-of person facts '())))
               (search
                 (append (cdr frontier) children)
                 (- remaining-work 1)
                 (append answers children))))))
    (search (list start) work-limit '()))
  (bounded-ancestor-search 'ada 10))

Примеры

Результат—

Вывод: —
Значение: —
Диагностика: —

Трасса выполнения0 / 0 событий

Ожидаемый результат

Ациклический поиск возвращает (complete (ben eli cy fox dia) () 4). Циклический поиск возвращает (truncated (ben cy ada ben cy) (cy) 0).

На что обратить внимание в трассе

Проследите за каждым car в frontier, конечным просмотром фактов, который дает его потомков, операцией append, ставящей этих потомков в очередь, и уменьшением бюджета на одну единицу. В запуске со статусом complete frontier опустошается при четырех оставшихся единицах. В циклическом запуске ada появляется снова до того, как бюджет достигает нуля, а cy остается в ожидании, когда результат помечается как truncated.

Попробуйте сами

Измените программу и сравните результат.

Запустите ациклический поиск с ограничением работы в 2 единицы. Перед выполнением предскажите префикс ответа, оставшийся frontier и статус.

Показать подсказку

Первое раскрытие ставит в очередь ben и eli. Второе раскрытие удаляет ben и ставит cy в очередь за eli.

Завершить этот урок

В этой главе пройдено 0 из 23 урока0%