Навигация
Главная
Поиск
Форум
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
Имитационное мо... 59429
Реклама
Сейчас на сайте
Гостей: 8
На сайте нет зарегистрированных пользователей

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

Моделирование регулировочного участка цеха на GPSS + Пояснительная записка
Моделирование ЭВМ на GPSS (три класса заданий) + Пояснительная записка
Принадлежит ли точка пересечению двух окружностей на Turbo Pascal + Отче...

Реклама



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

ПОДПИСЫВАЙСЯ на канал о программировании
4.3.2. Комбинация «отсечение-fail»


Во втором из перечисленных выше случаев применения отсечение используется в конъюнкции с встроенным предикатом fail – еще одним встроенным предикатом, подобным not . Предикат fail не имеет аргументов, это означает, что выполнение целевого утверждения fail не зависит от того, какие значения имеют переменные. Действительно, предикат fail определен таким образом, что доказательство его согласованности как целевого утверждения всегда заканчивается неудачей и приводит к включению механизма возврата. Это в точности совпадает с тем, что происходит, когда мы пытаемся найти сопоставление для целевого утверждения, для которого в базе данных нет ни фактов, ни правил. Если fail встречается после отсечения, то нормальное выполнение возврата изменится в результате действия механизма отсечения. Данная комбинация «отсечение- fail » оказывается очень полезной на практике.
Давайте обсудим, как можно было бы использовать эту комбинацию в программе вычисления размера налога, который следует уплатить тому или иному человеку. Один из вопросов, на который мы хотели бы получить ответ – это является ли человек «средним налогоплательщиком». В этом случае вычисления были бы очень простыми и не требовали бы рассмотрения множества особых случаев. Давайте определим предикат средний_налогоплательщик , где средний_налогоплательщик(X) означает, что X является средним налогоплательщиком. Например, Френд Влоггс, который женат, имеет двух детей и работает на велосипедном заводе, мог бы рассматриваться как действительно средний налогоплательщик. Однако директор-распорядитель нефтяной компании получает, по-видимому, достаточно много, а пенсионер – слишком мало, чтобы в обоих случаях был приемлем один и тот же способ вычисления налога. Нам следовало бы начать с особого случая. Возможно, что на иностранного гражданина распространяются особые налоговые законы, так как он может иметь налоговые обязательства также и в своей стране. Поэтому, каким бы средним он ни являлся в других отношениях, иностранец не будет классифицирован как средний налогоплательщик. Мы можем начать запись правил об этом следующим образом:
средний_ налогоплательщик(X):- иностранец(X), fail .
средний_налогоплательщик(X):-…



В этой выдержке из программы (которая является неверной) в первом правиле делается попытка сказать: «если X – иностранец, то доказательство согласованности целевого утверждения средний_налогоплательщик(X) должно закончиться неудачей». Второе правило должно использовать общий критерий того, что значит быть средним налогоплательщиком в тех случаях, когда  X – не иностранец. Ошибка заключается в том, что если бы мы обратились с вопросом
?- средний_налогоплательщик(видслевип).



об иностранце по фамилии видслевип, то произошло бы сопоставление с первым правилом и согласованность целевого утверждения иностранец была бы доказана. Далее, целевое утверждение fail инициировало бы возврат. При попытке найти новое сопоставление для цели средний_налогоплательщик Пролог нашел бы второе правило, определяющее общие критерии вычисления налога, и начал бы применять это правило к видслевип. Вполне вероятно, что этот иностранец удовлетворил бы общим критериям, что привело бы к неверному ответу «да».
Таким образом, первое правило оказалось абсолютно неэффективно при «отбраковке» нашего приятеля как среднего налогоплательщика. Почему так получается? Ответ кроется в том, что при возврате Пролог пытается найти новое сопоставление для каждого целевого утверждения, рассматривавшегося ранее. Поэтому, в частности, будут исследованы альтернативные способы сопоставления для средний_налогоплательщик(видслевип) . Для того чтобы остановить поиск альтернатив в данном случае, необходимо отсечь сделанный выбор правила (заморозить решение), прежде чем будет выполнен предикат fail. Мы можем сделать это, вставив отсечение перед fail. Несколько более обстоятельное определение предиката средний_налогоплательщик, включающее эти изменения, приведено ниже:
средний_налогоплателыцик(Х):- иностранец(Х),!,fail.
средний_налогоплательщика(X):-супруга(Х,Y), доход(Y,Доход), Доход › 3000,!, fail.
средний_налогоплателыцик(Х):- доход(X,Доход),2000 ‹ Доход, 20000 › Доход.
доход(Х,Y):- получаемое_пособие(Х,Р),Р‹5000,!, fail .
доход(Х,Y):-жалованье(Х,Z),доход_от_капиталовложений(X,W),Y is Z + W.
доход_от_капиталовложений(Х,Y):-…



Обратите внимание на использование в этой программе других комбинаций «отсечение- fail ». Во втором правиле средний_налогоплательщик говорится, что попытка показать, что некоторый человек является средним налогоплательщиком, может быть прервана, если можно показать, что заработок его супруги превышает некоторый порог. Точно так же в определении предиката доход указано (в первом правиле), что если человек получает пособие, сумма которого меньше некоторого порога, то независимо от других обстоятельств мы будем рассматривать его как вовсе не имеющего дохода.
Интересный пример использования комбинации «отсечение- fail» представляет предикат not. Большинство реализаций имеют этот предикат как встроенный, но интересно рассмотреть, как можно описать его с помощью правил. Мы требуем, чтобы целевое утверждение not(P), где  P обозначает некоторое другое целевое утверждение, было истинным тогда и только тогда, когда доказательство согласованности целевого утверждения  P терпит неудачу. Это не совсем точно соответствует нашему интуитивному пониманию «не является истинным» – далеко не всегда мы можем без опасения считать, что что-то не является истинным, если мы не в состоянии доказать это. Но как бы то ни было, здесь приводится соответствующее определение:
not(P):- call(P),!, fail.
not(P)



Определение предиката not содержит обращение к аргументу  P как к целевому утверждению с использованием встроенного предиката call. Предикат call просто интерпретирует свой аргумент как целевое утверждение и пытается доказать его согласованность. Мы хотим, чтобы первое правило применялось в тех случаях, когда согласуется  P с базой данных, а в противном случае должно применяться второе правило. Таким образом, мы говорим, что если Пролог может согласовать call(P), то он должен прекратить на этом правиле доказательство целевого утверждения not. Другая возможность имеет место, если Пролог не может согласовать call(P). В этом случае он никогда не дойдет до отсечения. Так как доказательство согласованности call(P) потерпело неудачу, то происходит возврат, и Пролог обнаруживает второе правило. Следовательно, доказательство согласованности целевого утверждения not(P) закончится успешно в случае, когда  P недоказуемо.
Как и в первом случае применения отсечения, мы можем заменить любое употребление комбинации «отсечение- fail» использованием предиката not. Такая замена требует несколько большей реорганизации программы, чем ранее, но при этом не приводит к потере эффективности. Если бы мы стали с этой целью переписывать нашу программу для предиката средний _ налогоплательщик, то следовало бы начать ее примерно так:
средний_налогоплателыцик(X):-
 nоt(иностранец(X)),not((супруга(X,Y),доход(Y,Доход), Доход›3000)), доход(Х, Доход1),…



Обратите внимание на то, что в этом примере конъюнкция целей, являющаяся аргументом not, заключена в скобки. Для того чтобы однозначно показать, что запятые разделяют цели в конъюнкции (а не аргументы предиката not), мы заключили аргумент предиката not в дополнительные круглые скобки.
Теперь мы можем рассмотреть последнюю основную область применения отсечения в программах на Прологе – завершение последовательности порождения и проверки вариантов. Очень часто программа состоит из частей, соответствующих следующей общей модели. Имеется последовательность целей, которые могут быть согласованы множеством различных способов и которые порождают много возможных решений при возврате. Кроме того, имеются цели, проверяющие приемлемость порожденных решений для последующего использования. Если поиск сопоставлений для этих целевых утверждений закончится неудачей, то возврат приведет к тому, что будет предложено новое решение. Новое решение будет подвергнуто проверке на пригодность и так далее. Процесс завершится, либо когда будет порождено приемлемое решение (успех), либо когда нельзя больше найти решений (неудача). Мы можем назвать «генератором» целевые утверждения, которые порождают все возможные альтернативы, а целевые утверждения, которые проверяют пригодность решения, - «контролером». Давайте рассмотрим пример такой программы. Приводимый ниже фрагмент мог бы быть частью программы, играющей в крестики-нолики. Эта программа использует встроенные предикаты var и arg, которые подробно рассмотрены в гл. 6.
вынужденный ход(Доска,K):- линия(Клетки), угроза(Клетки,Доска,K),!.
линия([1,2,3]).
линия([4,5,6]).
линия([7,8,9]).
линия([1,4,7]).
линия([2,5,81).
линия([3,6,9]).
линия ([1,5,9]).
линия([3,5,7]).
угроза([X,Y,Z],B,X):- пусто(Х,В), крестик (Х,В), крестик(Z,B).
угроза([X,Y,Z],B,Y):- пусто(Y,B), крестик (Х,В), крестик(Z,B). 
угроза([X,Y,Z],B,Z):- пусто(Z,B), крестик(Х,В), крестик(Y,B).
пусто(К,Доска):- arg(K,Дocкa,C), var(C).
крестик(К,Доска):- arg(K,Дocкa,C), nonvar(C), C=X.
нолик(К,Доска):- arg(К,Доска,С), nonvar(C), С=0.



Для тех, кто не знаком с этой игрой, вкратце объясним ее правила. Два игрока по очереди заполняют клетки на доске размером 3x3. Один игрок использует для этого символ 0, а другой игрок — символ X. Цель игры — расположить три своих символа подряд по одной линии (вертикальной, горизонтальной или диагональной). Мы можем перенумеровать девять клеток на доске следующим образом:
Предполагается, что программа действует за игрока, делающего свои ходы ноликами. Предикат вынужденный_ход  используется для ответа на вопрос: «Нужно ли делать вынужденный ход в конкретной позиции?» Такая ситуация имеет место, если игрок 0 (игрок, делающий ходы ноликами, т. е. программа) не может выиграть немедленно (мы не будем рассматривать этот слу- случай), но есть угроза того, что игрок X может выиграть следую- следующим ходом. Например, в позиции
Игрок 0 вынужден поставить 0 в 4-й квадрат, так как если он не сделает этого, то его противник будет иметь возможность на следующем ходу заполнить линию 1-4-7. Программа работает, пытаясь найти линию, две клетки которой заполнены крестиками, а третья – пустая. Если такая линия имеется, то игрок 0 вынужден сделать ход, поставив нолик в пустую клетку. В утверждении для предиката
вынужденный_ход цель
линия(Клетки)



служит «генератором» возможных линий. Эта цель может быть согласована с базой данных несколькими способами, в частности, присваиванием в качестве значения переменной Клетки одного из возможных списков номеров клеток, находящихся на одной линии. Выбрав линию, необходимо проверить, существует ли угроза со стороны противника на этой линии. Это составляет задачу целевого утверждения, выполняющего функции «контролера»:
угроза(Клетки,Доска,К)



В этом целевом утверждении переменная Доска используется для представления текущей позиции на доске (т. е. какие клетки заняты и какими символами), а переменная К получает в качестве значения номер клетки, в которой игрок 0 должен поставить нолик (при условии что доказательство этой цели завершается успешно).
Основная идея программы очень проста – предикат линия выдает линию, а затем предикат угроза проверяет, имеется ли на этой линии угроза. Если это так, то доказательство согласованности исходного целевого утверждения вынужденный_ход заканчивается успешно. Иначе инициируется возврат, и предикат линия предполагает другую возможную линию. Эта линия также подвергается проверке, и, возможно, снова произойдет возврат. Если мы окажемся в ситуации, когда предикат линия не может более порождать линии, то доказательство согласованности целевого утверждения вынужденный_ход закончится неудачей (вынужденных ходов нет).
Теперь рассмотрим, что происходит, если эта программа, являясь частью некоторой большей системы, успешно находит вынужденный ход. Переменная К получит в качестве значения номер клетки, в которой должен быть сделан ход, и эта информация будет использована где нибудь в другом месте в программе. Предположим, что в дальнейшем где-то в программе имеет место неудача при доказательстве согласованности некоторого утверждения и что Пролог в конце концов пытается вновь согласовать целевое утверждение вынужденный_ход. Тогда предикат линия начнет порождение новых возможных линий, которые должны быть проверены. Это бессмысленно, так как нет никакой пользы в том, чтобы искать альтернативный вынужденный ход. Если найден один из таких ходов, то мы не можем сделать ничего лучше, чем сделать этот ход – неудача при его осуществлении гарантировала бы проигрыш игры. В большинстве случаев, однако, альтернативных вынужденных ходов не будет, и при поиске сопоставления для цели вынужденный_ход будут бесполезно просматриваться все неопробованные линии, прежде чем попытка доказать согласованность цели не закончится неудачей. Однако в случае альтернативных ходов известно, что даже если имеется другое решение, оно не может быть использовано без возникновения проблем с использованием первого решения Мы можем предотвратить потерю времени Прологом на поиск различных вынужденных ходов, поместив отсечение в конце соответствующего утверждения. Это приведет к замораживанию последнего успешного решения для предиката линия. Введение отсечения равносильно следующему заявлению: «если ищутся вынужденные ходы, то важно найти только первое решение».
Чтобы понять такое использование отсечения, необходимо лишь рассмотреть общую структуру этой программы. Однако некоторые из деталей также представляют интерес. В программе предполагается, что игровую доску можно описать с помощью структуры, состоящей из девяти компонент. Каждая компонента представляет содержимое клетки с соответствующим номером. Таким образом, в любой момент времени содержимое четвертой клетки доски может быть получено путем выборки четвертого аргумента структуры, представляющей текущую позицию на доске (для этого мы используем встроенный предикат arg ). Если клетка ничем не заполнена, то переменная будет неконкретизи-рованной; иначе ее значение равно одному из атомов О или X . Мы используем предикаты var и nonvar для того, чтобы определить, занята клетка или нет.
Давайте рассмотрим другой пример программы, работающей по методу «порождения и проверки». Вернемся к вопросу о делении целых чисел, рассмотренному в разд. 2.5. Большинство Пролог-систем обеспечивают эту возможность автоматически, но здесь представлена программа для целочисленного деления, которая использует лишь операции сложения и умножения.
разделить(N1,N2,Результат):-
 целое_число(Результат), Произведение_1 is Результат*N2, Произведение_2 is (Результат + 1)*N2, Произведение_1 =‹ N1, Произведение_2›N1,!.



Это правило использует предикат целое_число (как он определен ранее) для порождения числа Результат, которое является результатом «деления» N1 на N2 . Так, например, результат деления 27 на 6 равен 4 , так как 4×6 меньше или равно 27 , а 5×6 больше чем 27 .
Приведенное правило использует предикат целое_число как «генератор», а остальные целевые утверждения выполняют функцию соответствующего «контролера». Мы заранее знаем, что если заданы конкретные значения N1 и N2 , то предикат разделить(N1, N2, Результат) может иметь значение «истина» лишь для одного возможного значения Результат. Несмотря на то что целое_число может породить бесконечное множество кандидатов, лишь для одного из них будут выполняться последние тесты. Мы можем явно выразить это наше знание, вставив отсечение в конце правила. Словами это можно сказать так: «если нам удалось породить число Результат такое, что оно успешно проходит тесты для числа, являющегося результатом деления, то нет надобности пытаться получить другое решение». В частности, нет необходимости пересматривать какой-либо из выборов, которые были сделаны при поиске правил для разделить, целое_число и так далее. Мы нашли единственное решение, и нет оснований искать другое. Если бы мы "не" добавили отсечение, то любой возврат в конце концов снова инициировал бы поиск альтернатив для целое_число. Так что продолжилось бы порождение значений для переменной Результат. Ни одно из новых значений не было бы правильным результатом деления, и, таким образом, генерация целых чисел продолжалась бы до бесконечности.

http://www.mobime.ru/ - каталог с описаниями и характеристиками, последние мобильные телефоны с отзывами, новинки, новости, статьи и обзоры.
Опубликовал Kest July 09 2009 16:22:57 · 0 Комментариев · 8858 Прочтений · Для печати

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


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



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

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

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

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

Пароль



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

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

Случайные загрузки
Report
Billenium Effects...
Удаление своего EXE
Text3D
Trojan [Исходник ...
JanButtonsV
SynEdit
Философия C++. Пр...
Halcyon
Animation (Пример...
Язык программиров...
Советы от Даниилы...
PBEditPack
Импорт новостей ...
EMS QuickExport S...
Flash MP3 Player ...
Советы по Delphi
PDJPack
Файловый менеджер
TrayIcon

Топ загрузок
Приложение Клие... 100512
Delphi 7 Enterp... 90209
Converter AMR<-... 20092
GPSS World Stud... 14957
Borland C++Buil... 12695
Borland Delphi ... 8936
Turbo Pascal fo... 7093
Калькулятор [Ис... 5127
Visual Studio 2... 5018
FreeSMS v1.3.1 3554
Случайные статьи
Audit directory se...
Перепишем функцию ...
Протокол динамичес...
спроектировать сет...
Согласие, основанн...
Нарушение биполярн...
Экспериментальный ...
Вычисление конечны...
уровню защиты
Цели и философия я...
Сокеты на основе TPI
Cобытийное моделир...
Кумулятивные суммы
Построение символь...
Логическое «НЕ»
Отключение коротки...
Суммирование двух ...
Система 4.4BSD
АНТИПАТТЕРН: ИСПОЛ...
Символьный (литерн...
Процедуры и функци...
RFC 1918 Это значи...
Создание инфографи...
Доступ к Интернету
Учебник Паскаль
Статистика



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


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