Tomēr starp informētiem un neinformētiem meklēšanas paņēmieniem informētā meklēšana ir efektīvāka un rentablāka.
Salīdzinājuma diagramma
| Salīdzināšanas pamats | Informēta meklēšana | Neinformēta meklēšana |
|---|---|---|
| Pamata | Izmanto zināšanas, lai atrastu risinājumus. | Nav zināšanu izmantošanas |
| Efektivitāte | Ļoti efektīvs, jo patērē mazāk laika un izmaksu. | Efektivitāte ir starpniecība |
| Izmaksas | Zems | Salīdzinoši augsts |
| Veiktspēja | Atrod risinājumu ātrāk | Ātrums ir lēnāks par informētu meklēšanu |
| Algoritmi | Dziļuma pirmā meklēšana, visplašākā meklēšana un zemākā izmaksu pirmā meklēšana | Heiristiskā dziļuma pirmā un plašākā meklēšana un A * meklēšana |
Informētās meklēšanas definīcija
Informatīvā meklēšanas tehnika izmanto problēmu specifiskās zināšanas, lai dotu priekšstatu par problēmas risinājumu. Šāda veida meklēšanas stratēģija faktiski novērš algoritmu klupšanu par mērķi un virzienu uz risinājumu. Informēta meklēšana var būt izdevīga izmaksu ziņā, ja optimizācija tiek panākta ar zemākām meklēšanas izmaksām.
Lai meklētu optimālu ceļa izmaksu grafikā, īstenojot informētu meklēšanas stratēģiju, heiristiskajai funkcijai h (n) tiek iekļauti visdaudzsološākie mezgli n. Tad funkcija atgriež ne-negatīvu reālo skaitli, kas ir aptuvena ceļa cena, kas aprēķināta no mezgla n līdz mērķa mezglam.
Šeit vissvarīgākā informētās tehnikas daļa ir heiristiskā funkcija, kas atvieglo papildu zināšanu nodošanu algoritmam. Tā rezultātā tas palīdz atrast ceļu uz mērķi, izmantojot dažādus blakus esošos mezglus. Pamatojoties uz informētu meklēšanu, ir dažādi algoritmi, piemēram, heiristiskā dziļuma pirmā meklēšana, heiristiskā platuma pirmā meklēšana, A * meklēšana utt. Tagad saprotam heiristisko dziļumu pirmo meklēšanu.
Heiristiskā dziļuma pirmā meklēšana
Līdzīgi kā dziļuma pirmā meklēšanas metode, kas dota zem heiristiskā dziļuma, pirmais meklējums izvēlas ceļu, bet šķērso visus ceļus no izvēlētā ceļa pirms cita ceļa izvēles. Tomēr tā izvēlas labāko ceļu vietējā līmenī. Gadījumos, kad mazākā heiristiskā vērtība ir robežas prioritāte, tad to sauc par labāko pirmo meklēšanu.
Vēl viens informēts meklēšanas algoritms ir A * meklēšana, kas apvieno zemāko izmaksu pirmo un labāko pirmo meklēšanu. Šī metode ņem vērā gan ceļa izmaksas, gan heiristisko informāciju paplašināmā ceļa meklēšanas un atlases procesā. Aprēķinātā kopējā ceļa maksa, ko izmanto katram ceļam, kas atrodas uz robežas no sākuma mezgla. Tāpēc tā izmanto divas funkcijas vienlaicīgi - izmaksas (p) ir atklātā ceļa izmaksas un h (p) ir aprēķinātā ceļa izmaksu vērtība no sākuma mezgla līdz mērķa mezglam.
Neinformētas meklēšanas definīcija
Neinformētā meklēšana atšķiras no informētas meklēšanas tādā veidā, ka tā tikai sniedz problēmas definīciju, bet ne vairāk, lai atrastu problēmas risinājumu. Neinformētās meklēšanas primārais mērķis ir nošķirt mērķa un mērķa valsti, un tas pilnībā ignorē galamērķi, uz kuru tas virzās ceļā, līdz tas atklāj mērķi un ziņotāju pēcteci. Šī stratēģija ir pazīstama arī kā aklā meklēšana.
Šajā kategorijā ir dažādi meklēšanas algoritmi, piemēram, dziļuma pirmā meklēšana, vienota izmaksu meklēšana, visplašākā meklēšana un tā tālāk. Tagad ar dziļuma pirmās meklēšanas palīdzību sapratīsim aiz neinformētās meklēšanas koncepcijas.
Pirmā meklēšana
Vispirms vispirms tiek meklēts pēdējais, kas tiek izmantots, lai pievienotu un noņemtu mezglus. Vienlaikus tiek pievienots vai noņemts tikai viens mezgls, un pirmais elements, kas noņemts no kaudzes robežas, būtu pēdējais elements, kas pievienots kaudzei. Izmantojot robežkontroles rezultātus, ceļu meklēšanā meklējami pirmie ceļi. Kad tiek meklēts īsākais un optimālākais ceļš, izmantojot dziļuma pirmo meklēšanu, ceļš, ko rada blakus esošie mezgli, vispirms tiek pabeigts, pat ja tas nav vēlamais. Pēc tam tiek meklēts alternatīvais ceļš, izmantojot atkāpšanos.
Citiem vārdiem sakot, algoritms izvēlas pirmo alternatīvu katrā mezglā, tad atkāpjas uz citu alternatīvu, līdz tas ir šķērsojis visus ceļus no pirmās izvēles. Tas rada arī problēmu, ja meklēšanu var pārtraukt, jo grafikā parādās bezgalīgas cilpas (cikli).
Galvenās atšķirības starp informēto un neinformēto meklēšanu
- Iepriekšējā informētā meklēšanas tehnika izmanto zināšanas, lai atrastu risinājumu. No otras puses, pēdējā neizmantotā meklēšanas tehnika neizmanto zināšanas. Vienkāršāk sakot, nav pieejama papildu informācija par risinājumu.
- Informētās meklēšanas efektivitāte ir labāka nekā neinformētā meklēšana.
- Nepazīstama meklēšana patērē vairāk laika un izmaksu, jo tai nav atrisinājuma par risinājumu, salīdzinot ar informētu meklēšanu.
- Pirmā meklēšana pēc dziļuma, visplašākā meklēšana un zemākā izmaksu meklēšana ir algoritmi, kas ietilpst neinformētās meklēšanas kategorijā. Pretstatā informētam meklējumam ir tādi algoritmi kā heiristiskais dziļums - pirmais, heiristiskais platums - pirmais meklējums un A * meklēšana.
Secinājums
Informēta meklēšana nodrošina virzienu attiecībā uz risinājumu, bet neinformētā meklējumā par risinājumu nav sniegts neviens ieteikums. Tas padara neinformētu meklēšanu ilgāku, kad tiek īstenots algoritms.
