Методы искусственного интеллекта для синтеза проектных решений. Подольский В.Е - 41 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

6.7.4. Слияние списков
Данная функция выполняется рекурсивно:
append([],L,L).
append([X|L],L2,[X|L3]) :- append(L1,L2,L3).
Выход на граничное условие происходит, когда первый аргумент является пустым списком. Любой список,
присоединённый к пустому списку, даёт тот же самый список. Во всех других случаях выполняется второе правило, смысл
которого можно описать так:
1)
первый элемент первого списка (X) всегда будет и первым элементом третьего списка;
2)
хвост третьего списка (L3) всегда будет представлять результат присоединения второго списка (L2) к хвосту первого
списка (L1). Для присоединения рекурсивно вызывается предикат append;
3)
так как при каждом обращении к правилу удаляется голова первого списка, то постепенно этот список будет
исчерпан и станет пустым так, что произойдет выход на граничное условие.
6.8. ОТСЕЧЕНИЕ
В Прологе используется специальный механизм, называемый отсечением (или сокращением). Отсечение позволяет
указать, какие из сделанных ранее выборов не следует пересматривать при возврате по цепочке согласованных целевых
утверждений.
Существуют две причины, побуждающие включать в программу такие указания:
1)
программа будет выполняться быстрее, так как не будет тратиться время на попытки найти новые сопоставления для
целей, о которых заранее известно, что они не внесут ничего нового в решение;
2)
программа может занимать меньше места в памяти, так как отсутствует необходимость запоминать точки возврата
для последующего анализа.
В некоторых случаях включение отсечения в программу будет означать переход от правила, которое не работает, к
правилу, которое работает.
Отсечение записывается в программе с помощью предиката “!”
Например, в рассматриваемом ранее примере имелось правило:
Sreda (“разбавленная кислота”) :- аsk_sreda (Х), is(Х, _),
conc(“менее 70“), write (“среда = разбавленная кислота“).
Переписав правило с использованием отсечения:
Sreda (”разбавленная кислота”) :- аsk_sreda (Х), is(Х, _), !,
conc(“менее 70“), write (“среда = разбавленная кислота“).
Мы упростим процесс поиска. Если мы не найдём подтверждения факта is, то все остальные условия отсекутся и не
потребуется дальнейших действий, тогда как в первоначальном варианте нам требуется проверить согласованность всех
условий, входящих в правило.
Существуют различные способы описания того, что произошло с решениями, попавшими в область действия
отсечения:
−
во-первых, можно сказать, что оставшиеся альтернативы отбрасываются;
−
во-вторых, можно смотреть на символ отсечения как на некий разделитель (забор), отделяющий целевые
утверждения, например: foo:- а, b, с,!, d, e, f.
При обработке такого правила Пролог без каких-либо ограничений может выполнять возврат среди целей а, b и с до тех
пор, пока не будет доказана цель с. Это приведет к тому, что Пролог перешагнёт через “забор !” и приступит к доказательству
согласованности целевого утверждения d. Далее возврат может осуществляться между целевыми утверждениями d, e, f. При
этом возможно, мы достигнем согласованности всех целей. Однако возможно этого не произойдёт и перешагнув “забор”
обратно новых попыток доказательства утверждения с делаться не будет, а следовательно правило foo потерпит неудачу.
Итак, можно выделить три основных случая использования отсечения:
1.
Когда мы хотим указать системе, заданного целевого утверждения, т.е. отсечение означает: если мы дошли до этого
места, то выбрали именно то правило, которое нужно для данного целевого утверждения. Примером такого случая может
служить задание граничных условий при рекурсии.
2.
Когда мы хотим указать системе, что необходимо немедленно прекратить доказательство согласованности
конкретного правила, не пытаясь найти для него альтернативные решения, т.е. это означает: если вы дошли до этого места,
вам следует прекратить попытки доказать согласованность данного целевого утверждения (пример выше).
3.
Когда мы хотим закончить порождение альтернативных решений. В этом случае отсечение означает: если вы дошли
до этого места, то вы нашли единственное решение задачи.
Итак, подводя итог, отметим, что программа на языке Пролог включает цель, которую необходимо доказать, используя
все имеющиеся факты и правила, т.е. необходимо доказать согласованность цели с базой знаний. В процессе доказательства
база знаний просматривается сначала. Если цель сопоставляется с правилом, то требуется доказательство всех утверждений,
входящих в это правило.
В случае удачного поиска, мы можем сделать попытку вновь доказать согласованность цели с базой знаний. В этом
случае необходимо вернуть в исходное неопределённое состояние каждую переменную, конкретизированную при выборе
предыдущего утверждения. Эти действия можно назвать “уничтожением” результатов, полученных ранее при
доказательстве согласованности цели. Затем просмотр базы знаний возобновляется, но не сначала, т.е. ранее обнаруженные
факты и правила не учитываются. Как и ранее цель, выбранная при возврате, может оказаться согласованной или не
согласованной с базой знаний.

Страницы