Графики, дървета и мрежи
6.1. Графики, дървета и мрежи
За описание на много видове абстрактни данни в компютърната наука като цяло и изкуствен интелект теория, по-специално, той е широко използван терминология назаем от теория на графите. Осигурени са следните дефиниции тук, за да се покаже как тези привлечени термини се тълкува в описанието на структуриран обект, който е малко по-различен от лечението им в "родния" от областта на математическия.
Фиг. 6.1. Някои видове графики: а) обичайни графиката; б) да бъде свързан граф с контур; в) обикновен насочено графика - дърво
Всички определения са формулирани на предположението, че има два вида примитиви - възли и връзки. Възлите са изходящи и целеви точки за облигации и обикновено по някакъв начин маркирани. Комуникацията може да бъдат маркирани, но не е задължително. Всичко зависи от това дали ние се занимаваме с връзки от един вид, или по-различно. В обичайния терминологията на графиката теория възли се наричат "възли", и съобщението - "Брой ръбове", или "дъги".
Определение 6.1. Ако N- възел зададена, тогава всяка подгрупа на NxN е обобщена диаграма Г. Ако подгрупата NxN двойки поръчат има стойност, тогава графиката G е насочено.
Фиг. 6.1 показва различните видове графики. Имайте предвид, че графиката не трябва да бъдат свързани. Ако предварително определено условие е, че примките нямат право, т.е. във всяка двойка трябва да присъстват различни възли, тогава тази графика се нарича обикновено. Ако колоната не се допуска не само вериги, но и цикли (т.е. серийна комуникация, в която началната и крайната възли са едни и същи), след като графика се нарича гора.
Определение 6.2. Ако G- обикновена графика, в която има п възли и N-1 връзки, и няма цикли, тогава тази графика е дърво.
С други думи, на дървото - свързан гора. Обикновено, един от дървото е корен възел, например възлова точка е в графиката, показана на фиг. 6.1 инча Останалите възли образуват разклоняване структура "приемници" на корен възел, в които няма цикли. Сайтове, които нямат наследници са крайни или "листа" на дървото, докато другите възли се наричат междинно съединение (не-терминал).
На теория графиката мрежа се нарича претеглените насочено графика, т.е. графика, в която всяка връзка съпоставена с определен брой. Обикновено, тези цифри се изчисляват "цена" за начина, по дължината на връзката или връзката, на пътната карта. Във всеки конкретен случай на приложение като графика, описваща официални посредством тези проблеми могат да бъдат третирани по различен начин.
Следното определение на мрежата по-близо до специфичните проблеми на изкуствен интелект, които сега ние сме ангажирани.
Определение 6.3. Ако L - е набор от претеглят връзки, с N, по-горе, множество възли, мрежата - е всяка подгрупа NxLxN, която има стойност от порядъка на триади.
Комуникационна мрежа са почти винаги съсредоточени, защото връзката представлявана от претеглени връзки, не трябва да бъде симетричен.
Обикновените графики се използват за представяне на връзките между обектите в пространството или времето. Можете да ги използвате, за да представят по-абстрактни причинно-следствени връзки, като например отношенията между различните видове патологии в медицината (фиг. 6.2). Достъп до тази информация, свързана с известна степен чрез използване на специални средства за проследяване на пътя на графиката, които са предназначени за различни алгоритми (вж., Например, работи [Pearl, 1984]).
Фиг. 6.2. част от мрежата на причинно-следствената връзка ([Pople, 1982P
За представяне на йерархични класификации и мрежи се използват дървета. Например, на фиг. 6.3 класификация на болестите показва едно дърво на местоположението на засегнатия орган. Коренът възел на дървото представлява набор от всички болести и следващите - болестни групи съответния първичен засегнатия орган. Всеки един от тези елементи ще бъдат неговите наследници, които представляват по-тясна група от заболявания, и т.н. Крайните възли на дървото ще представляват специфично заболяване.
Семантичните мрежи за първи път са използвани за представяне на значението на израза на естествения човешки език, от който са произлезли името на този клас мрежи. Сега те се използват като структура, подходяща за представяне на общите типове информация - някои от възлите представляват концепции (понятия), както и за комуникация - отношения между понятия. Фиг. 6.4 представя две парчета от семантичната мрежа. Първият фрагмент е глаголът да се получи, и показва, че глаголът може да има три вида на взаимодействие с останалата част на офертата: с донора, на реципиента и обекта, който трябва да бъде предаден. Надписи във възлите за които комуникация подход, съответстват на клас от лица, които могат да действат като комуникационни единици. По този начин, донора и реципиента, обикновено хората-, и това, което трябва да мине - нищо.
Фиг. 6.3. Обикновените дърво класификация на болестите
Фиг. 6.4. Фрагменти от семантичната мрежа: а) Подаване на глагола "да даде"; б) представяне на конкретно действие
Вторият фрагмент, съответстващ на конкретно фраза или специфични стъпки за изпълнение, споменатата този глагол. Това изпълнение се обадихме дават-265. Смисълът на фразата е, че Джон предава Мери книгата "Война и мир". Фразата може да се разглежда като допустимо, тъй като всички свои членове да отговарят на ограниченията, определени от съответните мрежови възли. Джон и Мери принадлежи към класа на хора "Война и мир" - една книга към класа, която, от своя страна, е вид клас неща.
Обикновено, като възел 265 е свързан с възел за получаване на връзка, което показва, че даването-265 - е един от конкретни реализации на понятието (в този случай действието), за да даде. Този вид специална връзка често се нарича ISA-връзка (като например ", че е.").
Срок асоциативна мрежа отразява по-добре характера на използването на такива формални структури за предизвикателствата, пред които ние се обмисля. Тъй като устройството асоциативни мрежи все повече се използват за моделиране на обекти и техните взаимоотношения в определена област, която е необходима за изграждане на експертни системи, по-долу ги погледнем по-подробно.