Video: Where good ideas come from | Steven Johnson 2024
Deel van algoritmen voor dummy's Cheat Sheet
De volgende tabel beschrijft algoritmen en algoritmetypen die u mogelijk handig vindt voor verschillende typen gegevensanalyse. (U kunt discussies van al deze algoritmen vinden in Algorithms For Dummies.)
Algoritme | Beschrijving | Nuttige link |
A * Zoeken | Het algoritme volgt de kosten van knooppunten terwijl het deze met behulp van de vergelijking: f (n) = g (n) + h (n), waarbij:
n is het knooppunt-ID g (n) zijn de kosten van het bereiken van het knooppunt tot nu toe h (n) zijn de geschatte kosten om de doel van het knooppunt f (n) is 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. |
Standford. edu |
Evenwichtige boom | Een soort boom die door middel van reorganisatie een evenwichtige structuur behoudt, zodat deze kortere toegangstijden biedt. Het aantal elementen aan de linkerkant verschilt maximaal één van de cijfers aan de rechterkant. | Webdocs |
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. | Planning. cs |
Binary Tree | Dit is een type boom met knooppunten die verbinding maken met nul (bladknooppunten), één of twee (vertakkingsknooppunten) andere knooppunten. Elk knooppunt definieert de drie elementen die het moet bevatten om connectiviteit en opslaggegevens te bieden: gegevensopslag, linkse verbinding en juiste verbinding. | cs. cmu. edu |
Breadth-First Search | Deze techniek begint bij het basisknooppunt, onderzoekt eerst elk van de onderliggende knooppunten en gaat dan alleen 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. | Khan Academcy |
Brute Force | Dit is een techniek van probleemoplossing waarin iemand elke mogelijke oplossing uitprobeert, op zoek naar de beste probleemoplossing. Brute-force technieken garanderen een best passende oplossing wanneer er een bestaat, maar zijn zo tijdrovend om te implementeren dat de meeste mensen ze vermijden. | Igm. univ |
Diepte-eerst zoeken | Deze techniek begint bij het wortelknooppunt en onderzoekt een reeks verbonden onderliggende knooppunten totdat deze een bladknooppunt 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 meer dan één keer dezelfde knooppaden 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. | Hacker Earth |
Divide and Conquer | Dit is een techniek van probleemoplossing waarbij het probleem wordt opgesplitst in de kleinst mogelijke stukjes en opgelost met behulp van de eenvoudigste benadering mogelijk. Deze techniek bespaart veel tijd en middelen in vergelijking met andere benaderingen, zoals brute kracht. Het garandeert echter niet altijd een optimaal resultaat. | Khan Academy |
Dijikstra | Dit is een algoritme dat wordt gebruikt om het kortste pad te vinden in een gerichte, gewogen grafiek (met positieve gewichten). | Geeks voor geeks |
Grafiek | Een grafiek is een soort boomextensie. Net als bij bomen, hebt u knooppunten die met elkaar verbonden zijn om relaties te creëren. In tegenstelling tot binaire bomen kan een grafiek echter meer dan een of twee verbindingen hebben. Grafiekknooppunten hebben vaak een veelvoud aan verbindingen. U ziet grafieken die worden gebruikt in plaatsen zoals kaarten voor GPS en allerlei andere plaatsen waarvoor de top-down benadering van een boom niet zal werken. | Tutorials |
Greedy Algorithms | De techniek om problemen op te lossen waarbij de oplossing vertrouwt op het beste antwoord voor elke stap van het probleemoplossingsproces. Greedy-algoritmen doen over het algemeen twee aannames:
Het maken van een optimale keuze bij een bepaalde stap is mogelijk. Door bij elke stap de optimale selectie te kiezen, is het vinden van een optimale oplossing voor het algehele probleem mogelijk. |
Zelfstudies |
Greedy Best-First Search (BFS) | Het algoritme kiest altijd het pad dat het dichtst bij het doel ligt met behulp van de vergelijking: f (n) = h (n). Dit specifieke algoritme kan vrij snel oplossingen vinden, maar het kan ook vastlopen in loops, dus veel mensen beschouwen het niet als een optimale benadering om een oplossing te vinden. | Centurion2 |
hashing | Dit is een methode om de locatie van een bepaald gegevensitem in de datastructuur te voorspellen (wat die structuur ook mag zijn) voordat u ernaar op zoek gaat. Deze benadering is afhankelijk van het gebruik van sleutels die in een index zijn geplaatst. Een hashfunctie verandert de sleutel in een numerieke waarde die door het algoritme in een hashtabel wordt geplaatst. Een hashtabel biedt de mogelijkheid om een index te maken die verwijst naar elementen in een gegevensstructuur, zodat een algoritme de locatie van de gegevens gemakkelijk kan voorspellen. | Tutorials |
Heap | Dit is een geavanceerde structuur waarmee gegevens kunnen worden ingevoegd in de boomstructuur. Het gebruik van gegevensinvoer maakt het sorteren sneller. Je kunt deze bomen verder classificeren als max. Heaps en min-heaps, afhankelijk van de mogelijkheid van de boom om onmiddellijk de maximale of minimale waarde in de boom te geven. | Tutorials |
Heuristieken | Dit is een techniek van probleemoplossing die berust op zelfontdekking en voldoende nuttige resultaten oplevert (niet noodzakelijkerwijs optimaal, maar goed genoeg) om een probleem goed genoeg aan te pakken zodat een betere oplossing niet mogelijk is. ' t noodzakelijk. Zelfontdekking is 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). | Northwest. edu |
MapReduce | Dit is een raamwerk om algoritmen te laten werken door parallel berekeningen te gebruiken (met behulp van meerdere computers die met elkaar zijn verbonden in een netwerk), waardoor algoritmen hun oplossingen sneller kunnen voltooien. | Hadoop Apache |
Mergesort | Mergesort is een op algemene doeleinden gebaseerde, vergelijkingsmethode voor het sorteren van gegevens. Het hangt af van een verdeel-en-heers aanpak om zijn taak uit te voeren. | Geeks voor geeks |
Nash Equilibrium | Dit is een speltheorie waarin de andere spelers de evenwichtsstrategie kennen voor de andere spelers, dus niemand heeft er iets aan te winnen door zijn of haar persoonlijke strategie te veranderen. Deze theorie ziet gebruik in elke vijandige situatie waarin de speler rekening moet houden met de beslissingen die door alle andere spelers worden genomen om het spel te winnen. | Khan Academy |
PageRank | PageRank is een algoritme voor het meten van het belang van een knooppunt in een grafiek. Dit algoritme vormt de basis van de kernalgoritmen van Google om relevante zoekopdrachten naar gebruikers te sturen. | Princeton. edu |
Pure Heuristic Search | Dit algoritme breidt nodes uit in volgorde van hun kosten. Het onderhoudt twee lijsten. De gesloten lijst bevat de knooppunten die al zijn onderzocht en de open lijst bevat de knooppunten die nog moeten worden onderzocht. 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. | World of Computing |
Quicksort | Dit is een sorteerstrategie voor algemeen gebruik die is gebaseerd op het partitioneren van arrays van gegevens in kleinere arrays. Het hangt af van een verdeel-en-heers aanpak om zijn taak uit te voeren. | Zelfstudies |
Ongebalanceerde structuur | Dit is een structuur die nieuwe gegevensitems plaatst waar nodig in de structuur zonder rekening te houden met de balans. Deze methode voor het toevoegen van items maakt het bouwen van de boom sneller maar vermindert de toegangssnelheid bij het zoeken of sorteren. | Quora |