4.3.1 · Явные альтернативы

Недетерминированный поиск и множество успехов

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

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

Как меняется вычисление, если после одного успеха сохраняются оставшиеся альтернативы?

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

Первый поиск получает цитированные деревья выражений. evaluate интерпретирует по одному дереву за раз, в то время как search применяет acceptable? к полученному значению и продолжает просмотр как после неудачи, так и после успеха. Никакая преждевременная фиксация не отбрасывает оставшиеся альтернативы.

Вторая программа делает явными две позиции выбора. scan-y проверяет каждый y для одного x, а scan-x повторяет эту работу для каждого x. Возврат всех пар, сумма квадратов компонентов которых равна 25, раскрывает конечный недетерминированный поиск как обычное управление, создающее списки.

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

(begin
  (define (evaluate expression)
    (if (number? expression)
        expression
        (let ((operator (car expression))
              (left (evaluate (cadr expression)))
              (right (evaluate (caddr expression))))
          (cond ((eq? operator '+) (+ left right))
                ((eq? operator '*) (* left right))))))
  (define (search alternatives acceptable?)
    (if (null? alternatives)
        '()
        (let ((value (evaluate (car alternatives))))
          (if (acceptable? value)
              (cons value (search (cdr alternatives) acceptable?))
              (search (cdr alternatives) acceptable?)))))
  (search '((+ 1 2) (* 2 3) (+ 4 5) (* 4 4)) odd?))

Примеры

Результат—

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

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

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

Первая программа возвращает (3 9). Вторая программа возвращает ((3 4) (4 3)).

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

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

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

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

Измените первый предикат на even? и предскажите каждое сохраненное значение в исходном порядке альтернатив.

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

Сначала вычислите все четыре дерева выражений. Успешное значение не останавливает просмотр.

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

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