Grafice, copaci și rețele
6.1. Grafice, copaci și rețele
Pentru o descriere a multor tipuri de date abstracte în informatică în teoria generală și inteligență artificială, în special, este terminologia utilizată pe scară largă împrumutat de la teoria grafurilor. sunt furnizate următoarele definiții aici pentru a arăta modul în care acești termeni împrumutate sunt interpretate în descrierea obiectului structurat, care este oarecum diferit de tratamentul lor în „nativ“ a câmpului matematic.
Fig. 6.1. Unele tipuri de grafice: a) grafic obișnuit; b) să fie un grafic conectat cu o buclă; c) ordinare grafic regia - arbore
Toate definițiile sunt formulate pe presupunerea că există două tipuri de noduri - primitivele si link-uri. Nodurile sunt punctele de ieșire și țintă pentru obligațiuni și, de obicei, într-un fel marcate. Comunicarea poate fi, de asemenea, marcate, dar nu neapărat. Totul depinde de faptul dacă avem de-a face cu conexiuni de un fel sau diferite. În terminologia uzuală a nodurilor teoria grafurilor sunt numite „noduri“, și de comunicare - „Count margini“, sau „arce“.
Definiția 6.1. Dacă N-set nod, atunci orice subset de NxN este un grafic generalizat G. Dacă subsetul comanda perechilor are o valoare N x N, atunci graful G este direcționat.
Fig. 6.1 prezintă diferitele tipuri de grafice. Rețineți că graficul nu trebuie să fie conectat. În cazul în care condiția predeterminată este faptul că buclele nu sunt permise, și anume, în fiecare pereche trebuie să fie prezente noduri diferite, atunci acest grafic se numește obișnuit. În cazul în care coloana nu este permisă nu numai buclele, ci și cicluri (de exemplu, comunicație serială, în care pornirea și nodurile se termină sunt aceleași), atunci un astfel de grafic se numește o pădure.
Definiția 6.2. Dacă G- grafic obișnuit în care există n noduri și n-1 conexiuni, și nu există cicluri, atunci acest grafic este un copac.
Cu alte cuvinte, copac - o pădure conectat. De obicei, unul dintre arborele este un nod de rădăcină, de exemplu, nodul e în graficul prezentat în Fig. 6.1 in. Nodurile rămase formează o structură de ramificare „succesorii“ ale nodului rădăcină, în care nu există bucle. Site-urile care nu au moștenitori sunt terminale sau „frunze“ ale copacului, în timp ce celelalte noduri sunt numite intermediare (non-terminal).
În teorie, graficul de rețea se numește un grafic direcționat ponderat, adică, grafic în care fiecare link mapat la un anumit număr. De obicei, aceste numere sunt estimate „costul“ al modului de-a lungul lungimii legăturii sau conexiunea, pe foaia de parcurs. În fiecare caz particular de aplicare ca un grafic care descrie mijloace formale ale acestor probleme pot fi tratate în mod diferit.
Următoarea definiție a rețelei mai aproape de problemele specifice ale inteligenței artificiale, pe care acum angajate.
Definiția 6.3. Dacă L - este un set de conexiuni ponderate, o grupare N, anterior, o multitudine de noduri, rețeaua - este orice subset NxLxN, care are o valoare în ordinea triade.
Rețelele de comunicare sunt aproape întotdeauna concentrate, deoarece relația reprezentată de conexiuni ponderate, nu ar trebui să fie simetrice.
Graficele obișnuite sunt folosite pentru a reprezenta relațiile dintre obiecte în spațiu sau timp. Le puteți utiliza pentru a reprezenta relații cauzale mai abstracte, cum ar fi relațiile dintre diferitele tipuri de patologii în medicină (fig. 6.2). Accesul la astfel de informații în legătură cu o anumită măsură prin utilizarea mijloacelor speciale de urmărire trasee pe grafic, care sunt concepute pentru o varietate de algoritmi (vezi. De exemplu, locul de muncă [Pearl, 1984]).
Fig. 6.2. parte a rețelei de cauzalitate ([Pople, 1982P
Pentru prezentarea clasificărilor și a rețelelor ierarhice utilizate copaci. De exemplu, în Fig. 6.3 Clasificarea bolilor prezinta un copac de pe locul organului afectat. Nodul rădăcină al arborelui reprezintă mulțimea tuturor bolilor și succesorii săi - grupuri de boli de organe afectate primară corespunzătoare. Fiecare dintre aceste unități vor fi moștenitorii lui, reprezentând grup mai restrâns de boli, etc. Nodurile terminale ale arborelui va reprezenta o anumită boală.
rețele semantice au fost folosite pentru prima dată pentru a reprezenta semnificația expresiei limbajului uman natural, din care a venit numele acestei clase de rețele. Acum, ele sunt folosite ca o structură adecvată pentru a reprezenta tipurile generale de informații - unele dintre nodurile reprezintă concepte (concepte), și de comunicare - relații între concepte. Fig. 6.4 prezintă două bucăți de web-ul semantic. Primul fragment este verbul a da, și arată că verbul poate avea trei tipuri de interacțiune cu restul ofertei: cu donatorul, beneficiarul și obiectul care urmează să fie transmis. Inscripții în nodurile la care abordare de comunicare, să corespundă clasei de entități care pot acționa ca entități de comunicare. Astfel, donatorul și primitorul, de obicei-oameni, și ceea ce aveți nevoie pentru a trece - un lucru.
Fig. 6.3. Clasificarea lemnului ordinară a bolilor
Fig. 6.4. Fragmente ale web-ului semantic: a) Prezentarea verbul „a da“; b) prezentarea unei acțiuni specifice
Al doilea fragment care corespunde unei anumite fraze sau măsuri specifice de executare, a spus acest verb. Această implementare am numit da-265. Sensul expresiei este că Ioan transmite Maria cartea „Război și Pace“. Fraza poate fi considerată admisibilă, întrucât toți membrii săi satisfac constrângerile specificate de nodurile rețelei respective. Ioan și Maria aparține unei clase de oameni, „Război și pace“ - o carte la clasa, care, la rândul său, este un tip de lucruri de clasă.
In mod normal, dând nod-265 este asociat cu nodul pentru a da legătură, ceea ce indică faptul că emanații 265 - este una dintre realizările concrete ale conceptului (în acest caz, acțiunea) pentru a da. Acest tip de conexiune specială este adesea numită ISA-obligațiuni (cum ar fi „este.“).
Termen de rețea asociativă reflectă mai bine natura utilizării unor astfel de structuri formale pentru provocările pe care le au in vedere. Deoarece dispozitivul rețele asociative sunt tot mai folosite pentru a modela obiecte și relațiile lor într-un anumit domeniu, care este necesară pentru construirea de sisteme expert, mai jos ne uităm la ele mai în detaliu.