Acest capitol este dedicat rezolvării problemelor utilizând graficul spațial de stare. Spațiul de stat este descris ca un set de stări - vârfurile graficului, setul de tranziții de la arce de stat la stat al graficului, setul de stări inițiale și setul de stări finale. Soluția problemei este reprezentată sub forma unei căi pe graficul spațial de stare care leagă starea inițială cu starea finală.
Dacă spațiul de stare al problemei este mic, atunci toate soluțiile optime vor fi găsite prin căutarea în profunzime. În cazul problemelor cu un spațiu mare de stare, numai o soluție optimă va fi calculată prin căutarea lățimii.
La probleme se folosesc rezolvatori universali. Stările în diferite sarcini pot aparține unor domenii diferite. Pentru a ne aminti cele mai bune dintre soluțiile găsite, se folosește varM variabila variabilă. Compilatorul găsește tipurile necesare.
13.1. Căutarea în adâncime de stat
În această secțiune, căutarea în adâncime în spațiul de stare este utilizată pentru a rezolva probleme cunoscute. În primul rând, solverul este aplicat problemei lupului, caprei și varzei. Pentru a rezolva alte probleme, în program sunt adăugate doar descrieri ale statelor și tranziții între ele.
Problema lupului, a caprei și a varzei este după cum urmează (Alquin, secolul al XIII-lea). Proprietarul cu un lup, o capră și o grămadă de capete de varză trebuie să traverseze râul de pe malul stâng spre dreapta, cu o barcă mică la dispoziția sa. În această barcă, cu excepția proprietarului, poate exista doar un lucru - fie un lup, o capră sau o varză. Nu poți lăsa un lup cu o capră fără supraveghere, ci o capră cu varză. Cum ar trebui să aranjez traversarea?
Stările în problemele de transport peste râu sunt de obicei descrise ca un triple care conține o mulțime de creaturi (obiecte) pe malul stâng, o mulțime de creaturi (obiecte) pe malul drept și malul în care este localizată barca.
Pentru a rezolva problemele, ca și înainte, este creat un proiect de consola. În acest proiect este creat un modul de adâncime. În modulul 13.2, linia din Visual Prolog 7.5 V = varM :: new ([]) din Visual Prolog 7.4 ar trebui înlocuită cu șirul V = varM *> :: nou ([]).
Exemplul 13.1. Clasa de adâncime
Exemplul 13.2. Implementarea clasei de adâncime
Articole similare
-
Cunoștințe, prelegere, fundamentele implementării tehnologiei de circuit a calculatoarelor
-
Know-how, prelegere, conexiune la serverul de baze de date microsoft sql
Trimiteți-le prietenilor: