Wat is het verschil tussen een heuristiek en een algoritme?
Antwoord 1, autoriteit 100%
Een algoritme is de beschrijving van een geautomatiseerde oplossing voor een probleem. Wat het algoritme doet, is nauwkeurig gedefinieerd. De oplossing kan al dan niet de best mogelijke zijn, maar u weet vanaf het begin wat voor resultaat u krijgt. Je implementeert het algoritmemet behulp van een programmeertaal om (een deel van) een programmate krijgen.
Sommige problemen zijn moeilijk en het is mogelijk dat u niet binnen een aanvaardbare tijd een acceptabele oplossing krijgt. In dergelijke gevallen kun je vaak veel sneller tot een niet al te slechte oplossing komen, door wat willekeurige keuzes toe te passen (onderlegde gissingen): dat is een heuristiek.
Een heuristiek is nog steeds een soort algoritme, maar een die niet alle mogelijke toestanden van het probleem zal onderzoeken, of zal beginnen met het onderzoeken van de meest waarschijnlijke.
Typische voorbeelden komen uit games. Bij het schrijven van een schaakprogramma kun je je voorstellen dat je elke mogelijke zet op een bepaald diepteniveau probeert en een evaluatiefunctie op het bord toepast. Een heuristiek sluit volledige takken uit die beginnen met duidelijk slechte zetten.
In sommige gevallen ben je niet op zoek naar de beste oplossing, maar naar een oplossing met een bepaalde beperking. Een goede heuristiek zou helpen om in korte tijd een oplossing te vinden, maar kan er ook niet in slagen om er een te vinden als de enige oplossingen zijn in de staten die het niet heeft geprobeerd te proberen.
Antwoord 2, autoriteit 31%
- Een algoritme is typisch deterministisch en het is bewezen dat het een optimaal resultaat oplevert
- Een heuristiek heeft geen bewijs van juistheid, bevat vaak willekeurige elementen en levert mogelijk geen optimale resultaten op.
Veel problemen waarvoor geen efficiënt algoritme bekend is om een optimale oplossing te vinden, hebben heuristische benaderingen die zeer snel bijna optimale resultaten opleveren.
Er zijn enkele overlappingen: “genetische algoritmen” is een geaccepteerde term, maar strikt genomen zijn dat heuristieken, geen algoritmen.
Antwoord 3, autoriteit 21%
Heuristisch, in een notendop is een ‘opgeleide gok’. Wikipedia legt het mooi uit. Aan het einde wordt een “algemene acceptatie”-methode genomen als een optimale oplossing voor het gespecificeerde probleem.
Heuristisch is een bijvoeglijk naamwoord voor
op ervaring gebaseerde technieken die helpen
bij het oplossen van problemen, leren en
ontdekking. Er wordt een heuristische methode gebruikt
om snel tot een oplossing te komen die
hoopte zo dicht mogelijk bij de best mogelijke te zijn
antwoord of ‘optimale oplossing’.
Heuristieken zijn “vuistregels”,
weloverwogen gissingen, intuïtieve oordelen
of gewoon gezond verstand. Een heuristiek is
een algemene manier om een probleem op te lossen.
Heuristiek als zelfstandig naamwoord is een andere naam
voor heuristische methoden.Om precies te zijn, heuristieken
staan voor strategieën die gemakkelijk worden gebruikt
toegankelijk, hoewel losjes toepasbaar,
informatie om het oplossen van problemen te beheersen
in mensen en machines.
Terwijl een algoritme een methode is die een eindige reeks instructies bevat die worden gebruikt om een probleem op te lossen. Het is wiskundig of wetenschappelijk bewezen dat de methode voor het probleem werkt. Er zijn formele methoden en bewijzen.
Heuristisch algoritmeis een algoritme dat in staat is om een
aanvaardbare oplossing voor een probleem in
veel praktische scenario’s, in de
mode van een algemene heuristiek, maar
waarvoor geen formeel bewijs is
de juistheid ervan.
Antwoord 4, autoriteit 8%
Een algoritmeis een op zichzelf staande, stapsgewijze reeks bewerkingen die moet worden uitgevoerd 4, meestal geïnterpreteerd als een eindige reeks (computer of menselijke) instructies om een oplossing voor een probleem te bepalen, zoals: is er een pad van A naar B, of wat is het kleinste pad tussen A en B. In het laatste geval kunt u ook genoegen nemen met een ‘redelijk dichtbij’ alternatieve oplossing.
Er zijn bepaalde categorieën algoritmen, waarvan het heuristische algoritme er één is. Afhankelijk van de (bewezen) eigenschappen van het algoritme valt het in dit geval in een van deze drie categorieën (noot 1):
- Exact: het is bewezen dat de oplossing een optimale ( of exacteoplossing) voor het invoerprobleem
- Approximation: het is bewezen dat de afwijking van de oplossingswaarde wees nooit verder verwijderd van de optimale waarde dan een vooraf gedefinieerde grens (bijvoorbeeld nooit meer dan 50% groter dan de optimale waarde)
- Heuristisch: het algoritme is niet bewezen optimaal te zijn, noch binnen een vooraf gedefinieerde grens van de optimale oplossing
Merk op dat een benaderingsalgoritme ook een heuristiek is, maar met de sterkere eigenschap dat er een bewezen gebondenheid is aan de oplossing (waarde) die het uitvoert.
Voor sommige problemen heeft niemand ooit een ‘efficiënt’ algoritme gevonden om de optimale oplossingen te berekenen (opmerking 2). Een van die problemen is het bekende handelsreizigersprobleem. Christophides’ algoritme voor het Travelling Salesman Problem, bijvoorbeeld, werd vroeger een heuristiekgenoemd, omdat niet bewezen was dat het binnen 50% van de optimale oplossing lag. Omdat het echter is bewezen, wordt het algoritme van Christophides nauwkeuriger een benaderingsalgoritme genoemd.
Vanwege beperkingen op wat computers kunnen doen, is het niet altijd mogelijk om efficiëntde besteoplossing te vinden. Als er voldoende structuur in een probleem is, kan er een efficiënte manier zijn om de oplossingsruimte te doorkruisen, ook al is de oplossingsruimte enorm (d.w.z. in het kortste padprobleem).
Heuristieken worden doorgaans toegepast om de looptijd van algoritmen te verbeteren door ‘expertinformatie’ of ‘opgeleide gissingen’ toe te voegen om de zoekrichting te sturen. In de praktijk kan een heuristiek ook een subroutine zijn voor een optimaal algoritme, om te bepalen waar eerstgezocht moet worden.
(opmerking 1): Bovendien worden algoritmen gekenmerkt door het feit of ze willekeurige of niet-deterministische elementen bevatten. Een algoritme dat altijd op dezelfde manier wordt uitgevoerd en hetzelfde antwoord geeft, wordt deterministisch genoemd.
(opmerking 2): Dit wordt het P vs NP-probleem genoemd, en problemen die zijn geclassificeerd als NP-compleet en NP-hard hebben waarschijnlijk geen ‘efficiënt’ algoritme. Opmerking; zoals @Kriss in de opmerkingen vermeldde, zijn er zelfs ‘slechtere’ soorten problemen, die mogelijk exponentiële tijd of ruimte nodig hebben om te berekenen.
Er zijn verschillende antwoorden die een deel van de vraag beantwoorden. Ik vond ze minder volledig en niet nauwkeurig genoeg, en besloot het geaccepteerde antwoord van @Kriss
niet te bewerken
Antwoord 5, autoriteit 6%
Eigenlijk denk ik niet dat ze veel gemeen hebben. Sommige algoritmen gebruiken heuristieken in hun logica (vaak om minder berekeningen te maken of snellere resultaten te krijgen). Meestal worden heuristieken gebruikt in de zogenaamde hebzuchtige algoritmen.
Heuristiek is enige “kennis” waarvan we aannemen dat deze goed is om te gebruiken om de beste keuze in ons algoritme te krijgen (wanneer een keuze moet worden gemaakt). Bijvoorbeeld … een heuristiek in schaken zou kunnen zijn (neem altijd de koningin van de tegenstander als je kunt, omdat je weet dat dit de sterkere figuur is). Heuristieken garanderen niet dat u naar het juiste antwoord zult leiden, maar (als de aannames correct zijn) krijgt u vaak antwoorden die in veel kortere tijd het beste benaderen.
Antwoord 6, autoriteit 4%
Een algoritme is een duidelijk gedefinieerde reeks instructies om een probleem op te lossen. Heuristieken omvatten het gebruik van een benadering van leren en ontdekken om tot een oplossing te komen.
Dus, als je weet hoe je een probleem moet oplossen, gebruik dan een algoritme. Als je een oplossing moet ontwikkelen, dan is dat heuristiek.
Antwoord 7, autoriteit 4%
Heuristieken zijn algoritmen, dus in die zin is er geen, maar heuristieken nemen een ‘gissing’-benadering bij het oplossen van problemen, wat een ‘goed genoeg’ antwoord oplevert, in plaats van een ‘best mogelijke’ oplossing te vinden.
Een goed voorbeeld is waar je een heel moeilijk (lees NP-compleet) probleem hebt waarvoor je een oplossing wilt, maar geen tijd hebt om er aan te komen, dus je moet een oplossing gebruiken die goed genoeg is op basis van een heuristisch algoritme , zoals het vinden van een oplossing voor een handelsreizigersprobleem met behulp van een genetisch algoritme.
Antwoord 8, autoriteit 4%
Algoritme is een reeks van enkele bewerkingen die gegeven een invoer iets (een functie) berekent en een resultaat oplevert.
Algoritme kan exacte of geschatte waarden opleveren.
Het kan ook een willekeurige waarde berekenen die met grote waarschijnlijkheid dicht bij de exacte waarde ligt.
Een heuristisch algoritme gebruikt enig inzicht in invoerwaarden en berekent geen exacte waarde (maar kan in de buurt van optimaal zijn).
In sommige speciale gevallen kan heuristiek een exacte oplossing vinden.
Antwoord 9, autoriteit 2%
Een heuristiek is meestal een optimalisatie of een strategie die meestal een goed genoeg antwoord geeft, maar niet altijd en zelden het beste antwoord. Als je bijvoorbeeld het handelsreizigersprobleem met brute kracht zou oplossen, is het een heuristiek om een gedeeltelijke oplossing weg te gooien zodra de kosten hoger zijn dan die van de huidige beste oplossing: soms helpt het, soms niet, en zeker niet’ de theoretische (big-oh-notatie) looptijd van het algoritme verbeteren
Antwoord 10, autoriteit 2%
Ik denk dat heuristiek meer een beperking is die wordt gebruikt in Learning Based Model in Artificial Intelligent, omdat de toekomstige oplossingstoestanden moeilijk te voorspellen zijn.
Maar mijn twijfel na het lezen van bovenstaande antwoorden is:
“Hoe zou Heuristic met succes kunnen worden toegepast met behulp van stochastische optimalisatietechnieken? of kunnen ze functioneren als volwaardige algoritmen wanneer ze worden gebruikt met stochastische optimalisatie?”
http://en.wikipedia.org/wiki/Stochastic_optimization
Antwoord 11, autoriteit 2%
Een van de beste verklaringen die ik heb gelezen komt uit het geweldige boek Code Complete, die ik nu citeer:
Een heuristiek is een techniek die u helpt bij het zoeken naar een antwoord. Zijn
resultaten zijn onderhevig aan toeval omdat een heuristiek u alleen vertelt hoe
te zoeken, niet wat te vinden. Het vertelt je niet hoe je direct kunt komen
van punt A naar punt B; het weet misschien niet eens waar punt A en
punt B zijn. In feite is een heuristiek een algoritme in een clownspak.
Het is minder voorspelbaar, het is leuker en het komt zonder 30 dagen,
geld-terug-garantie.Hier is een algoritme om naar iemands huis te rijden: Neem Highway 167
zuiden naar Puy-allup. Neem de afslag South Hill Mall en rijd 7,2 km
op de heuvel. Sla rechtsaf bij het licht bij de supermarkt, en dan
neem de eerste weg links. Draai de oprit van het grote bruine huis op
de linkerkant, op 714 North Cedar.Hier is een heuristiek om bij iemands huis te komen: Vind de laatste
brief die we u hebben gestuurd. Rijd naar de stad in het retouradres. Wanneer
als je naar de stad gaat, vraag iemand waar ons huis is. Iedereen weet
ons – iemand zal u graag helpen. Als je niemand kunt vinden, bel ons dan
vanaf een openbare telefoon, en we komen je halen.Het verschil tussen een algoritme en een heuristiek is subtiel, en de
twee termen overlappen elkaar enigszins. Voor de doeleinden van dit boek is de belangrijkste
verschil tussen de twee is het niveau van indirectheid van de
oplossing. Een algoritme geeft je direct de instructies. EEN
heuristiek vertelt u hoe u de instructies voor uzelf kunt ontdekken, of
tenminste waar je ze kunt zoeken.
Antwoord 12
Ze vinden een oplossing suboptimaal zonder enige garantie met betrekking tot de kwaliteit van de gevonden oplossing, het is duidelijk dat het voor de ontwikkeling van heuristiek alleen polynoom zinvol is. De toepassing van deze methoden is geschikt om problemen uit de echte wereld of grote problemen op te lossen die vanuit rekenkundig oogpunt zo onhandig zijn dat er zelfs geen algoritme is dat in staat is om een benaderende oplossing in polynomiale tijd te vinden.