Tačiau tarp informuotų ir nepažįstamų paieškos metodų informacija pagrįsta paieška yra efektyvesnė ir ekonomiškesnė.
Palyginimo diagrama
| Palyginimo pagrindas | Informuota paieška | Nežinoma paieška |
|---|---|---|
| Pagrindinis | Naudoja žinias, kad rastų žingsnius į sprendimą. | Nėra žinių |
| Efektyvumas | Labai efektyvus, nes sunaudoja mažiau laiko ir išlaidų. | Efektyvumas yra tarpininkavimas |
| Kaina | Žemas | Palyginti didelis |
| Spektaklis | Randa sprendimą greičiau | Greitis yra lėtesnis nei žinoma paieška |
| Algoritmai | Pirmoji paieška, pirmoji paieška ir mažiausia kaina | Heuristinis gylis pirmoji ir pirmoji paieška bei A * paieška |
Informuotos paieškos apibrėžtis
Informuotoje paieškos technikoje naudojamos problemos specifinės žinios, kad būtų galima išsiaiškinti problemos sprendimą. Ši paieškos strategija iš tikrųjų neleidžia algoritmams suklupti į tikslą ir kryptį prie sprendimo. Informuotoji paieška gali būti naudinga atsižvelgiant į išlaidas, kai optimizavimas pasiekiamas esant mažesnėms paieškos išlaidoms.
Norėdami ieškoti optimalios kelio kainos grafike, įgyvendinant informuotą paieškos strategiją, į perspektyviausius mazgus n įterpiami į heuristinę funkciją h (n). Tada funkcija grąžina ne neigiamą realaus skaičiaus, kuris yra apytikslė kelio kaina, apskaičiuota nuo mazgo n iki tikslinio mazgo.
Čia svarbiausia informuotos technikos dalis yra heuristinė funkcija, kuri palengvina papildomų žinių apie problemą skleidimą algoritme. Dėl to ji padeda rasti kelią į tikslą per įvairius kaimyninius mazgus. Yra įvairių algoritmų, pagrįstų žinoma paieška, pvz., Heuristinis gylis, pirmoji paieška, pirmoji paieška, A * paieška ir kt. Dabar suprasime heuristinę gylį - pirmąją paiešką.
Heuristinė gylio pirmoji paieška
Panašiai kaip ir pirmojo paieškos metodo, pateikto žemiau heuristinio gylio, pirmoji paieška pasirenka kelią, bet perkelia visus kelius iš pasirinkto kelio prieš pasirinkdama kitą kelią. Tačiau jis pasirenka geriausią kelią vietoje. Tais atvejais, kai mažiausia heuristinė vertė yra sienos prioritetas, tai vadinama geriausia pirmąja paieška.
Kitas informuotas paieškos algoritmas yra A * paieška, kuri sujungia mažiausios kainos ir geriausių pirmųjų paieškų koncepciją. Šiame metode atsižvelgiama ir į kelio kainą, ir į heuristinę informaciją ieškant ir pasirinkus išplėstinį kelią. Apskaičiuota bendra kelio kaina, naudojama kiekvienam pasienio maršrutui nuo pradžios iki tikslinio mazgo. Todėl ji naudoja dvi funkcijas tuo pačiu metu - kaina (p) yra aptikto kelio kaina ir h (p) yra apskaičiuota kelio kainos nuo pradinio mazgo iki tikslo mazgo vertė.
Neaiškios paieškos apibrėžtis
Nežinoma paieška skiriasi nuo žinomos paieškos taip, kad tik pateikia problemos apibrėžimą, bet ne daugiau žingsnio ieškant problemos sprendimo. Pagrindinis neinformuotos paieškos tikslas yra atskirti tikslinę ir netikslinę būseną, ir ji visiškai ignoruoja tikslą, kuriam ji keliauja, kol bus aptiktas tikslas ir ataskaitų perėmėjas. Ši strategija taip pat žinoma kaip akli paieška.
Pagal šią kategoriją yra įvairių paieškos algoritmų, pavyzdžiui, pirmoji paieška, vienodų išlaidų paieška, pirmoji paieška ir pan. Dabar suprasime neinformuotos paieškos sąvoką, naudodamiesi giluminio paieškos pagalba.
Pirmoji paieška
Išsamiai pirmą kartą ieškant, „Paskutinis iš pirmojo išeities“ kamino pridedamas ir pašalinamas mazgas. Vienu metu pridedamas arba pašalinamas tik vienas mazgas ir pirmasis elementas, pašalintas iš kamino ribos, būtų paskutinis elementas, pridėtas prie kamino. Naudodamiesi pasienio rezultatais, ieškant takų, pirmiausia sekėsi. Kai ieškoma trumpiausio ir optimaliausio kelio, naudojant pirmąjį gylį, gretimų mazgų sukurtas kelias bus baigtas, net jei jis nėra norimas. Tada ieškoma alternatyvaus kelio.
Kitaip tariant, algoritmas pasirenka pirmąją alternatyvą kiekviename mazge, o po to eina į kitą alternatyvą, kol jis nuvažiavo visus kelius nuo pirmojo pasirinkimo. Tai taip pat kelia problemą, kai paieška gali nustoti sustoti, nes grafike yra begalinių kilpų (ciklų).
Pagrindiniai skirtumai tarp informuotos ir neinformuotos paieškos
- Ankstesnis informuotas paieškos metodas naudoja žinias, kad rastų sprendimą. Kita vertus, pastaroji nežinoma paieškos technika nenaudoja žinių. Paprastai nėra daugiau informacijos apie sprendimą.
- Informuotosios paieškos efektyvumas yra geresnis nei nežinoma paieška.
- Nepažįstama paieška sunaudoja daugiau laiko ir sąnaudų, nes neturi jokios informacijos apie sprendimą, palyginti su žinoma paieška.
- Pirmoji paieška, pirmoji paieška ir mažiausia kaina pirmoji paieška yra algoritmai, kurie priklauso neinformuotos paieškos kategorijai. Priešingai, informuota paieška apima algoritmus, tokius kaip heuristinis gylis - pirmasis, heuristinis pločio pirmoji paieška ir A * paieška.
Išvada
Informuotoje paieškoje pateikiamas sprendimas dėl sprendimo, o neinformuotoje paieškoje nėra pasiūlymų dėl sprendimo. Tai leidžia neinformuotai atlikti paiešką ilgiau, kai įgyvendinamas algoritmas.
