Навигация
Главная
Поиск
Форум
FAQ's
Ссылки
Карта сайта
Чат программистов

Статьи
-Delphi
-C/C++
-Turbo Pascal
-Assembler
-Java/JS
-PHP
-Perl
-DHTML
-Prolog
-GPSS
-Сайтостроительство
-CMS: PHP Fusion
-Инвестирование

Файлы
-Для программистов
-Компонеты для Delphi
-Исходники на Delphi
-Исходники на C/C++
-Книги по Delphi
-Книги по С/С++
-Книги по JAVA/JS
-Книги по Basic/VB/.NET
-Книги по PHP/MySQL
-Книги по Assembler
-PHP Fusion MOD'ы
-by Kest
Professional Download System
Реклама
Услуги

Автоматическое добавление статей на сайты на Wordpress, Joomla, DLE
Заказать продвижение сайта
Программа для рисования блок-схем
Инженерный калькулятор онлайн
Таблица сложения онлайн
Популярные статьи
OpenGL и Delphi... 65535
Форум на вашем ... 65535
HACK F.A.Q 65535
Бип из системно... 65535
Гостевая книга ... 65535
Invision Power ... 65535
Пример работы с... 65535
Содержание сайт... 65535
ТЕХНОЛОГИИ ДОСТ... 65535
Организация зап... 65535
Вызов хранимых ... 65535
Создание отчето... 65535
Программируемая... 65535
Эмулятор микроп... 65535
Подключение Mic... 65535
Создание потоко... 65535
Приложение «Про... 65535
Оператор выбора... 65535
Модуль Forms 65535
Имитационное мо... 60528
Реклама
Сейчас на сайте
Гостей: 14
На сайте нет зарегистрированных пользователей

Пользователей: 13,117
новичок: Asit
Новости
Реклама
Выполняем курсовые и лабораторные по разным языкам программирования
Подробнее - курсовые и лабораторные на заказ
Delphi, Turbo Pascal, Assembler, C, C++, C#, Visual Basic, Java, GPSS, Prolog, 3D MAX, Компас 3D
Заказать программу для Windows Mobile, Symbian

Расчет размера дохода на одного человека в Turbo Pascal
База данных междугородних телефонных разговоров на Delphi
Моделирование работы узла коммутации сообщений на GPSS + Пояснительная з...

Реклама



Подписывайся на YouTube канал о программировании, что бы не пропустить новые видео!

ПОДПИСЫВАЙСЯ на канал о программировании
4.1. Порождение множественных решений


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



в которых отец(X, Y) обозначает, что Y является отцом X . Вопрос
?- отец(X,Y).



имеет несколько возможных ответов. Если мы будем вводить после каждого ответа точку с запятой, то Пролог выдаст следующие ответы:
X = мэри, Y = джордж;
X = джон, Y = джордж;
X = сью, Y = гарри;
X = джордж, Y = эдуард.



Пролог найдет эти ответы, просматривая базу данных в поисках фактов и правил с предикатом отец и печатая их в том порядке, в каком они представлены в базе данных. При этом Пролог не проявляет особого «интеллекта» – он ничего не помнит о предыдущих ответах. Так, если мы обратимся с вопросом
?- отец(_,X).



(для каких X верно то, что X является отцом), то мы получим
Х=джордж;
Х=джордж;
Х=гарри;
Х=эдуард.



при этом ответ джордж повторен дважды, так как Джордж является отцом как Мэри, так и Джона. Если Пролог может сделать одно и то же двумя различными способами, то он рассматривает это как два различных решения.
Повторный просмотр выполняется точно таким же способом, если выбор среди альтернатив происходит на более глубоком уровне обработки. Например, для определения отношения «одним из детей X является Y » могло бы быть использовано правило
ребенок(Х,Y):- отец(Y,X).



Тогда вопрос
?- ребенок(Х,Y).



дал бы
X = джордж, Y = мэри;
X = джордж, Y=джон;
X = гарри, Y = сью;
X = эдуард, Y = джордж.



Так как отец(Y, X) имеет четыре решения, то столько же решений имеет и ребенок(Х, Y). Более того, решения порождаются в том же самом порядке. Единственное, что отличает эти решения, - это различный порядок аргументов в соответствии с определением для предиката ребенок. Аналогично, если мы определили
отец(X):- отец(_,X).



(отец (X) обозначает, что X является чьим-либо отцом), то на вопрос
?- отец(X).



были бы получены ответы:
X = джордж;
X = джордж;
X  = гарри;
X = эдуард.



Если мы перемешаем факты и правила, то выбор альтернатив вновь будет производиться в соответствии с порядком, в котором представлены факты и правила. Так, мы могли бы определить:
человек(адам).
человек(X):- мать(X,Y).
человек(ева).
мать(каин,ева).
мать(авель,ева).
мать(иавал,ада).
мать(тувалкаин,цилла).



( адам - человек; объект является человеком, если он имеет мать; ева – человек. Перечисленные люди имеют указанных матерей). В этом случае если бы мы сделали запрос
?- человек (X).



то ответом было бы:
X = адам;
X = каин;
X = авель;
X = иавал;
X = тувалкаин;
X = ева.



Давайте рассмотрим более интересный случай, когда имеются два целевых утверждения, для каждого из которых есть несколько решений. Предположим, что мы планируем провести вечеринку и хотим порассуждать о том, кто с кем мог бы танцевать. Мы можем начать писать программу следующим образом:
возможная_пара(X, Y):- парень(Х), девушка(Y).
парень(джон).
парень(мармадук).
парень(бертрам).
парень(чарлз).
девушка(гризелда).
девушка(эрминтруда).
девушка(брунхильда).



В программе определено, что X и Y образуют возможную пару, если X является парнем, a Y — девушкой. Теперь давайте посмотрим, какие возможные пары имеются:
?- возможная_пара(X, Y).
X = джон, Y = гризелда;
X = джон, Y = эрминтруда;
X = джон, Y = брунхильда;
X = мармадук, Y = гризелда;
X = мармадук, Y = эрминтруда;
X = мармадук, Y = брунхильда;
X = бертрам, Y = гризелда;
X = бертрам, Y = эрминтруда;
X = бертрам, Y = брунхильда;
X = чарлз, Y = гризелда;
X = чарлз, Y = эрминтруда;
X = чарлз, Y = брунхильда.



Вы должны быть уверены, что понимаете, почему Пролог породил решения в таком порядке. Прежде всего он ищет сопоставление для цели парень(X) и находит, что первым парнем является джон. Затем он находит сопоставление для цели девушка(Y) , выбирая гризелда в качестве первой девушки. В этом месте мы запрашиваем новое решение, вводя ';'. Пролог поэтому считает, что последнее доказательство согласованности цели потерпело неудачу, и делает попытку вновь доказать согласованность последней из рассматривавшихся целей. Этой целью является утверждение девушка, встретившееся при доказательстве согласованности целевого утверждения возможная_пара. Обнаруживается альтернативный вариант эрминтруда, и, следовательно, следующим решением является пара джон и эрминтруда. Аналогично порождается пара джон и брунхильда в качестве третьего решения. При следующей попытке доказать согласованность целевого утверждения девушка(Y) Пролог обнаружит, что маркер, соответствующий этому целевому утверждению, находится в конце базы данных и, следовательно, попытка найти новое сопоставление для этого целевого утверждения терпит неудачу. Тогда делается попытка вновь доказать согласованность целевого утверждения парень(Х), маркер которого был установлен на первый факт предиката парень, и, следовательно, следующим найденным решением, соответствующим второму парню, является мармадук. Теперь, когда для этого целевого утверждения найдено новое решение, Пролог определяет, что следует делать далее – он должен найти сопоставление для цели девушка(Y), осуществляя поиск решения с самого начала базы данных. Так что он выбирает гризелда в качестве первой девушки. Следующие три решения содержат мармадук и имена трех девушек. Очередная попытка найти альтернативное решение для цели девушка заканчивается неудачей. Поэтому ищется другой парень, а поиск среди девушек производится с начала базы данных. Аналогичным образом происходит выполнение программы и далее.
В конце концов сложится ситуация, когда доказательство согласованности целевого утверждения девушка закончится неудачей и при этом будут также исчерпаны все решения для целевого утверждения парень. Программа не может более найти ни одной пары.
Все приведенные примеры являются очень простыми. Они содержат лишь определения большого числа фактов или используют правила для доступа к этим фактам. По этой причине они могут порождать только конечное число возможных решений. В некоторых случаях нам может потребоваться порождать бесконечное число возможных вариантов – не потому, что мы хотим рассмотреть их все, а потому, что мы не знаем заранее, сколько их понадобится. В этом случае необходимо рекурсивное определение (обсуждавшееся в предыдущей главе).
Рассмотрим следующее определение целого числа (здесь под «целым» числом понимается целое положительное число). Целевое утверждение целое _ число(N) согласуется с базой данных, если переменная N конкретизирована и ее значением является целое число. Если переменная N неконкретизирована в момент рассмотрения целевого утверждения, то попытка найти соответствие для утверждения целое_число (N) приведет к тому, что будет выбрано целое число, которое будет присвоено N в качестве значения.
/* 1 */ целое_число(0).
/* 2 */ целое_число (X):- целое_число (Y),X is Y+1)



Если мы зададим вопрос
?- целое_число (X).



то получим в качестве возможных ответов все целые числа в порядке возрастания (0, 1, 2, 3,…), по одному числу каждый раз. Всякий раз, когда инициируется возврат (возможно, в результате ввода точки с запятой ';'), для предиката целое_число находится новое сопоставление, в результате чего его аргументу присваивается очередное целое число. Таким образом, это короткое определение порождает бесконечное число решений. Почему? На каждом этапе самый нижний указатель (1) на рисунке указывает место, где впоследствии будет выбрано иное решение. Первоначально для ответа на вопрос имеется выбор между фактом 1 и правилом 2 . Если выбирается факт 1 , то ничего более выбирать не придется, и мы получаем X = 0. В противном случае выбирается правило 2 и ищется соответствие для цели, порождаемой этим правилом. Если выбирается факт 1 , то завершается доказательство целевого утверждения с ответом X=1 ; в противном случае используется правило 2 и снова ищется соответствие для появившейся подцели. И так далее. На каждом этапе первое что делает Пролог – это выбирает факт 1 . Только при выполнении возврата он изменяет последний сделанный им выбор. Каждый раз, когда он это делает, он возвращается к тому месту, где в последний раз выбирал факт 1 , и выбирает вместо него правило 2 . При этом выборе появляется новая подцель. Факт 1 представляет первую возможность для сопоставления с этой подцелью.
Большинство правил на Прологе будут порождать альтернативные решения, если они сопоставляются с целями, содержащими большое число неконкретизированных переменных. Например, отношение принадлежности элемента списку:
принадлежит(X,[X |_] ).
принадлежит(X,[_ |Y]):- принадлежит(X,Y).



порождает альтернативные решения. Если мы задаем вопрос
?- принадлежит(а,X).



(обратите внимание, что X в вопросе является неконкретизированной переменной), то последовательные значения переменной X будут представлять частично конкретизированные списки, в которых а является первым, вторым, третьим и так далее элементом списка. Убедитесь, что вы понимаете, почему так получается. Другим следствием возврата, допускаемого при выполнении предиката принадлежит, является то, что вопрос
?- принадлежит(а,[а,b,r,а,с,а,d,а,b,r,а]).



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

Бесплатный торрент трекер - скачать http://n-torrents.ru/.
Опубликовал Kest Июль 09 2009 16:15:31 · 0 Комментариев · 13326 Прочтений · Для печати

• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •


Комментарии
Нет комментариев.
Добавить комментарий
Имя:



smiley smiley smiley smiley smiley smiley smiley smiley smiley
Запретить смайлики в комментариях

Введите проверочный код:* =
Рейтинги
Рейтинг доступен только для пользователей.

Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.

Нет данных для оценки.
Гость
Имя

Пароль



Вы не зарегистрированны?
Нажмите здесь для регистрации.

Забыли пароль?
Запросите новый здесь.
Поделиться ссылкой
Фолловь меня в Твиттере! • Смотрите канал о путешествияхКак приготовить мидии в тайланде?
Загрузки
Новые загрузки
iChat v.7.0 Final...
iComm v.6.1 - выв...
Visual Studio 200...
CodeGear RAD Stud...
Шаблон для новост...

Случайные загрузки
Шкрыль А. - Разра...
IconCut [Исходник...
Интерактивный инт...
Flud Vkontakte.ru
Exe in exe
Sztransppanel
Усложнённый кальк...
PDJ_Anima
Программирование ...
Фундаментальные а...
SMExport
Swing. Эффектные...
MicroGPSS Studen ...
THttpScan v4.1
Анекдоты с ostrie.ru
Delphi 6. Учебный...
WAP версия сайта
Delphi 2005. Разр...
Text effect
Fig [Исходник на ...

Топ загрузок
Приложение Клие... 100530
Delphi 7 Enterp... 91894
Converter AMR<-... 20101
GPSS World Stud... 15392
Borland C++Buil... 13057
Borland Delphi ... 9153
Turbo Pascal fo... 7112
Калькулятор [Ис... 5193
Visual Studio 2... 5034
FreeSMS v1.3.1 3559
Случайные статьи
16.10.
Отличное описание ...
Программирование в...
Оперативно доступн...
INLINE error
Законы эмпирическо...
Использование Outl...
Бип из системного ...
ЦЕЛЬ: ПОЛУЧЕНИЕ СТ...
Команда INSERT
Windows 2000
Установка MPlayer ...
Создать глобальный...
брандмауэре
Команда ping - про...
13.1. Интерфейс
Создание дистрибут...
Инфраструктуры для...
Читателям первого ...
ОПИСАНИЕ МОДЕЛЕЙ С...
Элементы управлени...
Многопоточные очереди
ОСНОВНЫЕ КОНЦЕПЦИИ...
Тестирование компо...
Разработка приложе...
Статистика



Друзья сайта
Программы, игры


Полезно
В какую объединенную сеть входит классовая сеть? Суммирование маршрутов Занимают ли таблицы память маршрутизатора?