нижнем этаже. Миллер живет выше Купера. Смит живет не на соседнем с Флетчером этаже. Флетчер живет не на соседнем с Купером этаже. Кто где живет?

Можно впрямую определить, кто на каком этаже живет, перечислив все возможности и наложив данные нам ограничения:48

(define (multiple-dwelling) (let ((baker (amb 12 3 4 5)) (cooper (amb 12 3 4 5))

(fletcher (amb 1 2 3 4 5)) (miller (amb 1 2 3 4 5)) (smith (amb 1 2 3 4 5)))

(require

(distinct? (list baker cooper fletcher miller smith))) (require (not (= baker 5))) (require (not (= cooper 1))) (require (not (= fletcher 5))) (require (not (= fletcher 1))) (require (> miller cooper))

(require (not (= (abs (- smith fletcher)) 1))) (require (not (= (abs (- fletcher cooper)) 1))) (list (list baker baker)

(list cooper cooper)

(list fletcher fletcher)

(list miller miller)

(list smith smith))))

Выполнение выражения (multiple-dwelling) дает следующий результат:

((baker 3) (cooper 2) (fletcher 4) (miller 5) (smith 1))

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

Упражнение 4.38.

Измените процедуру multiple-dwelling, отказавшись от требования, что Смит и Флетчер живут не на соседних этажах. Сколько решений имеется у измененной загадки?

Упражнение 4.39.

Влияет ли порядок ограничений в процедуре multiple-dwelling на ответ? Влияет ли он на время, необходимое для поиска ответа? Если Вы считаете, что он имеет значение,

48 В нашей программе используется следующая процедура, определяющая, все ли элементы списка отличны друг от друга:

(define (distinct? items) (cond ((null? items) true)

((null? (cdr items)) true)

((member (car items) (cdr items)) false)

(else (distinct? (cdr items)))))

Процедура member подобна memq, но на равенство проверяет с помощью equal?, а не eq?.

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

Упражнение 4.40.

Сколько возможных соответствий между людьми и этажами имеется в задаче о проживании, если учитывать требование, что все живут на разных этажах, и если его не учитывать? Крайне неэффективно порождать все возможные соответствия между людьми и этажами, а затем полагаться на то, что поиск с возвратом отсечет лишнее. Например, большая часть ограничений зависит только от одной или двух переменных, соответствующих людям, и их можно было бы проверять раньше, чем этажи выбраны для всех действующих лиц. Напишите и продемонстрируйте значительно более эффективную недетерминистскую процедуру, которая бы решала задачу, порождая только те варианты, которые еще не исключены благодаря предыдущим ограничениям. (Подсказка: потребуется набор вложенных выражений let.)

Упражнение 4.41.

Напишите процедуру для решения задачи о проживании на обычной Scheme. Упражнение 4.42.

Решите задачу «Лгуньи» (из Phillips 1934):

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

Бетти: «Китти была на экзамене второй, а я только третьей».

Этель: «Вам будет приятно узнать, что я написала лучше всех. Второй была

Джоан».

Джоан: «Я была третьей, а бедная Этель последней».

Китти: «Я оказалась второй. Мэри была только четвертой».

Мэри: «Я была четвертой. Первое место заняла Бетти».

В каком порядке на самом деле расположились отметки девочек?

Упражнение 4.43.

Решите с помощью amb-интерпретатора следующую задачу:49

У отца Мэри Энн Мур есть яхта, и у каждого из четверых его друзей тоже. Эти четверо друзей - полковник Даунинг, мистер Холл, сэр Барнакл Худ и доктор Паркер. У каждого из них тоже есть по дочери, и каждый из них назвал свою яхту в честь дочери одного из своих друзей. Яхта сэра Барнакла называется Габриэлла, яхта мистера Мура - Лорна, а у мистера Холла яхта Розалинда. Мелисса, яхта полковника Даунинга, названа в честь дочери сэра Барнакла. Отец Габриэллы владеет яхтой, названной в честь дочери доктора Паркера. Кто отец Лорны?

Попытайтесь написать программу так, чтобы она работала эффективно (см. упражнение 4.40). Кроме того, определите, сколько будет решений, если не указывается, что фамилия Мэри Энн - Мур.

49Задача взята из книжки «Занимательные загадки», опубликованной в 60-е годы издательством Литтон Индастриз. Книжка приписывает задачу газете «Кэнзас стейт энджинир».

Упражнение 4.44.

В упражнении 2.42 описывалась «задача о восьми ферзях», в которой требуется расставить на шахматной доске восемь ферзей так, чтобы ни один не бил другого. Напишите недетерминистскую программу для решения этой задачи.

Синтаксический анализ естественного языка

Программы, которые должны принимать на входе естественный язык, обычно прежде всего пытаются провести синтаксический анализ (parsing) ввода, то есть сопоставить входному тексту какую-то грамматическую структуру. Например, мы могли бы попытаться распознавать простые предложения, состоящие из артикля, за которым идет существительное, а вслед за ними глагол, например The cat eats («Кошка ест»). Чтобы выполнять такой анализ, нам нужно уметь определять части речи, к которым относятся отдельные слова. Мы можем для

50

начала составить несколько списков, которые задают классы слов:50 (define nouns (noun student professor cat class)) (define verbs (verb studies lectures eats sleeps)) (define articles (article the a))

Нам также нужна грамматика (grammar), то есть набор правил, которые описывают, как элементы грамматической структуры составляются из меньших элементов. Простейшая грамматика может постановить, что предложение всегда состоит из двух частей - именной группы, за которой следует глагол, - и что именная группа состоит из артикля и имени существительного. С такой грамматикой предложение The cat eats разбирается так:

(sentence (noun-phrase (article the) (noun cat)) (verb eats))

Мы можем породить такой разбор при помощи простой программы, в которой для каждого грамматического правила имеется своя процедура. Чтобы разобрать предложение, мы определяем две его составные части и возвращаем список из этих элементов, помеченный символом sentence:

(define (parse-sentence) (list sentence

(parse-noun-phrase) (parse-word verbs)))

Подобным образом, разбор именной группы состоит в поиске артикля и существительного:

(define (parse-noun-phrase) (list noun-phrase

(parse-word articles) (parse-word nouns)))

50Здесь мы используем соглашение, что первый элемент списка обозначает часть речи, к которой относятся остальные слова списка.