Echter, tussen zowel geïnformeerde als ongeïnformeerde zoektechnieken, is het geïnformeerde zoeken efficiënter en kosteneffectiever.
Vergelijkingstabel
| Basis voor vergelijking | Geïnformeerd zoeken | Niet-geïnformeerd zoeken |
|---|---|---|
| basis- | Gebruikt kennis om de stappen naar de oplossing te vinden. | Geen gebruik van kennis |
| rendement | Zeer efficiënt omdat het minder tijd en geld kost. | Efficiëntie is bemiddeling |
| Kosten | Laag | Relatief hoog |
| Prestatie | Vindt oplossing sneller | Snelheid is langzamer dan geïnformeerd zoeken |
| algoritmes | Diepte-eerst zoeken, eerst zoeken op de breedte en de eerste zoekopdracht met de laagste kosten | Heuristische diepte eerst en de eerste plaats zoekactie, en A * zoeken |
Definitie van geïnformeerd 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 van de oplossing. Een geïnformeerde zoekopdracht kan voordelig zijn in termen van de kosten waarbij de optimalisatie wordt bereikt tegen lagere zoekkosten.
Om een optimale padkosten in een grafiek te zoeken door 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 benaderende padkosten is, berekend vanaf knooppunt n naar het doelknooppunt.
Hier is het belangrijkste onderdeel van de geïnformeerde techniek de heuristische functie die het mogelijk maakt om de aanvullende kennis van het probleem aan het algoritme te geven. Als gevolg hiervan helpt het bij het vinden van de weg naar het doel via de verschillende aangrenzende knooppunten. Er zijn verschillende algoritmen gebaseerd op de geïnformeerde zoekopdracht, zoals heuristische diepte-eerste zoekopdracht, heuristische breedte-eerste zoekopdracht, A * zoeken, enzovoort. Laten we nu de heuristische diepte-eerste zoekopdracht begrijpen.
Heuristische diepte Eerste zoekopdracht
Vergelijkbaar met diepte-eerste zoekmethode die hieronder wordt gegeven. Heuristische diepte eerste zoekopdracht kiest een pad maar doorloopt alle paden vanaf het geselecteerde pad voordat een ander pad wordt gekozen. Het kiest echter het beste pad lokaal. In gevallen waarbij de kleinste heuristische waarde de prioriteit is voor de grens, staat deze bekend als de beste eerste zoekopdracht.
Een ander geïnformeerd zoekalgoritme is A * zoeken, waarbij het concept van de eerste en beste eerste zoekopdrachten met de laagste kosten wordt samengevoegd. Deze methode houdt rekening met zowel padkosten als heuristische informatie bij het zoeken en selecteren van het pad dat moet worden uitgebreid. Een geschatte totale padkosten die worden gebruikt voor elk pad dat zich op de grens van het begin tot het doelknooppunt bevindt. Daarom gebruikt het twee functies tegelijkertijd - kosten (p) zijn de kosten van het gevonden pad en h (p) is de geschatte waarde van de padkosten van het startknooppunt naar het doelknooppunt.
Definitie van ongeïnformeerd zoeken
De ongeïnformeerde zoekopdracht verschilt van geïnformeerd zoeken, net zoals de probleemdefinitie, maar geen verdere stap naar het vinden van de oplossing voor het probleem. Het primaire doel van ongeïnformeerd zoeken is om onderscheid te maken tussen de doel- en niet-doelstatus en negeert de bestemming waarnaar het pad op weg gaat volledig totdat het doel wordt ontdekt en de opvolger wordt gerapporteerd. Deze strategie staat ook bekend als een blinde zoekopdracht.
Er zijn verschillende zoekalgoritmen onder deze categorie, zoals zoeken op diepte eerst, zoeken naar uniforme kosten, eerst zoeken in de breedte, enzovoort. Laten we nu het concept achter de ongeïnformeerde zoekopdracht begrijpen met behulp van diepte-eerst zoeken.
Diepte Eerste zoekopdracht
Bij een eerste zoekactie in de diepte 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, zou het laatste element zijn dat aan de stapel wordt toegevoegd. Door stapel in de grens te gebruiken werden resultaten in het zoeken van paden in de diepte op de eerste manier verder gegaan. Wanneer een kortst en optimaal pad wordt gezocht met behulp van diepte-eerste zoekopdracht, wordt het pad dat door de aangrenzende knooppunten is gemaakt eerst voltooid, ook als dit niet het gewenste pad is. Vervolgens wordt het alternatieve pad door backtracking doorzocht.
Met andere woorden, het algoritme kiest het eerste alternatief bij elk knooppunt en gaat daarna terug naar een ander alternatief totdat het alle paden van de eerste selectie heeft doorlopen. Dit roept ook een probleem op waarbij het zoeken stopt met stoppen vanwege de oneindige lussen (cycli) in de grafiek.
Belangrijkste verschillen tussen geïnformeerde en ongeïnformeerd zoeken
- De eerste geïnformeerde zoektechniek gebruikt kennis om de oplossing te vinden. Aan de andere kant gebruikt de laatste ongeinformeerde zoektechniek geen kennis. In eenvoudiger bewoordingen is er geen verdere informatie over de oplossing.
- De efficiëntie van de geïnformeerde zoekopdracht is beter dan de ongeinformeerde zoekopdracht.
- Niet-geïnformeerd zoeken kost meer tijd en geld, omdat het geen idee heeft van de oplossing in vergelijking met geïnformeerd zoeken.
- Diepte-eerste zoekopdracht, eerste zoekbreedte op basis van breedte en laagste kosten eerste zoekopdracht zijn de algoritmen die vallen onder de categorie van de ongeïnformeerde zoekopdracht. Daartegenover staat dat gefundeerde zoekopdrachten betrekking hebben op de algoritmen, zoals heuristische diepte-eerst, heuristische breedte-eerste zoekopdracht en A * -zoeking.
Conclusie
De geïnformeerde zoekopdracht geeft de richting met betrekking tot de oplossing, terwijl in ongeïnformeerd zoeken geen suggestie wordt gegeven met betrekking tot de oplossing. Dit maakt een ongeïnformeerde zoekopdracht langer wanneer het algoritme is geïmplementeerd.
