4.4.5 · 재귀 규칙 탐색

재귀 규칙에는 보이는 탐색 경계가 필요하다.

유한한 ancestor 질의는 parent 사실을 재귀적으로 펼칠 수 있지만 명시적인 작업 예산이 탐색을 끝냈는지 중간에 멈췄는지 함께 보고해야 합니다.

생각해 볼 질문

데이터에 순환이 있어도 재귀 규칙 확장을 정직하게 끝내려면 무엇이 필요할까요?

직접 parent 절과 재귀 ancestor 절 구분하기
대기 중인 대상을 frontier로 명시하기
frontier 항목 하나를 펼칠 때 작업 단위 하나 사용하기
완료된 결과와 한도에서 잘린 결과 구분하기
중복 제거 없는 순환 탐색에서 반복 답 관찰하기

첫 번째 프로그램은 ancestor에 두 절을 프로시저 형태로 부여합니다. 현재 사람의 모든 child는 직접적인 답이 되며, 같은 규칙이 한 세대 더 멀리 탐색할 수 있도록 모든 child를 frontier에도 넣습니다. 사실이 유한하고 비순환적이므로 10단위 작업 예산이 소진되기 전에 frontier가 비어 결과는 complete로 표시됩니다.

두 번째 프로그램은 세 사람으로 이루어진 순환을 사용합니다. ada를 펼치면 ben에 닿고, ben은 cy에 닿으며, cy는 다시 ada에 닿습니다. 평가기는 제거된 frontier 항목마다 정확히 하나의 작업 단위를 사용하며 예산이 0에 도달하면 남은 frontier와 함께 truncated를 반환합니다. 이 너비 우선 수업 모델은 parent 확장과 명시적인 frontier와 반복되는 답과 complete 또는 truncated 상태를 다룹니다.

SICP 코드UTF-8 1,284 / 1,048,576바이트

(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)을 반환합니다.

실행 추적에서 볼 점

각 frontier car와 그 children을 생성하는 유한한 사실 스캔, 그 children을 큐에 넣는 append, 1단위 예산 감소를 따라가세요. complete 실행에서는 4단위가 남은 상태로 frontier가 빕니다. 순환 실행에서는 예산이 0에 도달하기 전에 ada가 다시 나타나고 결과가 truncated로 표시될 때 cy가 대기 상태로 남습니다.

직접 해보기

프로그램을 수정하고 결과를 비교해 보세요.

작업 한도를 2로 설정하여 비순환 탐색을 실행하세요. 실행하기 전에 답 접두사와 남은 frontier와 상태를 예상하세요.

힌트 보기

첫 번째 확장은 ben과 eli를 큐에 넣습니다. 두 번째 확장은 ben을 꺼내고 eli 뒤에 cy를 큐에 넣습니다.

이 수업 완료하기

이 장의 총 23개 수업 중 0개 완료0%