Методът на най-бързото изкачване (

Последният метод за евристично търсене е търсене с минимизиране на общата цена на пътя (А*). Той може да се разглежда като частен случай на метода на най-доброто спускане, при който се използва специална оценяваща функция. Тази функция се получава като сума на два компонента – точен компонент, който дава цената на изминатия път от началния възел до оценявания връх и евристичен компонент, който дава приблизителна стойност на цената на оставащата част от пътя от оценявания връх до целевия връх. Методът е пълен дори при безкрайни графи (естествено, с крайна разклоненост), стига теглата на ребрата в графа да са положителни и е оптимален, ако евристичната компонента в оценяващата функция е приемлива, т.е. никога не надценява действителната оптимална цена на оставащата част от пътя от оценявания връх до целевия връх.

В частния случай когато евристичната компонента е 0 получаваме неинформиран метод за търсене, който се нарича търсене с равномерна цена на пътя (uniform cost search). Той винаги е оптимален и е пълен за безкрайни графи, ако теглата на ребрата са положителни.

Сега ще опишем реализация на всички описани методи на Prolog.

Графът отново представяме както по-горе. Евристичната функция се описва с факти от вида distance (Node, Goal, D) – означава, че евристичната оценка на възела Node на оставащата част от пътя до възела Goal е D.
best_first ([[Goal|Path],_], Goal, FinalPath) :–

reverse ([Goal|Path], FinalPath).

best_first ([Path|List], Goal, FinalPath) :–

extend (Path, NewPaths),

append (NewPaths, List, NewList),

sort (NewList, Goal, SortedList),

best_first (SortedList, Goal, FinalPath).

sort ([], _, []).

sort (L, Goal, [MinPath|SortedL]) :–

min (L, MinPath, Goal, LeftL),

sort (LeftL, Goal, SortedL).

min ([P|List], Q, Goal, [P|List1]) :–

min (List, Q, Goal, List1),

h (P, Goal, HP), h (Q, Goal, HQ),

HP > HQ, !.

min ([P|List], P, _, List).

h ([Node|Path], Goal, H) :– distance (Node, Goal, H).

Предикатът best_first реализира метода на най-доброто спускане. Реализацията на extend е както по-горе. Предикатът sort сортира списъка от пътища, предаден като първи аргумент по метода на пряката селекция. Той има допълнителен аргумент целевият възел Goal, тъй като той участва при изчисляване на евристичните оценки (функцията h).

trim (Beam, SortedList, SortedList1)

и първият аргумент на последващото извикване на best_first се променя от SortedList на SortedList1. Предикатът trim се реализира по следния начин:

trim (N, [X|L], [X|L1]) :– N > 0, !, N1 is N-1, trim (N1, L, L1).

trim (_, _, []).
Предикатът a_star, който реализира търсене с минимизиране на общата цена на пътя се реализира аналогично на предиката best_first с една разлика: в дефиницията на предиката min, редът

h (P, Goal, HP), h (Q, Goal, HQ),

се заменя с реда

f (P, Goal, FP), f (Q, Goal, FQ).

Предикатът f се дефинира така:

f ([Node|Path], Goal, F) :–

reverse_path_cost ([Node|Path], G),

distance (Node, Goal, H),

F is G+H.

reverse_path_cost ([A, B], Cost) :– arc (B, A, Cost), !.

reverse_path_cost ([A, B|Path], Cost) :–

arc (B, A, Cost1),

reverse_path_cost ([B|Path], Cost2),

Cost is Cost1+Cost2.

За да получим неинформираният метод за търсене с равномерна цена на пътя, променяме само реализацията на f:

f ([Node|Path], Goal, F) :–

reverse_path_cost ([Node|Path], F).
И накрая описваме предикатът hill_climbing, който реализира методът на най-бързото изкачване.
hill_climbing ([Goal|Path], Goal, FinalPath) :–

reverse ([Goal|Path], FinalPath).

hill_climbing (Path, Goal, FinalPath) :–

extend (Path, NewPaths),

bestpath (NewPaths, Goal, BestPath),

betterpath (BestPath, Path, Goal, BestPath),

hill_climbing (BestPath, Goal, FinalPath).

bestpath ([P], _, P) :- !.

bestpath ([P|Rest], Goal, Q) :–

bestpath (Rest, Goal, P1),

betterpath (P, P1, Goal, Q).

betterpath ([Node1|P1], [Node2|P2], Goal, [Node1|P1]) :–

h (Node1, Goal, H1), h (Node2, Goal, H2),

H1 < H2, !.

betterpath (_, P, _, P).
Знанията и данните изразяват две страни на категорията информация. Знанията са общата, относително постоянната и неизменяема част от информацията. Данните са по-динамичната част и могат да се разглеждат като допълнение на знанията, тъй като носят конкретна информация за всеки обект. Рязка граница между данни и знания не съществува – не съществуват чисти знания и чисти данни. Това, което е знания в един момент от работата на системата, може да е данни в друг момент, както и данните могат да се интепретират като знания в определени случаи. Основните различия между данните и знанията в системите с изкуствен интелект са:

• 
  различие в степента на общност и постоянност/изменяемост;
  
• 
  различие в начина на ползване;
  
• 
  наличие на класификационно-йерархична структура на знанията, основана на родово-видови отношения от тип обект-клас, клас-суперклас, тип-подтип, ситуация-подситуация и т.н.
  

1. 
   Знания за обектите и фактите в предметната област (фактологически знания от най-ниско равнище).
   
2. 
   Знания за връзките (отношенията, релациите) между обектите и фактите в предметната област.
   
3. 
   Метазнания на много равнища (знания за самите знания, за структурата им, за връзките между тях, за начините на използването им и т.н.).
   

Всеки формализъм за представяне на знания може да бъде разгледан в два аспекта: синтактичен и логически. Синтактичният аспект се отнася до начина, по който явно зададените знания се съхраняват в системата, а логическият аспект до начина, по който явно зададените знания могат да се използват, за да бъдат извлечени допълнителни знания, които неявно се съдържат в тях.

Съществуват два основни типа формализми за представяне и използване на знания: формализми от процедурен (алгоритмичен) тип и формализми от декларативен тип. Основната разлика между двата типа формализми се свежда до това дали знанията са представени във вид, който позволява лесен и естествен отговор на въпроса какво? (декларативни формализми) или са във вид, който позволява лесен и естествен отговор на въпроса как? (процедурни формализми). При декларативните формализми основна тежест пада върху представянето на знанията. При процедурните формализми съществен е начинът на използване на знанията. При декларативните формализми знанията се представят явно, в декларативен формат, а при процедурните те се съдържат в процедурите на някаква програмна система. При процедурното представяне не съществуват толкова обособени база знания и интерпретатор, както е при декларативното представяне. Процедурните формализми дават възможност за по-голяма ефективност при използването на знанията, но при тези формализми измененията на знанията се правят по-трудно.
Първият формализъм за представяне и използване на знания, който ще разгледаме е представяне и използване на знания чрез процедури. Това е един типичен процедурен формализъм.

Знанията се представят чрез системи от малки по обем процедури-демони, в които са кодирани знания за определени характерни ситуации и всяка от които се активира сама при настъпване на съответната ситуация. Обикновено демоните са от изчислителен характер и например пресмятат релации. За базите от въпросните процедури-демони е типична хетерархична структура, за разлика от процедурите в стандартните програмни системи.

При създаването на една процедура, в нея трябва да се вложат знанията за конкретна ситуация и да се създадат необходимите връзки с останалите процедури от базата знания. За разлика от декларативните представяния, където знанията и връзките между тях са разделени, тук както самите знания, така и връзките са заложени в процедурите. Знанията се изразяват чрез семантиката на процедурите, а връзките между тях, чрез връзки между отделните процедури, т.е. чрез обръщения между процедури и предаване на параметри. Изменението на знанията е основен проблем при този формализъм. Изменението само на една процедура може да доведе след себе си до необходимост от изменение на голяма част от процедурите на системата (например, при добавяне на допълнителен параметър на процедура). Добавянето на нови процедури от своя страна не се изчерпва с механичното им долепяне към базата от знания, а води до изменението на редица от съществуващите процедури, за да се създадат необходимите връзки.

Основните предимства на този формализъм са неговите относително по-високи ефективност и бързодействие, което се дължи на факта, че управлението се предава директно от процедура на процедура в зависимост от текущите данни. Директните връзки, които са обръщения към други процедури са заложени в самите процедури, което води до директен извод.

Формализмът чрез процедури предоставя редица удобства при моделирането на процеси, тъй като дадена ситуация се обработва от конкретна процедура и управлението се предава директно точно на тази процедура, която притежава знания за съответната ситуация. Този формализъм е много удобен и при представяне на евристични знания. От друга страна, връзките са относително принудителни, което води до липса на модулност в системата и до трудности в управлението на процеса отвън. Друг недостатък е, че трудно се реализират системи за обяснение на резултата. Представянето и използването на знания чрез процедури има голямо приложение при управление на роботи, управление на процеси и др., където преобладават алгоритмичните знания.
Вторият формализъм, който разглеждаме е представяне и използване на знания чрез средствата на математическата логика. Това е един от най-рано възникналите формализми с ясно изразен декларативен характер. Представянето на знанията в термините на дадена формална логическа система се извършва с помощта на правилно построените формули в тази система, а използването на знанията се осъществява посредством валидните за логическата система правила и методи за извод. Най-често използваната формална логическа система е предикатното смятане от първи ред. Съществените му недостатъци са неговата полуразрешимост и недостатъчната му изразителна сила. Полуразрешимостта означава, че съществува алгоритъм, който с помощта на краен брой стъпки определя дали една формула е логическо следствие на краен брой други формули, ако въпросната формула действително е следствие, но не съществува подходящ краен алгоритъм за получаване на отрицателния отговор.

Изразителната сила е недостатъчна, тъй като в системите от първи ред кванторите се отнасят само за променливи (пробягват само елементите на универсума), но не и за функции (или произволни релации). За преодоляване на този проблем могат да се използват логики от по-висок ред. Друга особеност на предикатното смятане от първи ред е неговата монотонност – в процеса на логически извод могат само да се добавят формули към началното множество, но не и да се изключват. Това свойство пречи да се задават знания или свойства, които се смятат за верни по премълчаване, т.е. знания, които се смятат за верни, докато не стане известно противното. За представяне и използване на знания, които се смятат за верни по премълчване, се използват специален тип логики, наречени немонотонни логики. В случаите на представяне на знания, които се променят във времето могат да се използват темпорални логики. Общият вид на правилно построените формули от предикатното смятане от първи ред затруднява представянето с тяхна помощ на твърдения, които съдържат модалности от типа необходимо, възможно, случайно, невъзможно и др. За представянето на такива твърдения се използват модални логики. Често в практиката се работи с твърдения, които съдържат неточни определения като много, малко, повечето и др. Неточни знания от този тип обикновено се представят с помощта на размита логика. Най-същественото предимство на логическите системи е ясната семантика.

Всяка система с изкуствен интелект, основана на правила има три основни компонента: работна памет, база от правила и интерпретатор на правилата.

Работната памет (контекст) съдържа данните за решаваната задача, установени към текущия момент. Тези данни се формират от два източника. Първият източник е потребителя – той вмъква първоначалните данни в системата или вмъква допълнителни данни като отговор на допълнителен въпрос на системата. Вторият източник е интерпретатора на правилата – в зависимост от неговата реализация могат както да се вмъкват междинни резултати от логическия извод, така и да се изключват или модифицират съществуващи данни от работната памет. Представянето на данните в работната памет зависи от синтаксиса на правилата и най-често то е чрез тройки от вида обект-атрибут-стойност (например, тройката (A, B, C) означава, че обектът A има атрибут B със стойност C) или чрез тройки от вида атрибут-релация-стойност (например, тройката (A, R, B) означава, че стойността на атрибута A е в релация R със стойността B).

Базата от правила е съвкупност от правила за дадена предметна област, които са наредени по определен начин. Общият вид на правилата е следния: (if <условие1> <условие2> …<условиеN> then <следствие1> <следствие2> … <следствиеM>). Семантиката на правилата е следната: ако условията са вярни, то са вярни и следствията.

Интепретаторът е машината за извод на съответната система. Това е програмна система, чиято основно предназначение е да приложи вложените в правилата знания в системата върху данните за конкретната задача. Често интерпретаторът се използва за да направи опит да удоволетвори някаква зададена от потребителя цел. Условно работата му може да се раздели на две фази: избор на правило и изпълнение на правилото. По същество задачата в първата фаза се свежда до търсене в базата от правила по някакъв образец. Според образеца на търсене се различават два типа системи от продукционни правила – прави и обратни.

В зависимост от това също се говори за два типа алгоритми за действие на интерпретатора – прав извод (извод, управляван от данните) и обратен извод (извод, управляван от целите).

При първия тип системи, интерпретаторът в първата фаза от работата си търси правило, чиито условия се удоволетворяват от наличните данни в контекста, след което във втората фаза изпълнява следствията на намереното правило. Ако съществува повече от едно правило, чиито условия се удоволетворяват от контекста (т.е. трябва да се извърши конфликтна резолюция), се използват различни методи за избор на правило (например: първото срещнато правило; правило, което не е прилагано до момента; правило, което използва най-скоро записани в контекста данни). Изпълнението на следствията на правилото води до изменение на контекста, което от своя страна прави възможно изпълнението на друго правило, ако не е достигната съответната цел и т.н.

При втория тип системи, търсенето се извършва върху следствията на правилата, като за образец служи някаква зададена цел. След това се анализира лявата част на намереното правило, като неизвестните все още параметри се задават като нови цели. След това се прави опит да се удоволетворят по аналогичен начин новите цели и т.н. Този процес продължава, докато текущите цели се удоволетворят от данните в контекста или докато стане ясно, че те не могат да бъдат удоволетворени. При необходимост се извършва връщане назад, докато се удоволетворят целите или се изследват всички неизследвани възможности.

Основните предимства на системите с продукции са няколко.

Първото предимство е естественост на представянето на експертни знания, което ги прави широко приложими при изграждането на експертни системи.

Второто предимство е е модулност, която се изразява в няколко аспекта – постоянните знания са отделени от временните (първите са в базата от правила, вторите са в работната памет), различните правила са семантично независими, единственият начин по който правилата общуват е свързан с промяната на съдържанието на работната памет, интерпретаторът работи независимо от смисъла на знанията и данните, които са кодирани в базата от правила и в работната памет.

Третото предимство на системите с продукции е ограниченият синтаксис, въпреки че по-нататък ще посочим и някои недостатъци, които произтичат от него. Ограниченият синтаксис позволява лесно да се изграждат програми-редактори на системи от продукции и лесно да се реализират средства за генериране и обяснение на резултата на естествен език.

Съществуват и недостатъци на системите с продукции.

Всъщност, въпреки че системите с продукции дават възможност за обясняване на резултатите от извода, в тяхния класически вид има видове знания като стратегическите и поддържащите знания, които не могат да се представят в явен вид в базата от правила, което понякога прави генерираните обяснения недостатъчно съдържателни.

Друг недостатък, който произтича от ограничения синтаксис е невъзможността за представяне на дизюнктивни знания в следствията и на отрицателни знания въобще (освен в някои специални частни случаи).

Последният недостатък е, че съществува потенциална неефективност на работата на интерпретатора, източникът на която са определянето на конфликтното множество от правила и изборът на правило от него (конфликтна резолюция).

За преодоляване на този недостатък има различни подходи – уточняване на условията в правилата, пренареждане и ограничаване на конфликтното множество и използване на архитектура от тип “черна дъска”.
Четвъртият формализъм, който разглеждаме е представяне и използване на знания чрез семантични мрежи. Това е декларативен формализъм и спада към класа на структурните формализми, при които знанията се представят чрез множество от структурни единици, свързани помежду си чрез явно зададени връзки, подобно на организацията на знанията в човешкия мозък.

В семантичните мрежи знанията се представят с помощта на мрежа от възли и дъги, които ги свързват (с други думи семантичната мрежа е ориентиран граф). Възлите обозначават обектите (понятията, класове и т.н.) от предметната област. Дъгите представляват връзките (отношенията, релациите) между обектите. Възлите са два вида – релационни константи, които представляват таксономични категории или стойности на свойства и обектни константи, които представят предмети или обекти от предметната област. Връзките са три вида – връзки от тип “подмножество”, които описват релации от тип клас-суперклас, връзки от тип “елемент”, които описват релации от тип обект-клас и връзки тип “функция”, които описват свойства на обектите и класовете.

Изрично ще отбележим, че дъгите изразяват бинарни отношения между възлите.

Използването на знания, представени чрез семантични мрежи обикновено е свързано с извършване на изводи за обектите и намиране на техни свойства, които не са представени в явен вид. Основният механизъм за извод върху семантична мрежа е свързан с проследяване на връзките между отделните възли в мрежата. Най-често се използват две стратегии за извод: разпространяваща се активност и наследяване.

Най-съществените предимства на семантичните мрежи са простота, естественост, нагледност и яснота на представянето.

Семантичните мрежи имат доста недостатъци.

Първият недостатък е трудности при представянето на произволни n-арни релации. Този недостатък може частично

(с цената на нарушаване на предимствата) да се избегне, например чрез метода на Саймънс. При него за n-арната релация се въвежда отделен възел и обектите-аргументи на релацията се свързват към новия възел с бинарни връзки.

Друг недостатък е трудности при представянето на знания, които съдържат квантори. И тук има решения, например използването на разделени семантични мрежи, но отново се нарушава простотата и естествеността на представянето. Разделената семантична мрежа е йерархична съвкупност от подмрежи, всяка от които съответства на областта на действие на една или няколко променливи. Някои специални дъги в мрежата сочат не към възли, а към цели подмрежи.

Трети недостатък е неясната семантика – една семантична мрежа често може да бъде тълкувана по различни начини.

Четвърти недостатък са проблемите, които възникват при извършването на различни операции върху семантичните мрежи – например, дублиране на информация за съвпадащи обекти при обединяване на две семантични мрежи.

И последен недостатък са проблемите при управляване на наследяването – не винаги е целесъобразно да се извършва наследяване на свойства, а трудно се задава частична забрана за наследяване.

От информационна гледна точка, фреймът представлява йерархична структура от данни с три равнища. На най-високо равнище стои идентифициращата информация, която обикновено включва името на фрейма. На следващото равнище се съдържат полета с описания на различни характеристики, качества или свойства на обекта или класа обекти, представян от фрейма (слотове или атрибути). На най-ниско равнище се намират фасетите. Всяка фасета се прикрепя към някой слот и се използва за записване на допълнителни данни за описваната в слота характеристика. Най-често използваните имена на фасети са:

• 
  value – съдържа стойността на характеристиката, описвана от съответния слот;
  
• 
  default – съдържа стойността по премълчаване (която се използва, ако във value не е зададена конкретна стойност) на характеристиката, описвана от съответния слот;
  
• 
  if-needed – съдържа име или тяло на процедура, която да се изпълни при изчисляване на стойността на характеристиката, описвана от съответния слот, ако тази стойност не е дадена в явен вид и не се подразбира;
  
• 
  if-added (if-removed) – съдържат имена или тела на процедури, които се активират, ако бъде добавена (изтрита) стойност на съответната характеристика.
  

най-важна роля играе слотът с примерно име a-k-o (a kind of). Фасетата value към този слот съдържа списък от имена на фреймове, описващи класовете (суперкласовете), към които се причислява обектът (класът), описван от дадения фрейм.

Използването на знанията, представени чрез фреймове, се свежда най-вече до две основни дейности: съпоставяне с дадено описание и логически извод.

При първата дейност, целта е по дадено описание на някаква ситуация да се намерят съществуващи в базата от знания фреймове, които съответстват в задоволителна степен на това описание.

Втората дейност се свежда до наследяване на свойства от класовете, към които принадлежи даден обект (клас).

Ако ни интересува стойността, свързана с даден слот на даден фрейм, можем най-напред да потърсим тази стойност последователно във фасетите value, default и if-needed на дадения слот. Ако и на трите места не открием нищо подходящо, можем да използваме йерархията между фреймовете, дефинирана чрез слотовете a-k-o. В слота a-k-o на дадения фрейм е записано името на съответния суперфрейм и търсенето може да продължи в съответните фасети на суперфрейма, след това – при суперфрейма на суперфрейма и т.н. Възможно е слотовете a-k-o на някои фреймове да са записани имената на повече от един суперфрейм. Така в общия случай, предходниците на един фрейм образуват дърво и при търсене трябва да се възприеме някаква стратегия за обхождане на това дърво (например, в широчина или в дълбочина). Независимо от тази стратегия, търсенето на необходимата стойност може да се извършва по два начина:

Z-търсене и N-търсене.

При Z-търсенето, най-напред се обхождат фасетите value, default, if-needed на разглеждания слот на дадения фрейм, след това се преминава към първия предходник на фрейма (съгласно стратегията за обхождане на предходниците) и за същия слот на този фрейм се преглеждат отново трите въпросни фасети и т.н.

При N-търсенето най-напред се преглеждат фасетите value на дадения фрейм и на всички негови предходници, след това се преглеждат фасетите default на фрейма и на всички негови предходници и най-накрая се преглеждат фасетите if-needed на фрейма и на всички негови предходници.

Основните предимства на фреймовете са естественост на представянето, модулност и йерархична структура на базата от знания и добри възможности за използване на свойства, които са валидни по премълчаване.

A^t = A  _ij = _ji за всеки i, j  { 1, 2, …, n}.

A.A^t = E  A е обратима и A^-1 = A^t.