Turinys

• Palyginimo diagrama
• Sąmoningos paieškos apibrėžimas
• Pirmasis euristinis gylis
• Neapibrėžtos paieškos apibrėžimas
• Pirmoji gylio paieška
• Išvada

Paieška yra žingsnių sekos, reikalingos bet kuriai problemai išspręsti, paieška. Ankstesnis skirtumas tarp informuotos ir neinformuotos paieškos yra tas, kad informacija pagrįsta paieška pateikia gaires, kur ir kaip rasti sprendimą. Priešingai, neinformuota paieška neteikia jokios papildomos informacijos apie problemą, išskyrus jos specifikaciją.

Tačiau tiek informavus, tiek neinformuoti paieškos būdai, informacija pagrįsta paieška yra efektyvesnė ir ekonomiškesnė.

1. 1. Palyginimo diagrama
   2. Apibrėžimas
   3. Pagrindiniai skirtumai
   4. Išvada

Palyginimo diagrama

Palyginimo pagrindas	Informuota paieška	Neinformuota paieška
Pagrindinis	Pasitelkia žinias ieškant sprendimo žingsnių.	Nereikia naudoti žinių
Efektyvumas	Labai efektyvus, nes sunaudoja mažiau laiko ir sąnaudų.	Efektyvumas yra vidutiniškas
Kaina	Žemas	Palyginti aukštai
Spektaklis	Greičiau randa sprendimą	Greitis yra lėtesnis nei informacija pagrįsta paieška
Algoritmai	Pirminė euristinė ir pirmojo pločio paieška bei A * paieška	Pirmoji paieška pagal gylį, pirmoji platuma ir mažiausia kaina

Sąmoningos paieškos apibrėžimas

Remdamasi informacija pagrįstos paieškos metodais, naudodamiesi konkrečiomis problemos žiniomis, išsiaiškinate, kaip išspręsti problemą. Šio tipo paieškos strategija iš tikrųjų neleidžia algoritmams suklupti dėl tikslo ir sprendimo krypties. Informuota paieška gali būti naudinga išlaidų atžvilgiu, kai optimalumas pasiekiamas mažesnėmis paieškos sąnaudomis.

Norint grafike ieškoti optimalios kelio kainos, įgyvendinant pagrįstą paieškos strategiją, perspektyviausi mazgai n įterpiami į euristinę funkciją h (n). Tada funkcija grąžina neigiamą tikrąjį skaičių, kuris yra apytikslis kelio mokestis, apskaičiuotas nuo mazgo n iki tikslinio mazgo.

Svarbiausia informuotos technikos dalis yra euristinė funkcija, leidžianti algoritmui suteikti papildomų žinių apie problemą. Dėl to tai padeda rasti kelią į tikslą per įvairius kaimyninius mazgus. Yra įvairių algoritmų, pagrįstų informacija paremta paieška, pavyzdžiui, euristinė paieška pirmiausia pagal gylį, heuristinė pirmo pločio paieška, A * paieška, etcetera. Dabar supraskime pirmąją euristinę paiešką.

Pirmasis euristinis gylis

Panašus į paieškos metodą, pateiktą žemiau, heuristiniame gylyje, pirmiausia pasirenkamas kelias, tačiau prieš pasirenkant kitą kelią, jis pereina visus kelius iš pasirinkto kelio. Tačiau jis pasirenka geriausią kelią vietoje. Tais atvejais, kai mažiausia euristinė vertė yra prioritetas pasienyje, tada ji yra žinoma kaip geriausia pirmoji paieška.

Kitas pagrįstas paieškos algoritmas yra A * paieška, sujungianti mažiausios kainos ir geriausios pirmosios paieškos sąvoką. Šis metodas atsižvelgia ir į kelio kainą, ir į euristinę informaciją ieškant ir parenkant kelią, kurį reikia išplėsti. Numatoma bendra kelio kaina, naudojama kiekvienam keliui, esančiam ant sienos nuo pradžios iki tikslinio mazgo. Todėl jis tuo pačiu metu naudoja dvi funkcijas - savikaina (p) yra aptikto kelio kaina, o h (p) yra apskaičiuota kelio kainos nuo pradinio mazgo iki tikslo mazgo vertė.

Neapibrėžtos paieškos apibrėžimas

Neinformuota paieška skiriasi nuo informuotos paieškos tuo, kad joje tik pateikiamas problemos apibrėžimas, tačiau nesiimama jokių papildomų žingsnių ieškant problemos sprendimo. Pagrindinis neinformuotos paieškos tikslas yra atskirti tikslinę ir ne tikslinę būsenas, ir ji visiškai ignoruoja tikslą, kurio link ji eina, kol suranda tikslą ir praneša apie paskesnį. Ši strategija dar vadinama akląja paieška.

Šioje kategorijoje yra įvairių paieškos algoritmų, tokių kaip pirmoji paieška pagal gylį, vienodų sąnaudų paieška, pirmo pločio paieška ir pan. Leiskite mums dabar suprasti neinformuotos paieškos sąvoką pasitelkiant išsamią paiešką.

Pirmoji gylio paieška

Atliekant išsamią paiešką, mazgas pridedamas ir pašalinamas „Stable Last in first out“ rinkinyje. Vienu metu pridedamas arba pašalinamas tik vienas mazgas, o pirmasis elementas, pašalintas iš krūvos krašto, būtų paskutinis elementas, pridėtas prie krūvos. Naudojant krūvą pasienyje, pirmiausia ieškoma kelių nuodugniai. Kai ieškoma trumpiausio ir optimalaus kelio, naudojant pirmiausia gylį, gretimų mazgų sukurtas kelias pirmiausia užbaigiamas, net jei jis nėra norimas. Tada ieškoma alternatyvaus kelio atgal.

Kitaip tariant, algoritmas pasirenka pirmąją alternatyvą kiekviename mazge, tada grįžta prie kitos alternatyvos, kol apvažiuos visus kelius nuo pirmosios atrankos. Tai taip pat kelia problemą, kai paieška gali nustoti sustoti dėl grafike esančių begalinių kilpų (ciklų).

1. Ankstesnė informuotos paieškos technika, norėdama rasti sprendimą, naudoja žinias. Kita vertus, pastaroji neinformuota paieškos technika žinių nenaudoja. Paprasčiau tariant, daugiau informacijos apie sprendimą nepateikiama.
2. Informacinės paieškos efektyvumas yra geresnis nei neinformuotos paieškos.
3. Neinformuota paieška reikalauja daugiau laiko ir sąnaudų, nes, palyginti su informacija pagrįsta paieška, ji neturi jokio sprendimo.
4. Paieška pagal gylį, platumą pirmiausia ir mažiausią kainą pirmiausia yra algoritmai, kurie priklauso neinformuotos paieškos kategorijai. Priešingai, informacija pagrįsta paieška apima tokius algoritmus kaip pirmoji euristinė paieška, pirmoji euristinė paieška ir A * paieška.

Išvada

Informacijoje pagrįsta paieška pateikia sprendimo kryptį, tuo tarpu neinformuotoje paieškoje sprendimas nėra siūlomas. Dėl to neinformuota paieška tampa ilgesnė, kai algoritmas yra įdiegtas.