4.3.3 · 비결정적 프로그램 예제

퍼즐은 선택과 제약을 말하고 실패는 다음 선택을 재개한다.

명시적인 성공·실패 continuation으로 multiple-dwelling 퍼즐을 풀고 문제마다 별도 중첩 루프를 쓰지 않고 유한 피타고라스 삼쌍을 열거합니다.

생각해 볼 질문

프로그램은 올바른 답을 설명하고 continuation 프로토콜은 대안 순서와 backtracking을 소유하도록 어떻게 나눌 수 있을까요?

남은 대안을 실패 continuation에 보존하면서 값 하나 고르기
현재 실패 continuation을 호출해 부분·완전 배정 거부하기
열거 제어와 별개로 서로 다름과 인접 제약 표현하기
성공 뒤 재개하여 유한한 모든 해 수집하기
같은 choose 프로토콜을 수치 탐색 문제에 재사용하기
유한 깊이 우선 열거와 공정한 무한 탐색 구분하기

choose는 첫 선택지를 succeed에 넘기고 남은 선택지를 next-failure로 묶습니다. 따라서 중첩된 층 선택마다 가장 가까운 미시도 대안으로 정확히 돌아갈 continuation이 있습니다. 다섯 층을 모두 고르면 제약 술어가 해 하나를 보고하거나 현재 continuation을 호출합니다. search에는 퍼즐 사실이 있고 choose와 해 수집에는 탐색 프로토콜이 있습니다.

피타고라스 프로그램은 숫자 선택에 같은 continuation을 재사용합니다. 순서 제약이 순열을 없애고 제곱 등식이 1부터 10까지에서 두 삼쌍을 받아들입니다. 두 예제는 유한 리스트를 깊이 우선으로 탐색하고 선택한 범위에서 도달한 모든 선택을 기록합니다.

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

(begin
  (define (choose options succeed fail)
    (if (null? options)
        (fail)
        (succeed
          (car options)
          (lambda ()
            (choose (cdr options) succeed fail)))))
  (define (distinct? values)
    (cond ((null? values) #t)
          ((member (car values) (cdr values)) #f)
          (else (distinct? (cdr values)))))
  (define (absolute value)
    (if (< value 0) (- value) value))
  (define floors '(1 2 3 4 5))
  (define (search succeed fail)
    (choose floors
      (lambda (baker fail-baker)
        (choose floors
          (lambda (cooper fail-cooper)
            (choose floors
              (lambda (fletcher fail-fletcher)
                (choose floors
                  (lambda (miller fail-miller)
                    (choose floors
                      (lambda (smith fail-smith)
                        (if
                          (and
                            (distinct?
                              (list baker cooper fletcher miller smith))
                            (not (= baker 5))
                            (not (= cooper 1))
                            (not (= fletcher 5))
                            (not (= fletcher 1))
                            (> miller cooper)
                            (not (= (absolute (- smith fletcher)) 1))
                            (not (= (absolute (- fletcher cooper)) 1)))
                          (succeed
                            (list (list 'baker baker)
                                  (list 'cooper cooper)
                                  (list 'fletcher fletcher)
                                  (list 'miller miller)
                                  (list 'smith smith))
                            fail-smith)
                          (fail-smith)))
                      fail-miller))
                  fail-fletcher))
              fail-cooper))
          fail-baker))
      fail))
  (define solutions '())
  (search
    (lambda (solution next-alternative)
      (set! solutions (append solutions (list solution)))
      (next-alternative))
    (lambda () solutions)))

(begin
  (define (choose options succeed fail)
    (if (null? options)
        (fail)
        (succeed
          (car options)
          (lambda ()
            (choose (cdr options) succeed fail)))))
  (define (distinct? values)
    (cond ((null? values) #t)
          ((member (car values) (cdr values)) #f)
          (else (distinct? (cdr values)))))
  (define (absolute value)
    (if (< value 0) (- value) value))
  (define floors '(1 2 3 4 5))
  (define (search succeed fail)
    (choose floors
      (lambda (baker fail-baker)
        (choose floors
          (lambda (cooper fail-cooper)
            (choose floors
              (lambda (fletcher fail-fletcher)
                (choose floors
                  (lambda (miller fail-miller)
                    (choose floors
                      (lambda (smith fail-smith)
                        (if
                          (and
                            (distinct?
                              (list baker cooper fletcher miller smith))
                            (not (= baker 5))
                            (not (= cooper 1))
                            (not (= fletcher 5))
                            (not (= fletcher 1))
                            (> miller cooper)
                            (not (= (absolute (- smith fletcher)) 1))
                            (not (= (absolute (- fletcher cooper)) 1)))
                          (succeed
                            (list (list 'baker baker)
                                  (list 'cooper cooper)
                                  (list 'fletcher fletcher)
                                  (list 'miller miller)
                                  (list 'smith smith))
                            fail-smith)
                          (fail-smith)))
                      fail-miller))
                  fail-fletcher))
              fail-cooper))
          fail-baker))
      fail))
  (define solutions '())
  (search
    (lambda (solution next-alternative)
      (set! solutions (append solutions (list solution)))
      (next-alternative))
    (lambda () solutions)))

예제

결과—

출력: —
값: —
진단: —

실행 추적0 / 0 개 이벤트

예상 결과

층 퍼즐은 (((baker 3) (cooper 2) (fletcher 4) (miller 5) (smith 1)))을 반환합니다. 수치 탐색은 ((3 4 5) (6 8 10))을 반환합니다.

실행 추적에서 볼 점

choose 호출 하나에서 next-failure 클로저까지 따라가고 현재 완전 배정을 거부한 제약이 가장 가까운 대안을 재개하는 지점을 찾으세요. 성공에서는 해를 기록하는 일과 열거를 계속하도록 next-alternative를 부르는 일을 구분하세요. 기호 층 배정과 수치 삼쌍에서 같은 프로토콜을 비교하세요.

직접 해보기

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

같은 choose를 사용해 yacht 퍼즐이나 네 변수 합 퍼즐을 추가하세요. 안전한 제약을 더 일찍 옮기기 전과 뒤에 최종 제약까지 도달한 완전 후보 수를 기록하세요.

힌트 보기

필요한 값이 모두 알려지는 즉시 제약은 현재 실패 continuation을 호출할 수 있습니다. 더 이른 거부는 답 집합이 아니라 작업량을 바꿉니다.

이 수업 완료하기

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