Inhoud

• Vergelijkingstabel
• Definitie van geïnformeerde zoeken
• Heuristische diepte eerste zoekopdracht
• Definitie van niet-geïnformeerde zoekopdracht
• Diepte eerste zoekopdracht
• Gevolgtrekking

Zoeken is een proces van het vinden van een reeks stappen die nodig zijn om een ​​probleem op te lossen. Het eerdere verschil tussen geïnformeerde en niet-geïnformeerde zoekopdracht is dat de geïnformeerde zoekopdracht een leidraad biedt voor waar en hoe de oplossing te vinden. Omgekeerd geeft de niet-geïnformeerde zoekopdracht geen aanvullende informatie over het probleem, behalve de specificatie ervan.

Tussen geïnformeerde en niet-geïnformeerde zoektechnieken is het geïnformeerde zoeken echter efficiënter en kosteneffectiever.

1. 1. Vergelijkingstabel
   2. Definitie
   3. Belangrijkste verschillen
   4. Gevolgtrekking

Vergelijkingstabel

Basis voor vergelijking	Geïnformeerde zoekopdracht	Niet-geïnformeerde zoekopdracht
basis-	Gebruikt kennis om de stappen naar de oplossing te vinden.	Geen gebruik van kennis
rendement	Zeer efficiënt omdat het minder tijd en kosten kost.	Efficiëntie is mediatory
Kosten	Laag	Relatief hoog
Prestatie	Vindt oplossing sneller	Snelheid is langzamer dan geïnformeerde zoeken
algoritmes	Heuristische diepte eerst en breedte-eerst zoeken, en A * zoeken	Diepte-eerste zoekopdracht, breedte-eerste zoekopdracht en goedkoopste zoekopdracht

Definitie van geïnformeerde zoeken

De geïnformeerde zoektechniek maakt gebruik van de probleemspecifieke kennis om een ​​idee te geven van de oplossing van het probleem. Dit type zoekstrategie voorkomt eigenlijk dat de algoritmen struikelen over het doel en de richting naar de oplossing. Geïnformeerd zoeken kan voordelig zijn in termen van de kosten wanneer de optimaliteit wordt bereikt tegen lagere zoekkosten.

Om de optimale padkosten in een grafiek te zoeken door een geïnformeerde zoekstrategie te implementeren, worden de meest veelbelovende knooppunten n ingevoegd in de heuristische functie h (n). Vervolgens retourneert de functie een niet-negatief reëel getal dat een geschatte padkost is, berekend vanaf knooppunt n naar het doelknooppunt.

Het belangrijkste deel van de geïnformeerde techniek is hier de heuristische functie die het mogelijk maakt om de aanvullende kennis van het probleem aan het algoritme door te geven. Als gevolg hiervan helpt het de weg naar het doel te vinden via de verschillende aangrenzende knooppunten. Er zijn verschillende algoritmen op basis van de geïnformeerde zoekopdracht, zoals heuristische diepte-eerste zoekopdracht, heuristische breedte-eerste zoekopdracht, A * zoekopdracht, enzovoort. Laten we nu heuristische diepte-eerste zoekopdracht begrijpen.

Heuristische diepte eerste zoekopdracht

Vergelijkbaar met de diepte-eerste zoekmethode die hieronder wordt gegeven. Heuristische diepte-eerste zoekopdracht kiest een pad maar doorloopt alle paden van het geselecteerde pad voordat een ander pad wordt gekozen. Het kiest echter lokaal het beste pad. In gevallen waarin de kleinste heuristische waarde de prioriteit voor de grens is, staat deze bekend als de beste eerste zoekopdracht.

Een ander weloverwogen zoekalgoritme is A * zoeken, waarbij het concept van laagste kosten eerst en beste eerste zoekopdrachten wordt samengevoegd. Deze methode houdt rekening met zowel padkosten als heuristische informatie tijdens het zoeken en selecteren van het pad dat moet worden uitgebreid. Een geschatte totale padkosten die worden gebruikt voor elk pad dat zich aan de grens bevindt vanaf het begin tot het doelknooppunt. Daarom gebruikt het twee functies tegelijkertijd - kosten (p) zijn de kosten van het ontdekte pad en h (p) is de geschatte waarde van de padkosten van het startknooppunt naar het doelknooppunt.

Definitie van niet-geïnformeerde zoekopdracht

De niet-geïnformeerde zoekactie verschilt van de geïnformeerde zoekactie omdat het alleen de probleemdefinitie biedt, maar geen verdere stap voor het vinden van de oplossing voor het probleem. Het primaire doel van niet-geïnformeerde zoeken is om onderscheid te maken tussen de doel- en niet-doelstatus, en het negeert de bestemming waar het naartoe gaat in het pad volledig totdat het het doel ontdekt en de opvolger rapporteert. Deze strategie wordt ook wel een blinde zoekopdracht genoemd.

Er zijn verschillende zoekalgoritmen in deze categorie, zoals diepte-eerst zoeken, uniform zoeken op kosten, breedte-eerst zoeken, enzovoort. Laten we nu het concept achter de niet-geïnformeerde zoekopdracht begrijpen met behulp van diepte-eerst zoeken.

Diepte eerste zoekopdracht

Bij diepgaande eerste zoekopdracht wordt een Last in first out-stapel gebruikt om de knooppunten toe te voegen en te verwijderen. Er wordt slechts één knooppunt tegelijk toegevoegd of verwijderd en het eerste element dat van de grens van de stapel wordt verwijderd, is het laatste element dat aan de stapel wordt toegevoegd. Door het toepassen van stapel in de grens resulteert in het zoeken van paden die op de eerste manier diepgaand is verlopen. Wanneer een kortste en optimale pad wordt gezocht met behulp van diepte-eerst zoeken, wordt het pad dat is gemaakt door de aangrenzende knooppunten eerst voltooid, zelfs als dit niet de gewenste is. Vervolgens wordt het alternatieve pad gezocht via backtracking.

Met andere woorden, het algoritme kiest het eerste alternatief bij elk knooppunt en gaat vervolgens terug naar een ander alternatief totdat het alle paden van de eerste selectie heeft doorlopen. Dit werpt ook een probleem op waarbij het zoeken kan stoppen vanwege oneindige lussen (cycli) aanwezig in de grafiek.

1. De voormalige techniek voor geïnformeerd zoeken maakt gebruik van kennis om de oplossing te vinden. Aan de andere kant maakt de laatste niet-geïnformeerde zoektechniek geen gebruik van kennis. In eenvoudiger bewoordingen wordt er geen verdere informatie verstrekt over de oplossing.
2. De efficiëntie van de geïnformeerde zoekopdracht is beter dan de niet-geïnformeerde zoekopdracht.
3. Ongeïnformeerde zoeken kost meer tijd en kosten omdat het geen idee heeft van de oplossing in vergelijking met geïnformeerd zoeken.
4. Diepte-eerst zoeken, breedte-eerst zoeken en goedkoopste zoeken eerst zijn de algoritmen die vallen onder de categorie van de niet-geïnformeerde zoekopdracht. Daartegenover staan ​​geïnformeerde zoekopdrachten voor de algoritmen zoals heuristische diepte-eerst, heuristische breedte-eerst zoeken en A * zoeken.

Gevolgtrekking

De geïnformeerde zoekopdracht geeft de richting met betrekking tot de oplossing, terwijl bij niet-geïnformeerde zoekopdrachten geen suggestie wordt gegeven met betrekking tot de oplossing. Dit maakt niet-geïnformeerde zoekopdrachten langer wanneer het algoritme wordt geïmplementeerd.