Innehåll

• Jämförelsediagram
• Definition av informerad sökning
• Heuristisk djup Första sökning
• Definition av Oinformerad sökning
• Djup första sökning
• Slutsats

Sökning är en process för att hitta en sekvens av steg som behövs för att lösa alla problem. Den tidigare skillnaden mellan informerad och oinformerad sökning är att den informerade sökningen ger vägledning om var och hur man hittar lösningen. Omvänt ger den oinformerade sökningen ingen ytterligare information om problemet utom dess specifikation.

Mellan både informerade och oinformerade söktekniker är den informerade sökningen emellertid mer effektiv och kostnadseffektiv.

1. 1. Jämförelsediagram
   2. Definition
   3. Viktiga skillnader
   4. Slutsats

Jämförelsediagram

Grund 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 användning av kunskap
Effektivitet	Mycket effektiv eftersom det tar mindre tid och kostnad.	Effektivitet är medierande
Kosta	Låg	Relativt hög
Prestanda	Hitta lösning snabbare	Hastigheten är långsammare än informerad sökning
algoritmer	Heuristisk djup först och bredd-första sökning och A * sökning	Djup-första sökning, bredd-första sökning och lägsta kostnad första sökning

Definition av informerad sökning

Den informerade söktekniken använder den problemspecifika kunskapen för att ge en ledtråd till lösning av problemet. Denna typ av sökstrategi förhindrar 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 till lägre sökkostnader.

För att söka efter en optimal sökkostnad i en graf genom att implementera informerad sökstrategi infogas de mest lovande noderna i heuristfunktionen h (n). Därefter returnerar funktionen ett icke-negativt verkligt tal, vilket är en ungefärlig bankostnad 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 tillföra algoritmens ytterligare kunskap om problemet. Som ett resultat hjälper det 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örst-sökning, heuristisk bredd-först-sökning, A * -sökning osv. Låt oss nu förstå heuristisk djup-först-sökning.

Heuristisk djup Första sökning

Liknar den första djup-sökmetoden som ges nedan under heuristisk djup, den första sökningen väljer en sökväg men korsar alla sökvä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 de fall där det minsta heuristiska värdet är prioritet för gränsen, är det känt som bästa första sökning.

En annan informerad sökalgoritm är A * -sökning som slår samman konceptet med lägsta kostnad först och bästa första sökningar. Denna metod beaktar både sökkostnad och heuristisk information i processen att söka och välja den sökväg som ska utvidgas. En uppskattad total sökvägskostnad som används för varje väg som ligger på gränsen från början till målnoden. 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 för bankostnaden från startnoden till målnoden.

Definition av Oinformerad sökning

Den oinformerade sökningen skiljer sig från informerad sökning på det sättet att den bara ger problemdefinitionen men inget ytterligare steg för att hitta lösningen på problemet. Det primära syftet med oinformerad sökning är att skilja mellan målet och icke-måltillståndet, och det ignorerar fullständigt destinationen det är på väg in i sökvägen tills den upptäcker målet och rapporterar efterträdaren. Denna strategi är också känd som en blind sökning.

Det finns olika sökalgoritmer under denna kategori som djup-först-sökning, enhetlig kostnadssökning, bredd-först-sökning och så vidare. Låt oss nu förstå konceptet bakom den oinformerade sökningen med hjälp av en första djup-sökning.

Djup första sökning

Fördjupad första sökning, en Last in first out-stack används för att lägga till och ta bort noderna. Endast en nod läggs till eller tas bort åt gången och det första elementet som tas bort från buntens gräns skulle vara det sista elementet som läggs till i bunten. Genom att använda stapel i gränsen fortsatte sökningen av vägar på djupet första sättet. När en kortaste och optimal sökväg söks med djup-först-sökning avslutas den sökväg som skapas av de angränsande noderna först, även om den inte är den önskade. Sedan sökas den alternativa vägen genom backtracking.

Med andra ord, algoritmen väljer det första alternativet vid varje nod och sedan spårar tillbaka till ett annat alternativ tills den har korsat alla banor från första valet. Detta väcker också ett problem där sökningen kan upphöra att sluta på grund av oändliga slingor (cykler) i grafen.

1. Den tidigare informerade söktekniken använder kunskap för att hitta lösningen. Å andra sidan använder den sistnämnda oinformerade söktekniken inte kunskap. I enklare termer finns ingen ytterligare information om lösningen.
2. Effektiviteten hos den informerade sökningen är bättre än den oinformerade sökningen.
3. Oinformerad sökning tar mer tid och kostnader eftersom det inte har någon aning om lösningen jämfört med informerad sökning.
4. Djup-först-sökning, bredd-första sökning och lägsta kostnad första sökning är algoritmerna som hör till kategorin för den oinformerade sökningen. I motsats till detta täcker informerad sökning algoritmer som heuristisk djup-först, heuristisk bredd-först-sökning och A * -sökning.

Slutsats

Den informerade sökningen ger riktningen beträffande lösningen medan det i oinformerad sökning inte ges några förslag om lösningen. Detta gör oinformerad sökning längre när algoritmen implementeras.