Imidlertid, mellom informerte og uinformerte søketeknikker, er det informerte søket mer effektivt og kostnadseffektivt.
Sammenligningstabel
| Grunnlag for sammenligning | Informert søk | Uinformert søk |
|---|---|---|
| grunn~~POS=TRUNC | Bruker kunnskap for å finne trinnene for løsningen. | Ingen bruk av kunnskap |
| Effektivitet | Meget effektiv som forbruker mindre tid og pris. | Effektivitet er mediatorisk |
| Koste | Lav | Relativt høy |
| Opptreden | Finner løsningen raskere | Hastigheten er tregere enn informert søk |
| algoritmer | Dybde-første søk, bredde-første søk og laveste pris første søk | Heuristisk dybde første og bredde-første søk, og A * søk |
Definisjon av informert søk
Den informerte søketeknikken utnytter problemspesifikke kunnskaper for å gi et ledd i løsningen av problemet. Denne typen søkestrategi forhindrer faktisk algoritmer i å snuble om målet og retningen til løsningen. Informert søk kan være fordelaktig når det gjelder kostnadene der optimaliteten oppnås ved lavere søkekostnader.
For å søke en optimal bane kostnad i en graf ved å implementere informert søk strategi er de mest lovende noder n satt inn i heuristisk funksjon h (n). Deretter returnerer funksjonen et ikke-negativt reelt tall som er en omtrentlig sti-kostnad beregnet fra node n til målkoden.
Her er den viktigste delen av den informerte teknikken den heuristiske funksjonen som letter til å gi videre kunnskap om problemet til algoritmen. Som et resultat bidrar det til å finne veien til målet gjennom de ulike nabolagene. Det finnes ulike algoritmer basert på informert søk som heuristisk dybde-første søk, heuristisk bredde-første søk, A * -søk osv. La oss nå forstå heuristisk dybde - første søk.
Heuristisk Dybde Første Søk
I likhet med dybde-første søkemetode som er gitt nedenfor, gir heuristisk dybde første søk en sti, men krysser alle stier fra den valgte banen før du velger en annen sti. Men det velger den beste banen lokalt. I tilfeller der den minste heuristiske verdien er prioritet for grensen, er den kjent som best første søk.
En annen informert søkalgoritme er A * -søk som fusjonerer konseptet med laveste pris først og beste første søk. Denne metoden vurderer både banekostnad og heuristisk informasjon i prosessen med å søke og velge banen som skal utvides. Anslått total banekost som brukes for hver bane som ligger på grensen fra start til målknutepunktet. Derfor bruker den to funksjoner samtidig - kostnaden (p) er kostnaden for den oppdagede banen, og h (p) er den estimerte verdien av banekostnaden fra startnoden til målkoden.
Definisjon av uinformert søk
Det uinformerte søket er forskjellig fra informert søk i den måten at det bare gir problemdefinisjonen, men ikke noe videre skritt for å finne løsningen på problemet. Hovedformålet med uinformert søk er å skille mellom mål- og ikke-måltilstanden, og det ignorerer helt destinasjonen den er på vei mot i banen til den oppdager målet og rapporterer etterfølgeren. Denne strategien er også kjent som et blindt søk.
Det finnes ulike søkealgoritmer under denne kategorien, for eksempel dybde-første søk, enhetlig kostnadssøk, bredde-første søk og så videre. La oss nå forstå konseptet bak det uinformerte søket ved hjelp av dybde-første søk.
Dybde Første søk
I dybden første søk, brukes en siste i første ut-stakken til å legge til og fjerne nodene. Bare ett knutepunkt blir lagt til eller fjernet om gangen, og det første elementet som fjernes fra grensen på stakken, vil være det siste elementet som legges til stakken. Ved å ansette stakk i grensen resulterer i søken av stier videre i dybden første måte. Når en kortest og optimal bane blir søkt ved hjelp av dybde-første søk, blir banen som er opprettet av de tilstøtende knutepunktene, fullført først, selv om den ikke er den ønskede. Deretter søges alternativveien gjennom backtracking.
Algoritmen velger med andre ord det første alternativet ved hver knutepunkt og springer tilbake til et annet alternativ til den har krysset alle stier fra første valg. Dette gir også et problem hvor søket kan slutte å stoppe på grunn av uendelige løkker (sykluser) i grafen.
Viktige forskjeller mellom informert og uinformert søk
- Den tidligere informerte søketeknikken bruker kunnskap for å finne løsningen. På den annen side bruker den sistnevnte uinformerte søketeknikken ikke kunnskap. I enklere termer finnes det ingen ytterligere informasjon om løsningen.
- Effektiviteten til informert søk er bedre enn det uinformerte søk.
- Uinformert søk bruker mer tid og kostnader, da det ikke har noen anelse om løsningen i forhold til informert søk.
- Dybde-første søk, bredde-første søk og laveste pris første søk er algoritmene kommer under kategorien for det uinformerte søket. Imidlertid dekker informert søk algoritmer som heuristisk dybde-første, heuristisk bredde-første søk og A * -søk.
Konklusjon
Det informerte søket gir retningen om løsningen, mens det i uinformert søk ikke gis noe forslag til løsningen. Dette gjør uinformert søk lengre når algoritmen implementeres.
