programare euristic, aideus

Până în momentul de apariția calculatoarelor date de psihologie, etnologie, psihologie animală, pedagogie și metodologia științei împrăștiate a arătat că inteligența este convenabil atât capacitatea de a rezolva probleme (problema), precum și soluțiile de proces (de gândire) este implementată ca o căutare pentru un șir de acțiuni care începe situația (starea problemei) va fi tradus la situația finală (răspuns). Pornind de la un anumit nivel de dezvoltare a organismelor vii, prea multă acțiune prin executarea lor efectivă se înlocuiește cu o forță brută „virtuală“ „pliat“ acțiune. În matematică, la acel moment, pentru a descrierea riguroasă a raționamentului corect a fost formalizat conceptul de algoritm este implementat în funcție de secvența de date de intrare și descrie soluția problemei în termeni generali. Calculatoarele au fost create ca aparatul efectuează automat algoritmi, adică. E. Pentru a rezolva problemele prezentate într-o formă simbolică. Cu toate acestea, întrebarea cheie rămâne: cum să găsească algoritmii sau cel puțin un lanț liniar de acțiuni succesive? Din cauza NP-completitudinii, sau chiar problemă generală unsolvability de a găsi o listă completă a tuturor opțiunilor este, în multe cazuri, imposibil.

Potrivit lui Polya, omul este capabil într-un fel de a depăși această problemă prin utilizarea euristica - metode care să faciliteze rezolvarea problemelor. Dar este posibil să se programeze o euristică? Și, dacă este posibil, sub ce formă ar trebui să fie făcut? Oamenii de știință încearcă să răspundă la aceste întrebări a dus la 1950-60-e la apariția unei prime paradigme de inteligență artificială, numită „programare euristică.“ În domeniul AI de la începuturile sale, există multe domenii diferite de cercetare, dar este programarea euristică poate fi descrisă ca prima încercare de a crea o teorie cu adevărat generală a inteligenței artificiale.

Inteligența artificială problemă de programare euristică adesea studiat pe exemplul de jocuri intelectuale, cum ar fi dame, șah, t. D. Pe de o parte, „universul“ de orice joc de masă este dat un mic set de reguli foarte simple, care sunt ușor de programul. Pe de altă parte, în timpul jocului, cum ar fi șah, cu siguranță, este necesar să se gândească. Sarcini dovedesc teoreme matematice și sarcinile de planificare sunt, de asemenea, pe larg studiate în programarea euristic, dar au nevoie de cunoștințe de domeniu suplimentar (de exemplu, pentru a explica drepturile omului ale jocului de șah este mult mai simplu decât regulile de integrare) și au fost mai puțin demonstrativă și mai complexe pentru a pune în aplicare. Să încercăm să se uite la gândire mai întâi problema pentru un joc simplu.

Următoarele considerații pot părea neînsemnate, din cauza faptului că o metode bine cunoscute și mai sofisticate. Dar imaginați-vă în locul de pionieri, care absolut nimic nu a fost încă cunoscut și a fost nicăieri să împrumute soluții gata făcute. Acest lucru va ajuta să înțeleagă mai bine cauzele și dezvoltarea domeniului programării euristice și a cercetării inteligenței artificiale, în general. Într-adevăr, printre soluțiile obișnuite gata făcute pot fi mai aleatoare și nu optimă, și, prin urmare, o idee bună de a revizui rezultatele vechi, în contextul mai larg al ideilor moderne.

Să sarcina noastră este de a preda un calculator pentru a juca un joc intelectual - „și cruci“ zerouri pe 3 × 3. Cum ați rezolva această problemă?

Prima dorinta este de a specifica în mod explicit ceea ce se mută pentru a face computerul. Ambele începători merg, de obicei, pe această cale, deoarece se pare cel mai ușor și controlat. Lăsați calculatorul joacă cruci. Apoi, puteți specifica în mod explicit faptul că prima mutare se face în centrul terenului. În continuare, cu toate acestea, răspunsul calculatorului trebuie să depindă de rândul jucătorului.

Notăm pătratelor bord, în stilul „tablă de șah“: de la A1 la C3. Apoi, acest algoritm joc (folosind C ++ sintaxa) ar arata ceva de genul

Acest algoritm este similar cu sistemul pur și simplu reflexe. Dar, în cazul în care se mută înregistrate în programul nostru? Pentru a vă asigura că un anumit curs de rezultatele noastre pentru a câștiga, trebuie să verificați toate mutarile posibile ale inamicului. Acest lucru poate fi reprezentat ca un arbore de jocuri, de asemenea, cunoscut sub numele de arborele de opțiuni pentru sarcini non-jocuri. Următoarea figură prezintă un arbore fragment exemplu pentru joc „și cruci“ zerouri în Câmpul 3 × 3. Rădăcina acestui arbore este o placă goală, și ramuri care pleacă din acestea corespund posibile tușele primului jucător. Aceste ramuri sunt în noua stare a lumii de joc, de la fiecare dintre ele au vedere, de asemenea, ramurile corespunzătoare mișcările permise de al doilea jucător, și așa mai departe. În cazul sarcinilor non-joc în rădăcina arborelui de opțiuni pot fi, de exemplu, să rezolve ecuația, iar ramurile sale vor fi compatibile cu operațiunile permise pe transformarea acestei expresii.

De fapt, un astfel de copac descrie spațiul de stat - un set de condiții care pot fi unele, cum ar fi lumea jocurilor de noroc cu posibile tranziții între state. Pentru unele probleme, acest spațiu poate fi definit prin listarea în mod explicit toate stările posibile și tranziția între ele, dar cel mai adesea este dat implicit - sub forma unor reguli (jocuri, integrare, etc ...). Pe baza regulilor pot fi organizate proceduri generativ construirea în mod explicit un arbore de opțiuni.

Noi folosim această procedură pentru a construi un copac joc, și pentru a găsi în ea răspunde că ar conduce

la victorie, sau, în cazul în care nu este posibil, la o remiză. Le vom fi intrat în programul nostru. Este posibil ca programul de calculator, care joacă în „tic-tac-toe“, ea a construit arborele de opțiuni pe baza procedurii de generare cunoscute? În mod firesc, o mai elegant (față de cele prezentate mai sus) și algoritmul ar trebui să dețină joc pentru a construi copac și să aleagă cel mai bun curs, așa cum facem.

Pentru a efectua o astfel de construcție, fără a stoca în memorie o copie suplimentară a câmpului de joc (la fel ca în cazul mai general - modelul lumii) este problematică. Să presupunem că câmpul [3] [3] - un tablou auxiliar de 3 x 3, valoarea la care celula este setat la „-“ în cazul în care celula corespunzătoare nu este ocupat, iar „X“ și „O“, în cazul în care există o „cruce“ și „toe“ respectiv. Apoi, procedura de generare poate fi scrisă sub forma:

În cazul în care pre-stabilite toate valorile unui camp de matrice ca goale ( „-“), și apoi executați această procedură tree_ de căutare ( „X“), în cursul activității sale într-o matrice de câmp se va transforma toate combinațiile posibile de zerouri de locație și cruci.

Să fie procedură check_game care evaluează situația de pe bord, revenind pe „X“ sau „Despre“, în cazul în care 3 într-un rând, fie livrate la jucătorul respectiv „-“ în cazul în care acest lucru nu este. putem stabili starea lor de frunze noastre de copac (pe cineva câștiga sau desena).

Acum ia în considerare nodurile de copac care preced imediat frunzele. În cazul în care cel puțin una dintre frunze duce la jucători câștigătoare, cursul care corespunde nodului curent, atunci nodul este, de asemenea, un câștigător. Nodul va pierde numai în cazul în care toate frunzele, în care el conduce, sunt pierdute. În acest fel, puteți marca toate nodurile care preced frunzele, și continuă să se răspândească aceste informații până la rădăcină.

Este mai convenabil să prezinte câștigul de calculator ca „1“ trage „0“, iar pierderea de calculator ca „-1“. Apoi, pentru a determina site-ul pentru statutul curs de calculator, va trebui să ia maxim, cât și pentru progresul inamicului - cel puțin în toate nodurile copil. Această procedură nodurile evaluările de stare prezentate în figura următoare, se numește procedura minimax. Încorporați procedura de generare procedura Minimax nu este dificil.

Trebuie remarcat existența teoriei jocurilor, conceptul mai general - Nash echilibrul corespunzător astfel de strategii de jucători, din care nici unul dintre ei nu este profitabil să se abată, în cazul în care nu face ceilalți jucători.

În cazul în care procedura de generare este cunoscută și utilizând procedura minimax pentru a determina cel mai bun curs, care-i problema? După cum deja de multe ori a menționat mai sus, problema - în NP-completitudinii. Cu alte cuvinte, versiunea completă a arborelui poate obține foarte mare: de multe ori numărul de noduri crește exponențial cu adâncimea de copac, deoarece fiecare nod conduce la un număr de unități noi, fiecare dintre care, la rândul său, din nou, conduce la un număr de unități noi. De exemplu, dimensiunea de copac în bucăți este de 10 ^ 40, pentru sah - 10 ^ 120, și pentru primul și destul de greu de imaginat numărul - 10 ^ 400. În mod ironic, este de multe ori pentru a sublinia amploarea acestor numere spune despre superioritatea lor esențială a numărului de atomi sau particule elementare din univers, nu este justificată în totalitate prin compararea numărului de obiecte și numărul de combinații de stări ale obiectelor. Cu toate acestea, această comparație devine justificată atunci când vine vorba de sistemele clasice cu paralelism masă: chiar dacă fiecare atom din univers ar fi un procesor separat, atingere cu degetul 10.100 de combinații pe secundă, ale întregului univers pentru tot timpul care a trecut de la Big Bang, nu este suficient pentru a pentru a juca un joc perfect al doilea.

Opțiuni de lemn specificate implicit, prin regulile jocului, este un fel de invizibil pentru program. Ca șobolan pentru a explora labirint reală, trebuie să-și petreacă ceva timp pe studiul de fiecare furcă, urmat de o continuare a căii nu este vizibil, iar programul trebuie să-și petreacă ceva timp (resurse de calcul) pentru a explora opțiunile pentru copac și pentru a găsi drumul spre victorie.

În ciuda jocului aparent elementare „Tic-Tac-toe“ chiar și pe 3 × 3 pentru un copil care nu este familiarizat cu ea, necesită efort mental semnificativ. Acest joc necesită o căutare de variante la o adâncime de 4-5, care este aproape de complexitatea de a găsi centrul sarcinilor segment prin utilizarea unui conducător și busolă. Cu toate acestea, „gândire“ o dată „tic-tac-toe“ pe 3 × 3, vom ști decizia (calea în opțiunea „labirint“), iar jocul va pierde interesul. Pentru „adult“ jocuri intelectuale astfel de limitări nu este specifică pentru că tot spațiul de căutare în ele nu pot fi examinate pe parcursul vieții unei persoane și chiar și în timpul întregii perioade de existență a civilizației.

Ce se poate face în cazul în care întregul copac este generat nu poate fi? Care sunt motivele pentru a alege un curs? Programarea euristică, termenul câmpul „euristică“ este specificat ca un dispozitiv care vă permite să taie în opțiunile de sortare ramuri nepromițători pe copac, care este mult mai specific definiție decât ambele tehnici euristice care facilitează rezolvarea problemei.

O euristică este deja utilizat implicit în pregătirea copac joc pentru „Tic Tac Toe“. Acesta arată toate pozițiile inițiale de joc, nu în alta prin rotație și oglindire. Cu alte cuvinte, euristica utilizate simetrie. Cât de multe versiuni ale jocului, dacă nu iau în considerare simetria? Numărul lor - nu mai mult factorialul numărului 9. Utilizarea simetrii acest număr este redus cu un ordin. Cu toate acestea, câștigul relativ pentru câmpuri mari este mult mai mică, așa cum deja după mai multe accidente vasculare cerebrale simetrice încetează să existe continuare.

Simetria este o euristică foarte general, dar nu prea puternic, pentru că simetria jocului situație (chiar dacă există unul) este rupt foarte repede.

Se poate imagina o mai complicată (și private) euristic: mai profitabil o miscare care ar putea fi folosit într-un număr mai mare de construcții de trei într-un rând. Pentru această bază inițială euristică pentru „eco“ este cea mai profitabilă muta la centru, deoarece acesta poate participa la patru construcții diferite. Apoi, există pasaje în colțuri - pentru ei, numărul de construcții este de trei. Pentru mișcări de pereți acest număr doar două. Este clar că această euristică este insuficientă, deoarece ignoră capacitățile inamice (de exemplu, completează combinația acestuia).

Este dorinta naturala de a evalua profitabilitatea progresului cantitativ. Bazat pe o astfel de cuantificare poate fi tăiat ramuri porțiilor la fiecare nod al arborelui pentru acest lucru. Și, într-adevăr, în atribuirea de programare euristică euristice sub formă de (statică) funcție evaluează cele mai frecvente.