Imidlertid er den informerede søgning både effektiv og omkostningseffektiv mellem både informerede og uinformerede søgeteknikker.
Sammenligningstabel
| Grundlag for sammenligning | Informeret søgning | Uinformeret søgning |
|---|---|---|
| Grundlæggende | Bruger viden for at finde frem til løsningen. | Ingen brug af viden |
| Effektivitet | Meget effektiv som forbruger mindre tid og omkostninger. | Effektivitet er mediatorisk |
| Koste | Lav | Forholdsvis høj |
| Ydeevne | Finder løsning hurtigere | Hastigheden er langsommere end informeret søgning |
| Algoritmer | Dybde-første søgning, bredde-første søgning og laveste pris første søgning | Heuristisk dybde første og bredde-første søgning, og A * søgning |
Definition af informeret søgning
Den informerede søgeteknik udnytter problemspecifik viden for at give et fingerpeg om løsningen af problemet. Denne type søgestrategi forhindrer faktisk algoritmerne i at snuble om målet og retningen til løsningen. Informeret søgning kan være fordelagtig med hensyn til omkostningerne, hvor optimaliteten opnås ved lavere søgekostnader.
For at søge en optimal vejpris i en graf ved at implementere informeret søgestrategi indsættes de mest lovende noder n til den heuristiske funktion h (n). Derefter returnerer funktionen et ikke-negativt realtall, som er en omtrentlig sti-pris beregnet fra knude n til målkoden.
Her er den vigtigste del af den informerede teknik den heuristiske funktion, som letter til at give algoritmen yderligere viden om problemet. Som følge heraf hjælper det med at finde vejen til målet gennem de forskellige nærliggende noder. Der findes forskellige algoritmer baseret på den informerede søgning, såsom heuristisk dybde-første søgning, heuristisk bredde-første søgning, A * søgning osv. Lad os nu forstå heuristisk dybde-første søgning.
Heuristisk dybde Første søgning
I lighed med dybde-første søgemetode, der er angivet nedenfor, vælger heuristisk dybde første søgning en sti, men krydser alle stier fra den valgte sti, inden du vælger en anden sti. Det vælger dog den bedste vej lokalt. I tilfælde hvor den mindste heuristiske værdi er prioriteringen for grænsen, så er den kendt som den bedste første søgning.
En anden informeret søgealgoritme er A * -søgning, der fusionerer begrebet lavpris første og bedste første søgninger. Denne metode betragter både vejomkostninger og heuristiske oplysninger i processen med at søge og vælge den sti, der skal udvides. Anslået total stykpris, der anvendes til hver sti, der befinder sig på grænsen fra start til målknudepunkt. Derfor bruger den to funktioner på samme tid - omkostningerne (p) er prisen på den opdagede vej, og h (p) er den anslåede værdi af baneomkostningerne fra startnoden til målknudepunktet.
Definition af uinformeret søgning
Den uinformerede søgning adskiller sig fra informeret søgning i den måde, at det bare giver problemdefinitionen, men ikke yderligere skridt til at finde løsningen på problemet. Det primære mål med uinformeret søgning er at skelne mellem mål- og ikke-måltilstanden, og det ignorerer fuldstændigt den destination, den er på vej mod i stien, indtil den opdager målet og rapporter efterfølgeren. Denne strategi er også kendt som en blind søgning.
Der er forskellige søgealgoritmer under denne kategori som dybde-første søgning, ensartet omkostningssøgning, bredde-første søgning og så videre. Lad os nu forstå konceptet bag den uinformerede søgning ved hjælp af dybde-første søgning.
Dybde Første søgning
I dybden første søgning anvendes en sidste i første ud-stak til at tilføje og fjerne knuderne. Kun ét knude er tilføjet eller fjernet ad gangen, og det første element fjernet fra stakken er det sidste element, der tilføjes til stakken. Ved at anvende stakken i grænsen resulterer i søgning af stier videre i dybden første måde. Når en korteste og optimale sti, der søges ved hjælp af dybde-første søgning, afsluttes stien, der oprettes af de tilstødende knuder først, selvom den ikke er den ønskede. Derefter søges den alternative vej gennem backtracking.
Med andre ord vælger algoritmen det første alternativ ved hvert knudepunkt og springer tilbage til et andet alternativ, indtil den har krydset alle stier fra første valg. Dette rejser også et problem, hvor søgningen ophører med at stoppe på grund af uendelige sløjfer (cykler), der er til stede i grafen.
Nøgleforskelle mellem informeret og uinformeret søgning
- Den tidligere informerede søgeteknik bruger viden for at finde løsningen. På den anden side bruger den sidstnævnte uinformerede søgteknik ikke viden. I enklere termer findes der ikke yderligere oplysninger om løsningen.
- Effektiviteten af den informerede søgning er bedre end den uinformerede søgning.
- Uinformeret søgning bruger mere tid og omkostninger, da det ikke har nogen anelse om løsningen i forhold til informeret søgning.
- Dybde-første søgning, bredde-første søgning og laveste pris første søgning er algoritmerne kommer under kategorien for den uinformerede søgning. Imidlertid dækker informeret søgning algoritmerne som heuristisk dybde-første, heuristisk bredde-første søgning og A * -søgning.
Konklusion
Den informerede søgning giver retningen om løsningen, mens der i uinformeret søgning ikke gives noget forslag til løsningen. Dette gør uinformeret søgning mere langvarig, når algoritmen implementeres.
