1.uzdevums
Lai uzbūvētu mākslīgu sistēmu, kas spēj risināt problēmas , ir jāizpilda četras lietas:
• precīzi jādefinē pati problēma, jāapraksta gan sākuma situācija, gan beigu situācijas. katra no beigu situācijai atbilst problēmas risināšanai.
• jāanalizē formulēta problēma, norādo tās svarīgākos objektus un saites starp tiem;
• formālā veidā jāatspoguļo zināšanas, kas ir vajadzīgas problēmas risināšanai;
• jāizvēlēas un jāpielieto labākā problēmas risināšanas tehnika.
Stāvokļu telpa (grafs) ir līdzeklis, kas ļauj atspoguļot problēmu un atbildēt uz jautājumiem:
1)Vai iespējams atrast problēmas risinājumu?
2) Vai risinājumu var atrast vienmēr (pie jebkuriem ieejas datiem)?
3)Kā projektēt algoritmu, kas ļauj atrast risinājumu visefektīvākajā veidā?
Stāvokļa telpu atspoguļo grafa veidā. Grafa loki atspoguļo pārejas starp stāvokļiem un atbilst problēmas risināšanas soļiem. Grafa virsotnes ir problēmas risināšanas procesa diskrētajā stavoklī.
Stāvokļa telpas grafa raksturojumi:
• grafā vienmēr ir saknes virsotne (viena vai vairākas), kurai nav pēcteču;
• sākuma stāvokļiem vienmēr jāatbilst dotai informācijai par problēmu;
• grafs vienmēr ir orientēts (neorientēts grafs nepievedīs pie problēmas risinājuma);
• grafā vienmēr ir mērķa virsotnes (mērķi), kas parāda problēmas risinājumu un kuriem nav pēcteču;
• mērķa virsotnes vienmēr ir pēdējā grafa līmenī un tās ir strupceļu virsotnes, kurām nav pēcteču, taču ne visas pēdējā līmeņa visotnes ir mērķi;
• visām pārējām virsotnēm ir gan pēcteči, gan priekšteči.
…
