У представленій статті розглядається варіант реалізації алгоритму зворотного виведення при вирішенні логічних завдань. Даний алгоритм широко застосовується в системах штучного інтелекту, експертних системах. Наведено приклад його використання в практичних завданнях. Детально представлений сам алгоритм, а також граматика для побудови логічних формул і висловлювань.

Анотація наукової статті з комп'ютерних та інформаційних наук, автор наукової роботи - Рогозін Олег Вікторович, Рогозін Микола Олегович


Область наук:
  • Комп'ютер та інформатика
  • Рік видавництва: 2018
    Журнал
    Освітні технології (м.Москва)
    Наукова стаття на тему 'АЛГОРИТМ ЗВОРОТНОГО ВИВЕДЕННЯ ПРИ ВИРІШЕННІ ЛОГІЧНИХ ЗАВДАНЬ'

    Текст наукової роботи на тему «Алгоритм ЗВОРОТНОГО ВИВЕДЕННЯ ПРИ ВИРІШЕННІ ЛОГІЧНИХ ЗАВДАНЬ»

    ?ТЕХНОЛОГІЯ І ПРАКТИКА НАВЧАННЯ ^ 100.........................

    Рогозін Олег Вікторович, кандидат технічних наук, доцент кафедри ІУ-7 МГТУ ім. Баумана, м.Москва

    Рогозін Микола Олегович, асистент кафедри ІУ-7, МГТУ ім. Баумана, м.Москва

    АЛГОРИТМ ЗВОРОТНОГО ВИВЕДЕННЯ ПРИ ВИРІШЕННІ ЛОГІЧНИХ ЗАВДАНЬ

    У представленій статті розглядається варіант реалізації алгоритму зворотного виведення при вирішенні логічних завдань. Даний алгоритм широко застосовується в системах штучного інтелекту, експертних системах. Наведено приклад його використання в практичних завданнях. Детально представлений сам алгоритм, а також граматика для побудови логічних формул і висловлювань.

    Ключові слова: штучний інтелект, алгоритм зворотного виведення, експертні системи.

    Вступ

    У побудові сучасних обчислювальних систем все більшого значення набувають підходи і методи, засновані на використанні алгоритмів штучного інтелекту. Починаючи з вісімдесятих років минулого століття мови програмування з використанням елементів логічного мислення отримали широкий розвиток. Так, в ЕОМ п'ятого покоління в якості основного мови програмування було вирішено використовувати мову програмування Пролог. У цій мові механізм логічного висновку є вбудованим і реалізується на основі алго-

    ритму зворотного виведення. У представленій статті розглядається задача розробки модуля логічного висновку за аналогією з реалізованим в мові Пролог і демонструються можливості практичного використання даного алгоритму.

    Основні поняття, особливості та зміст завдання зворотного виведення

    Розглянемо в якості практичного прикладу реалізацію механізм зворотного виведення в логічної моделі. Модель представлення знань буде містити набір правил і фактів. Основні граматичні конструк-

    101

    ції модуля логічного висновку представимо на основі відомої нотації Бекуса - Наура:

    <правило> :: = <заголовок правила> >

    <список умов>

    <список умов> :: = <умова> |

    <список умов> & <умова> <умова> :: = <предикат> ( <список термів> )

    <список термів> :: = <терм> |

    <список термів>, <терм> <терм> :: = <константа> | <змінна> <факт> :: = <предикат> (<список констант>)

    <список констант> :: = <константа> |

    <список констант>,<константа> <мета> :: = <предикат> (<список констант>)

    З представленої граматики видно, що кожне правило може мати кілька умов, з'єднаних логічним «І».

    Розглянемо алгоритм зворотного виведення, який передбачає рух по дереву виведення від мети, і представимо його в «словесній формі».

    Алгоритм зворотного виведення

    При зворотному виведення, або пошуку від мети, розглядається мета, якої потрібно досягти. Аналізуються правила, що ведуть до мети, і визначаються умови їх застосування. Ці умови стають новими цілями, або підцілі, пошуку. Пошук триває в зворотному напрямку від досягнутих подцелей до тих пір, поки ми не досягнемо вихідних даних завдання. Таким чином визначається шлях від

    даних до мети, який насправді будується в зворотному напрямку.

    Алгоритм перевірки вірності мети

    1. Перевіряємо, чи є мета в списку фактів. Якщо є, мета вірна. Якщо немає, перехід до п. 2.

    2. Перевіряємо, чи можна замінити мета будь-яким фактом (предикатний символ факту збігається з предикативним символом мети, кількість термів однаково, якщо в списку термів мети є константи, вони збігаються з відповідними константами в списку термів факту). Якщо мета не можна замінити фактом, перехід до п. 3. Інакше - перехід до п. 4.

    3. Перевіряємо, чи можна вивести мета з будь-якого правила (предикатний символ заголовка правила збігається з предикативним символом мети, кількість термів в списку термів однаково, якщо в списку термів заголовка правила є константи, вони збігаються з відповідними константами в цілі). Якщо мета не можна вивести ні з якого правила, мета невірна. Якщо можна - перехід до п. 3.

    4. Уніфікація і отримання нових подцелей.

    При заміні фактом - заміна всіх термів мети і всіх поточних подцелей відповідними константами знайденого факту.

    При виведенні з правила - заміна всіх термів в заголовку знайденого правила і цих же термів в умовах правила на відповідні терми

    102

    мети. Новими підцілі стають умови правила.

    При цьому для того, щоб вихідна мета була вірна, необхідна істинність всіх поточних подцелей. Якщо одна з подцелей свідомо невірна (див. П. 2 алгоритму), то необхідно повернутися на попередній крок виведення. При цьому пошук за відповідними правилами і фактами триває, починаючи з наступної правил і фактів по відношенню до тих, які вже були розглянуті. Якщо повернення на попередній крок неможливо, початкова мета невірна.

    Розглянемо роботу нашого алгоритму на простому прикладі.

    приклад

    Правила: Факти:

    (1) ад > ад & пекло (1)? (1, 2)

    (2) пекло > «Уд) (2)? (2, 3)

    Мета: (3)? (6, 3)? (1, 6)

    Рішення:

    1. Список цілей:? (1, 6). У списку фактів немає такого факту, мета не можна замінити ніяким фактом, застосовуємо правило (1).

    2. Список подцелей:? (1, г), 6). Розглядаємо першу подцель.

    Можна замінити фактом (1).

    3. Список подцелей:? (1, 2),? (2, 6). Перша подцель вірна. До другої подцели застосовуємо правило (1).

    4. Список подцелей:? (2, г), 6). Розглядаємо першу подцель.

    Можна замінити фактом (2).

    5. Список подцелей:? (2, 3),? (3, 6). Перша подцель вірна. До другої подцели застосовуємо правило (1).

    6. Список подцелей:? (3, г), ДГ, 6).

    При необмеженій кількості рекурсій алгоритм зациклиться, постійно застосовуючи правило (1) до нової отриманої першої підцілі. При обмеженні числа рекурсій при поверненні до кроку 5 і застосуванні до другої подцели правила (2) отримаємо подцель? (6, 3), яку на наступному кроці алгоритм визнає вірною. Все подцели вірні, отже, правильна вихідна мета.

    Програма рішень в задачі визначення переваг

    Ускладнимо решаемую проблему і перевіримо роботу алгоритму в задачі визначення переваг. Розробимо програму, що реалізує алгоритм зворотного виведення. Для цього представимо граматику опису логічних висловлювань у вигляді наступних граматичних конструкцій:

    елементарні рядкові

    константа :: = последовательность_ строчних_букв

    змінна :: = последовательность_ заглавних_букв

    ставлення :: = последовательность_ строчних_букв

    Ці поняття представляють найменші логічні елементи в рядку, що вводиться користувачем з клавіатури. Поняття константа описує постійні значення, що входять до складу правил або фактів. Поняття змінна описує змінні, що входять до складу правил або цільової формули. Поняття відношення визначає формат строкового

    103

    значення для введення відносин між суб'єктами в рамках фактів або правил.

    приклади:

    константа: оля; шоколад; Маша. змінна: X; A; ХТО. відношення: любить; на; батько. аргумент :: = константа | змінна

    Поняття аргумент узагальнює поняття константа і змінна і служить для опису аргументів на правилі бази знань, які можуть бути як константами, так і змінними. спісок_констант :: = константа | константа, спісок_констант спісок_аргументов :: = аргумент | аргумент, спісок_аргументов

    Ці поняття описують відповідні списки з символом коми як роздільник.

    Предикатні формули твердження :: = відношення (спісок_ констант);

    вираз :: = відношення (спісок_аргу-ментів).

    Ці поняття описують найпростіший предикат - набір суб'єктів, пов'язаних ставленням. Тільки суб'єкти поняття твердження задаються константами, а суб'єктами поняття вираження можуть бути як константи, так і змінні.

    приклади:

    твердження: любить (оля, шоколад); батько (вова, олег); вираз: любить (лена, ЩО); батько (X, Y);

    предикат :: = твердження | вираз.

    Поняття предикат узагальнює поняття твердження і вираз і служить для опису предикатів в правилі бази знань, аргументи яких можуть бути як константами, так і змінними.

    набор_предікатов :: = предикат | предикат & набор_предікатов

    Це поняття описує набір предикатів з символом амперсанда як роздільник.

    формула :: = набор_предікатов

    Поняття формула визначається як набір предикатів і служить для завдання цільової формули і умов правил бази знань.

    Об'єкти бази знань

    факт :: = твердження.

    Поняття факт служить для опису факту бази знань і задається рядком затвердження, яка закінчується крапкою.

    приклад:

    любить (маша, цукерки). правило :: = предикат < формула.

    Поняття правило служить для опису правила бази знань і складається з двох частин. Тема (наслідок) правила задається предикатом, а умови - формулою. Як і рядок факту, рядок правила закінчується крапкою.

    приклад:

    на (X, Z) < на (X, Y) & на Z). мета :: = формула ?

    Поняття мета служить для опису цілі зворотного виведення і задає-

    104

    ся цільової формулою. Рядок мети завершується знаком питання.

    приклад:

    любить (маша, ЩО) ?

    Розроблена ієрархія класів програми

    Для проведення синтаксичного аналізу вводяться користувачем даних кожному ключовому поняттю наведеної вище граматики відповідає свій клас. Конструктор такого класу дозволяє створити його екземпляр на основі текстового рядка, який відповідає поняттю граматики. У разі помилки конструктор класу генерує виняток, відповідне типу помилки. Це виняток обробляється основною програмою, що реалізує користувальницький інтерфейс, яка і виводить повідомлення про помилку.

    Деякі класи об'єднують в собі декілька ключових понять граматики, схожих між собою. Наприклад, клас CValue може описувати поняття константа, змінна і ставлення, а клас CPredicate - поняття твердження і вираз. Одним з параметрів конструктора таких класів обов'язково є тип, що задає конкретне поняття.

    На рис. 1 показана ієрархія класів, а також напрямки включень і поняття граматики, описувані конкретними класами.

    Класи, які не описують понять граматики, служать для реалізації синтаксичного розбору і механізму зворотного виведення. Клас CError описує можливі помилки і використовується для створення виключень. Клас CLink описує званих вели-

    Мал. 1. Ієрархія класів та поняття граматики, описувані конкретними класами

    105

    ри пов'язаних змінних і служить для роботи з ними в процесі зворотного виведення. Клас CBase описує всю базу знань як набір фактів і правил, а також реалізує механізм зворотного виведення за заданою цільової формулою.

    синтаксичний аналіз

    Конструктор кожного класу реалізує синтаксичний аналіз рядка, яка описує щось конкретне поняття граматики, яке відповідає даному класу. При цьому він розбирає цей рядок на складові частини відповідно до граматичним визначенням даного поняття і викликає конструктори нижчестоящих за ієрархією класів, передаючи їм відповідні частини аналізованої рядки. приклад:

    Як вже було сказано, на вході конструктора класу, що описує кілька граматичних понять, обов'язково задається тип конструюється примірника. Цей тип задає конкретне граматичне поняття, що дозволяє однозначно визначити алгоритм синтаксичного аналізу отриманої рядка.

    Механізм зворотного виведення

    Механізм зворотного виведення заснований на рекурсивної заміні заданої цільової формули відповідно до фактами і правилами бази знань. Алгоритм такого висновку виглядає наступним чином.

    На першому кроці кожен предикат цільової формули, в якому знаходяться, піддається можливу заміну на відповідний факт бази знань. Нова отримана цільова формула рекурсивно аналізується по точно таким же алгоритмом.

    Після того як всі можливі подібні заміни будуть проведені, для кожного предиката цільової формули шукається відповідне правило бази знань, згідно з яким даний предикат можна замінити послідовністю інших предикатів, що становлять умову правила. Нова формула також рекурсивно піддається точно такою ж процедурою, починаючи з першого кроку.

    Таким чином, будується деякий дерево виведення, яке обходиться у відповідності зі стратегією пошуку в глибину. Цільова формула розбивається на частини, які замінюються новими формулами, істинність яких

    106

    легше встановити в рамках заданих фактів. Процес триває до тих пір, поки цільова формула не перетвориться в аксіому, тобто всі її предикати не стануть тотожно рівними якого-небудь факту бази знань. Якщо ж який-небудь предикат стає неможливо спростити, замінивши його фактом або застосувавши до нього правило, то аналіз такої цільової формули також припиняється, так як вона стає завідомо неправдивої.

    Якщо вихідна цільова формула містила змінні, то будь-яка заміна предиката цієї формули супроводжується запам'ятовуванням відповідних значень для кожної з цих змінних.

    Висота дерева виведення обмежена глибиною рекурсії. У процесі роботи алгоритму дерево виведення обходиться цілком. При обході листя дерева,

    в яких цільова формула перетворюється в аксіому, відбувається запам'ятовування як самої формули, так і множини значень змінних, про які говорилося вище. Ця інформація використовується в якості пояснення результатів виведення.

    Після того як обхід дерева виведення буде повністю завершений, відбувається оцінка результату. Якщо за час виведення не було знайдено жодного перетворення, що перетворює цільову формулу в аксіому, це означає, що дана формула помилкова. Якщо ж такі перетворення знайшлися, то цільова формула істинна, а накопичена в процесі обходу дерева інформація являє собою сукупність пояснень.

    Іншими словами, якщо вихідна цільова формула не містила змінних, то поясненням результату

    Мал. 2. Необхідність уніфікації змінних правила в процесі зворотного виведення

    107

    виведення є тотожна їй цільова формула, яка перетворилася на аксіому в результаті перетворень. Якщо ж в питанні містилися змінні, то, в разі кількох пояснень, до кожного з них додається реалізація сукупності цих змінних.

    Слід зазначити, що при використанні правила для модифікації цільової формули все його змінні уніфікуються шляхом додавання до них номера правила і поточної глибини рекурсії (рис. 2). Це робиться для того, щоб імена пов'язаних змінних не співпали зі змінними вихідної цільової формули або іншими проміжними змінними.

    Використання знака підкреслення унеможливлює для користувача оголошення змінної з таким же ім'ям.

    приклади

    Нехай база даних містить факти:

    1) любить (оля, шоколад);

    2) любить (оля, цукерки);

    3) любить (маша, шоколад);

    4) любить (маша, цукерки);

    5) любить (лена, морозиво);

    6) любить (юля, морозиво) і правило:

    7) ласун (X) < любить (X, Y). Фрагмент робочого вікна програми, що містить дані знання:

    вул

    Нехай цільова формула: ласун (оля) ?

    Тоді дерево виведення буде виглядати наступним чином:

    108

    Так як цільова формула не містила змінних, то, незважаючи на те що в процесі обходу дерева виведення було знайдено два перетворення, що перетворюють цільову формулу в аксіому, як пояснення результату виведення використовується тільки те, яке було отримано першим.

    Фрагмент робочого вікна програми, яка демонструє даний приклад:

    Тепер нехай цільова формула: ласун (КТО)? Отримаємо наступне дерево виведення:

    Слід зазначити, що результатом виведення будуть тільки різні реалізації сукупності змінних вихідної цільової формули. Тобто при отриманні кількох перетворень, що перетворюють цільову формулу в аксіому при одних і тих же значеннях вихідних змінних, як пояснення результату виведення використовується тільки те перетворення, яке було отримано першим.

    Все вищесказане демонструє фрагмент робочого вікна програми, що реалізує даний висновок:

    109

    Тестові приклади роботи програми

    Початкове робоче вікно програми, що містить тестові приклади:

    Демонстрація застосування рекурсивних правил виведення:

    ТЕХНОЛОГІЯ І ПРАКТИКА НАВЧАННЯ 110.........................

    Демонстрація послідовного застосування правил:

    Демонстрація коректного зв'язування змінних:

    Демонстрація виведення за цільовою формулою, що містить кілька змінних:

    Демонстрація виведення за цільовою формулою, що містить кілька змінних, з використанням рекурсивних правил:

    ви&од

    відношення (аргумент, ...) & відношення (аргумент, ..,) Et ...? | На (ДЕ, ЩО] ?

    |; 7Jj | | Істинно

    11 ДЕ = стіл. ЧТО = скатертину; тому на (зганяння, скатертину)

    2]. ДЕ = скатертину, ЩО = тарблка; тому на (скатертина, тарілка]

    3]. ДЕ = тарілка, ЩО | яблуко; тому на (тарілка, яблуко]

    4]. ДЕ = яблуко, ЩО = муна; т.к. на (яблуко, борошно)

    5]. ДЕ = стоячи ЩО - тарілка; тому на [стіл, скатертина) і на (скатертина, тарілка)

    6]. ДЕ = став, ЩО - яблуко; тому на [стіл, скатертина] і на [скатертину, тарілка] і на [тарілка, яблско]

    111

    Розгромна замовна стаття смуга прокрутки дозволяє подивитися всі інші результати, що не помістилися в вікні виводу:

    ви&од

    т відношення (аргумент, ...) & відношення (аргумент,! Et ...? (ДЕ, ЩО]?

    щ \

    істинно.

    6). ДЕ = стіл, ЩО я яблуко; т, до, на (стіл, скатертина) і на (скатертина, тарілка) і на (тарілка, яблуко)

    7). ДЕ = стіл, ЩО = муха; тому на (стіл, скатертина) і на (скатертина, тарілка] і на (тарілка, яблуко) і на (яблуко, муха)

    8). ДЕ = скатертину, ЩО = яблуко; тому на (скатертина, тарілка) і на (тарілка, яблуко)

    9). ДЕ = скатертину, ЩО = муха; тому на (скатертина, тарілка) і на (тарілка, яблуко) і н

    10), ДЕ = тарілка, ЩО = муха; тому на (тарілка, яблуко) і на (яблуко, муха)

    (Яблуко, муха)

    ЛІТЕРАТУРА

    1. Волков І.К., Загоруйко Е.А. Дослідження операцій: навч. для вузів. - 2-е вид. / Под ред В.С. Зарубіна, А.П. Крищенко. - М .: Изд-во МГТУ ім. Н.е. Баумана, 2002.

    2. Мушик Е., Мюллер П. Методи прийняття технічних рішень. / Пер. з нім. - М .: Світ, 1990..

    3. Орловський С.А. Проблеми прийняття рішень при нечітких вихідних даних. - М.: Наука, 1981.

    4. Кіні Р.Л., Райфа Х. ПР при багатьох критеріях переваги і заміщення. - М .: Радио и связь, 1981.

    5. Борисов А.Н. та ін. ПР на основі нечітких моделей. Приклади використання. - Рига: Зинатне, 1990..

    6. Солодовников І.В., Рогозін О.В., Шуру О.В. Реалізація механізму логічного висновку для прототипу експертної системи (ЕС) Нові інформаційні технології: матеріали сьомого науково-практичного семінару. - М .: Моск. держ. ін-т електроніки і математики, 2004.

    7. Саати Т. Прийняття рішень. Метод аналізу ієрархій. - М .: Сов. Радіо, 1993.

    8. Меліхов А.Н., Берштейн Л.С., Коровін С.Я. Ситуаційні радять системи з нечіткою логікою. - М .: Наука, 1990..

    9. Таха Х. Введення в дослідження операцій: В2 т .. - М .: Мир, 1985.

    10. Ермольев Ю.М., Ляшко І.І., Михалевич В.С., Тюптя В.І. Математичні методи дослідження операцій: навч. посібник для вузів. - Київ: Вища школа. Головне вид-во, 1979.


    Ключові слова: ШТУЧНИЙ ІНТЕЛЕКТ / АЛГОРИТМ ЗВОРОТНОГО ВИВЕДЕННЯ / ЕКСПЕРТНІ СИСТЕМИ

    Завантажити оригінал статті:

    Завантажити