Men mellan informerade och okända söktekniker är den informerade sökningen mer effektiv och kostnadseffektiv.
Jämförelsediagram
| Grunder för jämförelse | Informerad sökning | Oinformerad sökning |
|---|---|---|
| Grundläggande | Använder kunskap för att hitta stegen till lösningen. | Ingen kunskapsanvändning |
| Effektivitet | Mycket effektiv som förbrukar mindre tid och kostnad. | Effektivitet är mediatorisk |
| Kosta | Låg | Jämförelsevis hög |
| Prestanda | Hitta lösning snabbare | Hastigheten är långsammare än informerad sökning |
| algoritmer | Djup-första sökning, bredd-första sökning och lägsta kostnad första sökning | Heuristisk djup första och bredd-första sökningen, och A * -sökning |
Definition av informerad sökning
Den informerade söktekniken utnyttjar problemspecifik kunskap för att ge en ledtråd till lösningen av problemet. Denna typ av sökstrategi hindrar faktiskt att algoritmerna snubblar om målet och riktningen till lösningen. Informerad sökning kan vara fördelaktig när det gäller kostnaden där optimaliteten uppnås med lägre sökkostnader.
För att söka en optimal vägkostnad i ett diagram genom att implementera en informerad sökstrategi införs de mest lovande noderna n till den heuristiska funktionen h (n). Därefter returnerar funktionen ett icke-negativt realt tal som är en ungefärlig vägkostnad beräknad från nod n till målnoden.
Här är den viktigaste delen av den informerade tekniken den heuristiska funktionen som underlättar för att ge ytterligare kunskap om problemet till algoritmen. Som ett resultat bidrar det till att hitta vägen till målet genom de olika angränsande noderna. Det finns olika algoritmer baserade på den informerade sökningen som heuristisk djup-första sökning, heuristisk bredd-första sökning, A * -sökning etc. Låt oss nu förstå heuristisk djup - första sökningen.
Heuristisk djup Första sökningen
I likhet med djup första sökmetod som anges nedan väljer heuristiskt djup första sökningen en sökväg men passerar alla vägar från den valda sökvägen innan du väljer en annan sökväg. Men det väljer den bästa vägen lokalt. I fall där det minsta heuristiska värdet är prioriteringen för gränsen är den känd som bästa första sökningen.
En annan informerad sökalgoritm är A * -sökning som sammanfogar begreppet lägsta kostnad första och bästa första sökningar. Denna metod tar hänsyn till både vägkostnad och heuristisk information i processen att söka och välja den väg som ska utökas. En beräknad total vägkostnad som används för varje väg som ligger på gränsen från start till målnod. Därför använder den två funktioner samtidigt - kostnad (p) är kostnaden för den upptäckta sökvägen och h (p) är det uppskattade värdet av bankostnaden från startnoden till målnoden.
Definition av oinformerad sökning
Den obemannade sökningen skiljer sig från informerad sökning på det sättet att det bara ger problemdefinitionen men inget ytterligare steg för att hitta lösningen på problemet. Det främsta målet med oinformerad sökning är att skilja mellan målet och det icke-målmedvetna läget, och det ignorerar helt den destination det är på väg in i vägen tills det upptäcker målet och rapporter efterföljaren. Denna strategi kallas också en blind sökning.
Det finns olika sökalgoritmer under den här kategorin, såsom djup första sökning, enhetlig kostnadssökning, bredd-första sökning och så vidare. Låt oss nu förstå konceptet bakom den oinformerade sökningen med hjälp av djup första sökning.
Djup Första Sökningen
Fördjupad första sökning, en sista i första ut stapeln används för att lägga till och ta bort noderna. Endast en nod läggs till eller tas bort i taget och det första elementet som tas bort från stackens gräns är det sista elementet som läggs till i stapeln. Genom att använda stapel i gränsen resulterar sökningen av vägar på djupet i första hand. När en kortast och optimal sökväg sökes med hjälp av djup första sökning, är sökvägen som skapas av de intilliggande noderna färdigställda först även om den inte är den önskade. Då sökes den alternativa sökvägen genom backtracking.
Med andra ord väljer algoritmen det första alternativet vid varje nod och backspårar sedan till ett annat alternativ tills det har gått igenom alla vägar från första urvalet. Detta orsakar också ett problem där sökningen slutar sluta på grund av oändliga loopar (cykler) som finns i grafen.
Viktiga skillnader mellan informerad och oinformerad sökning
- Den tidigare informerade söktekniken använder kunskap för att hitta lösningen. Å andra sidan använder den senare oinformerade söktekniken inte kunskap. I enklare termer finns det ingen ytterligare information om lösningen.
- Effektiviteten hos den informerade sökningen är bättre än den obemannade sökningen.
- Oinformerad sökning förbrukar mer tid och kostnad eftersom det inte har någon aning om lösningen jämfört med informerad sökning.
- Djup-första sökning, bredd-första sökning och lägsta kostnad första sökning är algoritmerna faller under kategorin för den obemannade sökningen. Däremot täcker informerad sökning algoritmerna som heuristisk djup-första, heuristisk bredd-första sökning och A * -sökning.
Slutsats
Den informerade sökningen ger riktningen angående lösningen, medan det vid oinformerad sökning inte lämnas några förslag om lösningen. Detta gör oinformerad sökning mer långsiktig när algoritmen implementeras.
