Informacinės intelektualios sistemos veikimas ir planavimas

Informacinės intelektualios sistemos veikimas ir planavimas
Daugelio informacinių intelektualių sistemų (IIS) funkcionavimas yra tikslingas. Tipinis tokio funkcionavimo pavyzdys yra kelio planavimo tam tikram tikslui pasiekti užduočių sprendimas, kai žinoma fiksuota pradinė situacija. Sprendimo rezultatu turi būti veiksmų planas. Toks planas pri¬mena scenarijų, kuriame santykiai tarp viršūnių yra: „tikslas-potikslis”, „tikslas-veiksmas”, „veiks-mas-rezultatas” ir pan. Bet koks kelias šiame scenarijuje vedantis iš viršūnės, apibrėžiančios situaci¬ją, į bet kokią iš tikslo viršūnių nusako veiksmų planą. Veiksmų plano paieška atsiranda tik tada, kai susiduriama su nestandartine situacija kuuriai išspręsti nėra žinomo veiksmų plano. Visus plano su¬darymo uždavinius galima išskirti į du tipus, kuriems atitinka skirtingi modeliai: planavimas būsenų aplinkoje (SS-problema) ir planavimas uždavinių aplinkoje (PR-problema).
Pirmuoju atveju laikoma, kad yra užduota tam tikra situacijų aplinka. Situacijos aprašyme yra išorinio pasaulio ir IIS būsenos, kurios yra charakterizuojamos eile parametrų. Situacijos sudaro tam tikrus apibendrintus būvius. IIS veiksmai arba pokyčiai išorinėje aplinkoje veikia aktyvius bū¬vius. Iš apibendrintų būsenų išskiriamos pradinės (dažniausiai viena) ir baigtinės (tikslinės) būse¬nos. SS-problema yra kelio paieškoje vedančio išš pradinės būsenos į vieną iš baigtinių.
Esant planavimui uždavinių aplinkoje situacija kiek kitokia. Aplinka (erdvė) formuojama kai uždavinių aibei pritaiko tokius santykius kaip: “dalis-pilnumas”, “tikslas-potikslis”, “bendras atvejis – išskirtinis atvejis” ir pan. Uždavinių aplinka atspindi uždavinių skaidymą į použdavinius (tikslo į potikslius). Suklasifikuokime metodus, sk

kirtus SS ir PR problemų sprendimui.
Planavimas pagal būsenas
Uždavinių vaizdavimas būsenų erdvėje numano eilę aprašymų: būsenų, operatorių ir jų sąvei¬kos aibės, tikslo būsenų. Būsenų aprašymais gali būti simbolių eilutės, vektoriai, dvimačiai masy¬vai, medžiai, sąrašai ir t.t. Operatoriai perveda būsenas iš vienos į kitą. Kartais jie vaizduojami kaip produkcijos A=>B, reiškiančios, kad būsena A pereina į būsena B.
Būsenų erdvę galima pavaizduoti kaip grafą, kurio viršūnės yra būsenos, o lankai – operato¬riai. Jeigu lankas veda nuo viršūnės n; prie viršūnės n, tai n^ yra viršūnė tėvas, o n – vaikas (palikuo¬nis). Viršūnių seka nu, rij2,. , nįk, kur kiekviena n; yra viršūnės nyj vaikas, vadinasi keliu k nuo vir¬šūnės nu prie viršūnės n±. Tokiu būdu uždavinio sprendimo paieškos problema, kai yra planuojama pagal būsenas, susiveda prie kelio iš A į B paieškos grafe problemos. Dažniausiai grafai ne užduodami, o generuojami esant reikalui.
Yra žinomi aklieji ir kryptingi kelio paieškos būdai. Aklasis būdas turi du tipus: paieška į gylį ir paieška į plotį. Ieškant į gylį kiekviena alternatyva tiriama iki galo, ne paisant kitų alternatyvų. Šis metodas blogai tinka “aukštiems” medžiams, nes galima lengvai praeiti šalia teisingo sprendinio ir sugaišti daug laiko neteisingų kelių tyrimui. Ieškant į plotį fiksuotame lygyje tiriamos visos alter¬natyvos ir tik paskui pereinama prie sekančio lygmens. Šis metodas gali būti blogesnis nei paieška į gylį, jeigu keliai vedantis pfie tikslo viršūnės yra maždaug tame pačiame gylyje. Abu akli metodai reikalauja didelio laiko eikvojimo todėl reikalingi kriptingos paieškos metodai.
Šakų ir ribų metodas. Iš formuojamų paieškos metų nebaigtų kelių išrenkamas trumpiausias yra pratęsiamas vienu žingsniu. Naujai gauti nebaigti keliai yra nagrinėjami su prieš tai gautais ir vėl parenkamas trumpiausias iš jų. Procesas kartojamas iki pasiekiama tikslo viršūnę. Sprendimas užrašomas. Po to atmetami visi keliai ilgesni ar lygus rastajam, o trumpesni keliai tiriami prieš tai aprašytu metodu. Galų gale arba visi likusieji keliai atmetami, arba iš jų formuojamas trumpesnis, kuris pradedamas laikyti etaloniniu ir t.t.
Mūro trumpiausių kelių algoritmas. Pradinė viršūnė x<) pažymima 0. Tegul algoritmo darbo eigoje tam tikrame žingsnyje gauta viršūnės xj viršūnių-vaikų aibė G(XJ). Tada iš jo išbraukiami vi¬sos prieš tai gautos viršūnės, o likusios pažymimos vienetų didesne žyme, nei Xį žymė ir nuo jų pa¬daromos nuorodos į x,. Toliau pažymėtų viršūnių aibėje išrenkama viršūnė dar nefigūruojanti kaip nuorodų adresas. Išrenkama viršūnė su mažiausia žymę ir nuo jos daromos dukterinės viršūnės. Vir¬šūnių žymėjimas tęsiamas kol nepasiekiama dukterinė viršūnė.
Deikstros algoritmas. Kelių paieška su minimalia kaina yra apibendrintas Mūro metodas dėl svorinių lankų įvedimo.
Dorano ir Mičipaieškos su žema kaina algoritmas. Naudojamas kai yra didelė paieškos kaina palyginamai su optimalaus sprendimo kaina. Šiuo atveju, neišrenkama arčiausia nuo pradžios viršū¬nė kaip Mūro ir Deikstros algoritmuose, o išrenkama viršūnė euristinis atstumas nuo kurios iki tiks¬lo yra mažiausias. Esant geram įvertinimui, galima greitai gauti sprendimą, bet nebūtinai geriausią.
Harto, Nilsono ir Rafaelio algoritmas. Algoritme apjungti abu kriterijai: kelio kaina iki viršū¬nės g(x) ir kelio kaina nuo viršūnes h(x). f(x) = g(x) + h(x). Esant sąlygai h(x) uždavinys ir žinoma, kad operatorius f būtinai įeina į to uždavinio sprendimą. Toks operatorius vadinamas raktiniu. Tegul f pritaikymui reikalinga būsena C, o jo pritaikymo rezultatas f(C). Tuomet IR-viršūnė

Leave a Comment