Недетерминированное программирование

Лекция №9

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

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

Метод «образовать и проверить»

Метод «образовать и проверить» – общий прием, используемый при проектировании алгоритмов и программ. Суть его состоит в том, что один процесс или программа генерирует множество предполагаемых решений задачи, а другой процесс или программа проверяет эти предполагаемые решения, пытаясь найти те из них, которые действительно являются решениями задачи.

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

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

find(X)¬generate(X), test(X).

Эта Пролог-программа действует подобно обычной процедурной программе, выполняющей генерацию вариантов и их проверку. Если при решении вопроса find(X)?, успешно выполняется цель generate(X) с выдачей некоторого X, то затем выполняется проверка test(X). Если проверка завершается отказом, то производится возвращение к цели generate, с помощью которой генерируется следующий элемент. Процесс продолжается итерационно до тех пор, пока при успешной проверке не будет найдено решение с характерными свойствами или генератор не исчерпает все альтернативные решения.

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

В качестве генератора обычно используется программа для предиката member (программа 3.12), порождающая множество решений. На вопрос member(X[a,b,c])? будут даны в требуемой последовательности решения Х = а, Х = b и Х = с. Таким образом, предикат member можно использовать в программах, реализующих метод «образовать и проверить» для недетерминированного выбора корректного элемента из некоторого списка.

Программа 14.1 представляет собой простой пример реализации метода «образовать и проверить» с использованием в качестве генератора предиката member. Эта программа предназначена для идентификации частей речи предложения. Предполагается, что предложение представлено списком слов и существует база данных фактов, задающих части речи для определенных слов. Для задания частей речи используются унарные предикаты, аргументами которых являются слова, например, предикат существительное (man) указывает, что man – существительное, Отношение глагол(Предложение, Слово) истинно, если Слово в предложении Предложение является глаголом. Аналогичный смысл имеют предикаты существительное/2 и артикль/2. На вопрос глагол([а,man,loves,a,woman),V)? методом «образовать и проверить» будет дан ответ V= loves. Слова предложения генерируются с помощью предиката member, и затем проверяется, являются ли они глаголами.

глагол (Предложение, Глагол) ¬

Глагол – глагол в спискеслов Предложение.

глагол (Предложение, Слово) ¬

member (Слово, Предложение), глагол (Слово).

существительное (Предложение, Слово)

member (Слово, Предложение), существительное(Слово).

артикль (Предложение, Слово)

member (Слово, Предложение), артикль (Слово).