Algoritmen: berekeningskosten en volgende heuristieken - dummies

Vaak ziet u dat een heuristische benadering, een die vertrouwt over zelfontdekking en produceert voldoende bruikbare resultaten (niet noodzakelijk optimaal, maar goed genoeg) is de methode die je echt nodig hebt om een probleem op te lossen. Door het algoritme een deel van het vereiste werk voor u te laten uitvoeren, bespaart u tijd en moeite, omdat u algoritmen kunt maken die patronen beter zien dan mensen.

Bijgevolg is zelfontdekking het proces waarbij het algoritme je een potentieel bruikbaar pad naar een oplossing laat zien (maar je moet nog steeds rekenen op menselijke intuïtie en begrip om te weten of de oplossing de juiste is). In de volgende secties worden technieken beschreven die u kunt gebruiken om de kosten van een algoritme te berekenen met behulp van heuristiek als een methode om de werkelijke bruikbaarheid van een bepaalde oplossing te ontdekken.

Het probleem representeren als een ruimte

A probleemruimte is een omgeving waarin een zoekactie naar een oplossing plaatsvindt. Een reeks toestanden en de operatoren die worden gebruikt om die toestanden te veranderen, representeren de probleemruimte. Overweeg bijvoorbeeld een tegeldoos met acht tegels in een frame van 3 x 3. Elke tegel toont een deel van een afbeelding en de tegels beginnen in een willekeurige volgorde, zodat de afbeelding vervormd is. Het doel is om één tegel tegelijk te verplaatsen om alle tegels in de juiste volgorde te plaatsen en de afbeelding te tonen.

De combinatie van de startstatus, de gerandomiseerde tegels en de doelstatus - de tegels in een bepaalde volgorde - is de probleeminstantie. U kunt de puzzel grafisch weergeven met behulp van een grafiek met probleemruimten. Elk knooppunt van de grafiek met probleemruimten geeft een staat weer (de acht tegels in een bepaalde positie). De randen vertegenwoordigen bewerkingen, zoals tegelnummer acht naar boven verplaatsen. Als u tegel 8 naar boven verplaatst, verandert de afbeelding - deze gaat naar een andere staat.

Het winnen van het spel door van de startstatus naar de doeltoestand te gaan is niet de enige overweging. Om het spel efficiënt op te lossen, moet u de taak uitvoeren in het kleinste aantal mogelijke zetten, wat betekent dat u het kleinste aantal operatoren gebruikt. Het minimale aantal zetten dat wordt gebruikt om de puzzel op te lossen, is de probleemdiepte.

U moet rekening houden met verschillende factoren bij het weergeven van een probleem als een spatie. U moet bijvoorbeeld rekening houden met het maximale aantal knooppunten dat in het geheugen past, wat de ruimtecomplexiteit vertegenwoordigt. Als u niet alle knooppunten tegelijkertijd in het geheugen kunt plaatsen, moet de computer bepaalde knooppunten op andere locaties opslaan, zoals de vaste schijf, waardoor het algoritme aanzienlijk kan vertragen.Als u wilt bepalen of de knooppunten in het geheugen passen, moet u rekening houden met de tijdcomplexiteit, het maximumaantal knooppunten dat is gemaakt om het probleem op te lossen. Daarnaast is het belangrijk om de vertakkingsfactor te beschouwen, wat het gemiddelde aantal knooppunten is dat in de grafiek met probleemruimten is gemaakt om een probleem op te lossen.

Willekeurig en gezegend door geluk

Het oplossen van een zoekprobleem met brute-force technieken is mogelijk. Het voordeel van deze aanpak is dat u geen domeinspecifieke kennis nodig hebt om een van deze algoritmen te gebruiken. Een brute-force-algoritme heeft de neiging om de eenvoudigst mogelijke aanpak voor het oplossen van het probleem te gebruiken. Het nadeel is dat een brute-force benadering alleen goed werkt voor een klein aantal knooppunten. Hier zijn enkele van de algemene brute-force zoekalgoritmen:

Breedste eerst zoeken: Deze techniek begint bij het wortelknooppunt, onderzoekt elk van de onderliggende knooppunten eerst en gaat dan pas naar het volgende niveau. Het gaat niveau voor niveau verder totdat het een oplossing vindt. Het nadeel van dit algoritme is dat het elk knooppunt in het geheugen moet opslaan, wat betekent dat het een aanzienlijke hoeveelheid geheugen gebruikt voor een groot aantal knooppunten. Deze techniek kan controleren op dubbele knooppunten, wat tijd bespaart, en het komt altijd met een oplossing.
Diepte-eerste zoekopdracht: Deze techniek begint bij het basisknooppunt en onderzoekt een reeks verbonden onderliggende knooppunten totdat deze een knooppunt van bladeren bereikt. Het vordert van tak tot tak tot het een oplossing vindt. Het nadeel van dit algoritme is dat het niet op dubbele knooppunten kan controleren, wat betekent dat het meerdere knooppunten meerdere malen kan doorlopen. In feite vindt dit algoritme mogelijk helemaal geen oplossing, wat betekent dat u een afkappunt moet definiëren om te voorkomen dat het algoritme oneindig zoekt. Een voordeel van deze aanpak is dat het geheugen efficiënt is.
Bidirectioneel zoeken: Deze techniek zoekt gelijktijdig van het basisknooppunt en het doelknooppunt tot de twee zoekpaden elkaar in het midden ontmoeten. Een voordeel van deze aanpak is dat het tijd efficiënt is omdat het de oplossing sneller vindt dan vele andere brute-force oplossingen. Bovendien gebruikt het geheugen efficiënter dan andere benaderingen en vindt het altijd een oplossing. Het grootste nadeel is de complexiteit van de implementatie, die zich vertaalt in een langere ontwikkelingscyclus.

Een heuristische en een kostenfunctie gebruiken

Voor sommige mensen klinkt het woord heuristiek gewoon ingewikkeld. Het zou net zo gemakkelijk zijn om te zeggen dat het algoritme een goede inschatting maakt en het vervolgens opnieuw probeert wanneer het faalt. In tegenstelling tot brute-force-methoden leren heuristische algoritmen. Ze gebruiken ook kostenfuncties om betere keuzes te maken. Bijgevolg zijn heuristische algoritmen complexer, maar ze hebben een duidelijk voordeel bij het oplossen van complexe problemen. Net als bij brute force-algoritmen zijn er veel heuristische algoritmen en elk heeft zijn eigen reeks voordelen, nadelen en speciale vereisten. De volgende lijst beschrijft enkele van de meest voorkomende heuristische algoritmen:

Pure heuristiek zoeken: Het algoritme breidt knooppunten uit in volgorde van hun kosten.Het onderhoudt twee lijsten. De gesloten lijst bevat de knooppunten die al zijn onderzocht; de open lijst bevat de knooppunten die het nog moet verkennen. In elke iteratie breidt het algoritme het knooppunt uit met de laagst mogelijke kosten. Alle onderliggende knooppunten worden in de gesloten lijst geplaatst en de kosten van de afzonderlijke kindknooppunten worden berekend. Het algoritme stuurt de onderliggende knooppunten met lage kosten terug naar de open lijst en verwijdert de onderliggende knooppunten met hoge kosten. Bijgevolg voert het algoritme een intelligente, op kosten gebaseerde zoekopdracht naar de oplossing uit.
A * zoeken: het algoritme volgt de kosten van knooppunten terwijl het ze onderzoekt met behulp van de vergelijking: f (n) = g (n) + h (n), waarbij
- n de knooppunt-ID is.
- g (n) zijn de kosten om het knooppunt tot nu toe te bereiken.
- h (n) zijn de geschatte kosten om het doel van het knooppunt te bereiken.
- f (n) zijn de geschatte kosten van het pad van n naar het doel.

Het idee is om eerst de meest veelbelovende paden te doorzoeken en dure paden te vermijden. Greedy best-first search: