Note programmistera sisteme inteligente

Munca de zi cu zi a programatorului moderne lasă rar loc pentru dezvoltarea gândirii creative. Cel mai adesea, pentru a rezolva probleme, este suficient să se aplice soluția dovedită: modelul sau bibliotecă. Cunoașterea de abordări general acceptate și practici, biblioteci și cadre, asta e ceea ce astăzi este un semn de calificare de programator.

Între timp, frumusețea și magia de programare pentru mulți (eu sunt sigur că nu sunt singur în acest) sunt pe deplin dezvăluite pentru a rezolva probleme complexe algoritmice, atât de rar întâlnite în practica de zi cu zi. Și, din moment ce „muntele nu va veni la Mahomed“, că Mohammed a inventat un puzzle de unul singur!

Ca sarcini de warm-up pentru creier, vă sugerez să încerce să învețe pe un computer pentru a asambla puzzle-cunoscut „Cincisprezece“.

Cincisprezece - popular joc de puzzle inventat în 1878 de către Noah Chapman. Este o colecție de plăci pătrate identice cu numere aplicate, închise într-o cutie pătrată. Lungimea casetei de patru ori lungimea knuckles laterale pentru un set de 15 elemente (și de trei ori pentru un set de 8 elemente), respectiv, în necompletată caseta rămâne un câmp pătrat. Scopul jocului - mutarea încheieturile degetelor de pe caseta pentru a realiza ordonarea lor după număr, ceea ce face de preferință cât mai puțin posibil mișcare.
Cheia pentru rezolvarea problemei va deveni algoritm cunoscut pentru a găsi prima cel mai potrivit pe grafic A *. Pentru a simplifica prezentarea problemei, voi lua în considerare un puzzle cu o dimensiune a câmpului de 3 x 3.

Întregul proces de găsire a unei soluții la „tag-ul“ poate fi privit ca problema a casetei de căutare. Nodurile acestui grafic va puzzle starea câmp care rezultă din deplasarea knuckles:

Soluții de căutare pot fi reduse pentru a găsi starea terminalului de bord de joc (de obicei, ca ascendent un terminal, aranjament selectat de placi aranjate de la stânga la dreapta, de sus în jos).

Pentru a rezolva problema de a găsi un terminal de la partea de sus a graficului, puteți utiliza algoritmii de căutare exhaustivă (căutare adâncime sau lățimea), dar numărul de soluții posibile (permutări posibile) este probabil să fie suficient de mare pentru rezultatul de căutare exhaustivă nu se va vedea până la pensionare.

Un algoritm * poate reduce semnificativ numărul de state pentru a itera, prin aplicarea unor euristică de informații suplimentare. Deoarece astfel de informații este oferit să ia numărul estimat de permutări necesare obținerii unui stat terminale.

Pentru a înțelege exact cum A * vă permite să căutați pe grafic, am recomandăm să citiți articolul A * algoritmul pentru începători. Materialul de pe acest algoritm este scris atât de mult încât am nici o dorință de a locui cu privire la detaliile prezentate punerea sa în aplicare, dar, cu toate acestea, pentru mai bună înțelegere a ceea ce se întâmplă în înțelegerea unui algoritm * este necesar. Deci, pe scurt, eu încă va explica succesiunea acțiunilor întreprinse de algoritmul pentru a căuta o stare terminală prin exemplul soluțiilor puzzle-ului ales.

Un algoritm * presupune existența a două liste de noduri: deschise și închise. În primele vârfuri nu sunt dovedite încă algoritm, iar al doilea acele noduri care au îndeplinit deja în căutarea de soluții.

La fiecare pas, din lista de noduri deschise selectate la vârf cu cea mai mică greutate. Greutate (F) din fiecare nod este calculat ca suma distanțelor de la nodul inițial la curent (G) și o presupunere euristică că distanța de la nodul curent la un terminal (H). F i = i + G H i. unde i - vârful curent (starea de tabla de joc).

Pentru „pyatnashek“, puteți face presupunerea că, pentru a atinge partea de sus a terminalului, trebuie să efectuați o mișcare nu este mai mic decât numărul de placi care nu sunt în locurile lor, iar distanța de la vârful inițial la curent contoriza numărul de permutări efectuate:

În plus, nodurile selectate sunt generate pentru nodurile copil (state care pot fi obținute prin mutând piesele într-o celulă goală). Fiecare nod are un link către părinte, și anume „Remembers“ din care de stat provine.

Secvența de acțiuni se repetă până când lista de noduri deschise este de cel puțin un nod sau până la punerea în aplicare a algoritmului nu îndeplinește partea de sus a terminalului.

o soluție Java.

Un algoritm * este folosit pentru a rezolva un număr mare de sarcini. Nu vreau să limiteze soluția sa de punere în aplicare doar „pyatnashek“. De aceea, propun să abstracte de la problema care trebuie rezolvată cu ajutorul unor interfete, clase abstracte și moștenirea.

În primul rând, problema care trebuie rezolvată prin algoritmul A *, definiția diferită de noduri (sau state). Introducem o clasă abstractă care încapsulează generală, pentru oricare două vârfuri, comportament:

De asemenea, diferite reguli problema de generare de noduri copil, algoritmul de calcul distanța de la vârful inițial și o estimare euristică a distanței până la un vârf de terminal. Alegem aceste caracteristici în interfața:

Pe baza acestor abstractii, este posibil să se implementeze algoritmul A * este după cum urmează:

Această soluție este oarecum mai mică decât optimă. Cu siguranță ați observat că informațiile din lista de noduri închise redundante: nu vom ști niciodată detaliile de sus a listei, ci doar faptul apartenenței la un top de ea. Pentru aceasta nu este suficient pentru a se mentine sus, iar valorile funcțiilor hash.

Acum, în ceea ce privește punerea în aplicare a pyatnashek direct. Nu voi reproduce aici tot codul sursă, îl puteți vedea în depozitul de pe BitBucket. Mă concentrez doar pe interesant, în opinia mea, lucrurile.

În primul rând, terenul de joc foarte convenabil pentru a reprezenta o matrice unidimensională, acest lucru va evita bucle imbricate inutile, și, în general, mai ușor decizia face. vertex algoritm dezvăluire (a primit descendenții săi), într-un astfel de caz, obținut este destul de simplu. Inițial, celula este gol indicele de indicele de os este apoi calculat, care va fi mutat într-o celulă goală. Indexul este calculat ca suma indicelui celulelor goale și indicele unuia dintre vecinii săi. celule vecine coduri elementare: pentru vecinul din stânga este -1, unul pentru vecinul din dreapta, vecinul de mai sus - (dimensiunea câmpului), vecinul de jos + (dimensiunea câmpului):

În al doilea rând, pentru a genera starea inițială, primul lucru care vine în minte este de obicei - este un aranjament aleatoriu de celule de pe terenul de joc. Dar această abordare are un dezavantaj major. Dacă ați uitat deja la wiki. știi că exact jumătate din toate pozițiile inițiale posibile pyatnashek imposibil de a aduce la minte colectate. Aceasta este, cu această abordare, riscați să genereze o astfel de stare inițială, o decizie pentru care nu există deloc, sau căuta o soluție este amânată pentru indecent pentru o lungă perioadă de timp. Pentru a nu strica impresia lui a muncii depuse, puteți merge în altă parte: este posibil să se efectueze N permutări aleatoare boxurile corecte, pornind de la o stare terminală. Această abordare garantat de a oferi starea inițială, are o soluție și se lasă să se adapteze complexitatea căutării:

UPD: La cererea de urgență a unui cititor anonim, voi descrie două mod aparent evident, pentru a genera starea inițială.

În conformitate cu formula dată în Wikipedia, puteți verifica starea inițială a posibilității de ao aduce la un mediu terminal:

Putem arăta că exact jumătate din toate posibile 1 307 674 368 000 poziții inițiale pyatnashek imposibil de a aduce la mintea colectate (= 15!): Lăsați cutia cu numărul de reglare (dacă numărul de la stânga la dreapta și de sus în jos) pătrate cu numere mai mici. Presupunem, că este, dacă după knuckles cu numărul mii Nr numere mai puțin. Considerăm, de asemenea, numărul - numărul unui număr de celule goale (numărând de la 1). În cazul în care suma

este ciudat, apoi rezolva puzzle-ul nu există.
Și dacă nu există nici o soluție, regenera starea inițială. Bazându-se pe caz nu va pe placul meu, ci de a alege una sau alta abordare tine. În orice caz, o decizie majoră, și nu starea inițială :)

Procedura de verificare a stării inițiale:

Testați soluția în acțiune: FifteenPuzzle.jar.

$ Java -jar FifteenPuzzle.jar -h

În motivele de prelegeri pe „Sisteme inteligente“.

Îmi exprim recunoștința personală pentru Kopylovu Andreyu Valerevichu, pentru o prezentare interesantă a cursului.

Încercați un alt criteriu pentru determinarea greutății în partea de sus. Nu numărul de placi care nu sunt în locurile lor, iar calea totală care trebuie să treacă fiecare încheietură la locul lui. (Pentru primul colț din exemplul dvs., H = 10), am aranjat pentru concurs și algoritmii dumneavoastră, diferența în numărul de noduri care trebuie procesate atinge ordinea. Cincisprezece 4x4, treizeci de pasaje de amestecare (da, eu amestecate la întâmplare se mută):
algoritmul meu
Deschideți List - 1668
listă închisă - 1753
algoritmul dvs.
Deschideți Listă - 22317
Închis List - 22452

„Principalul dezavantaj -. Nu găsește întotdeauna cea mai scurtă soluție, deși, de obicei, este destul de aproape de ea.“

În general, se aplică de cercetare, nu înseamnă că rezultatul va fi cum era de așteptat. Cu A * i este cea mai scurtă cale _ischu_. Nu este primul disponibil, și anume cel mai scurt. Faptul că rezultatul poate fi diferit de așteptările mele,, așteptările lor, nu neagă :)

Încercați în loc de G inserați deget de la picior. Sunt în listele închise și deschise, se pare,
undeva, la 150 - 300 de înregistrări, în medie. În cazul în care starea următoare este lista deschisă sau închisă, pur și simplu ignora-l. Și da, H calculat ca distanța totală parcursă de fiecare os la locul lui. Barca clicuri puzzle două secunde: D

. „Bazându-se pe caz nu va pe placul meu, ci de a alege una sau alta abordare tine.“

Adică, la voia întâmplării? În cazul în care amplasarea pieselor pe teren nu validează, rândul său, doar (matricea transpune) „parte“ și a obține o stare validă. Deci, este o abordare destul de normal.