Студопедия

Главная страница Случайная страница

Разделы сайта

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






  • Согласование целевых утверждений. Поиск с возвратом






     

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

    Если в процедурных языках повторные вычисления проводятся с помощью оператора цикла, то в логическом программировании основными средствами таких вычислений является поиск с возвратом (BackTracking.) и рекурсия. Рассмотрим на примере правила разные_жанры и базы знаний процесс согласования целевых утверждений (ЦУ) вместе с работой механизма поиска с возвратом.

    Для наглядности введем вспомогательную структуру „состояние просмотра”, в которой пройденные записи в БЗ условно обозначаются символом * для первой подцели (внешней) в первой колонке, а для второй (внутренней) – во второй колонке. При этом при возвращении к предыдущей подцели отметки о просмотре в БЗ для текущей подцели аннулируются. Вычисления заканчиваются, когда все предикаты в БЗ будут пересмотрены для согласования самой внешней из подцелей.

    В результате запроса

    ? разные_жанры (Х, Y)

    ЦУ примет форму

    ? книга (Х, Y), книга (Х, Z) и Y< > Z, (1)

    которое содержит две подцели и одно условие. Сопоставление первой подцели с БЗ (состояние а) дает Х=стаут, Y=детектив и приходим к новому ЦУ

    ? книга (стаут, Z) и детектив< > Z.

    Обращение к БЗ (состояние b) дает Z=детектив, а проверка условия детектив< > детектив дает ложь (F). Другие сопоставления предиката книга (стаут, Z) с БЗ являются невозможными. В этом месте вступает в действие поиск с возвратом, мы возвращаемся к предыдущей подцели, ЦУ снова принимает вид (1) и просмотр БЗ начинается с записи, следующей после отметки.

    БЗ Состояние просмотра

    книга (стаут, детектив) * - * * * * * * * * * *

    книга (по, поэзия) - - - - * * * * * * * *

    книга (по, детектив) - - - - - - - * * - * *

    книга (шевченко, поэзия) - - - - - - - - - - * *

    а) b) c) d) e) f)

    Теперь из второй записи имеем Х=по, Y=поэзия и новое ЦУ

    ? книга (по, Z), поэзия< > Z (2)

    Согласование полученного ЦУ с БЗ, начиная с первого предиката, дает Z=поэзия, поэзия< > поэзия и, таким образом, дает ложь (F) (состояние c). Дальнейшее согласование (проход по неотмеченным предикатам из второй колонки) дает Z=детектив, поэзия< > детектив и, таким образом, находим первое решение (состояние d)

    Х=по, Y=поэзия, Z= детектив.

    Поиск с возвратом (проход по неотмеченным предикатам во второй колонке) других решений для (2) не дает и BackTracking снова возвращает нас к ЦУ (1), при этом просмотр начинается с третьей записи. Имеем

    Х=по, Y=детектив и новое ЦУ

    ? книга (по, Z), детектив< > Z

    которое будет истинным при Z=поэзия и находим второе решение (состояние e)

    Х=по, Y=детектив, Z=поэзия.

    Дальнейший поиск приводит к ситуациям, аналогичным состоянию b, и в результате БЗ для внешней подцели будет исчерпана – состояние f.

     






    © 2023 :: MyLektsii.ru :: Мои Лекции
    Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
    Копирование текстов разрешено только с указанием индексируемой ссылки на источник.