Qual è la differenza tra un euristica e un algoritmo?

Question

Qual è la differenza tra un euristica e un algoritmo?

Answer 1

Un algoritmo è la descrizione di una soluzione automatizzata di un problema . Che cosa fa l'algoritmo è definito con precisione. La soluzione potrebbe o non potrebbe essere il migliore possibile, ma si sa fin dall'inizio che tipo di risultato che si otterrà. Si implementa il algoritmo utilizzando un linguaggio di programmazione per ottenere (una parte di) un programma .

Ora, alcuni problemi sono difficili e si può non essere in grado di ottenere una soluzione accettabile in un tempo accettabile. In questi casi spesso si può ottenere un non troppo cattiva soluzione molto più velocemente, mediante l'applicazione di alcune scelte arbitrarie (ipotesi plausibili):. Questo è un euristica

Un'euristica è ancora una sorta di un algoritmo, ma uno che non esplorerà tutti i possibili stati del problema, o inizierà esplorando i più probabili.

Esempi tipici sono dai giochi. Quando si scrive un programma di scacchi gioco che si possa immaginare cercando ogni possibile mossa a un certo livello di profondità e l'applicazione di una certa funzione di valutazione alla scheda. Un'euristica escluderebbe rami pieni che iniziano con, ovviamente, si muove male.

In alcuni casi non si è alla ricerca della soluzione migliore, ma per qualsiasi soluzione di montaggio qualche vincolo. Una buona euristica aiuterebbe a trovare una soluzione in tempi brevi, ma può anche non riuscire a trovare se le uniche soluzioni sono negli Stati Uniti che ha scelto di provare.

Answer 2

• Un algoritmo è tipicamente deterministico e dimostrato di produrre un risultato ottimale
• Un euristico ha alcuna prova della correttezza, comporta spesso elementi casuali, e non può produrre risultati ottimali.

Molti problemi per i quali non algoritmo efficiente per trovare una soluzione ottimale è noto avere approcci euristici che producono risultati quasi ottimali molto rapidamente.

Ci sono alcune sovrapposizioni: "algoritmi genetici" è un termine accettato, ma a rigor di termini, quelli sono euristica, non algoritmi

.

Answer 3

euristica, in poche parole è un "un'ipotesi". Wikipedia spiega bene. Alla fine, un metodo "consenso generale" viene preso come una soluzione ottimale al problema specificato.

  

euristica è un aggettivo per   tecniche basati sull'esperienza che aiutano   nella soluzione dei problemi, l'apprendimento e   scoperta. Un metodo euristico è usato   venire rapidamente a una soluzione che è   sperato di essere vicino alla migliore possibile   risposta, o 'soluzione ottimale'.   Euristiche sono "regole del pollice",   ipotesi plausibili, giudizi intuitivi   o semplicemente il buon senso. Un'euristica è   un modo generale di risolvere un problema.   Euristica come un sostantivo è un altro nome   per i metodi euristici.

     

In termini più precisi, l'euristica   stare in piedi per le strategie che utilizzano facilmente   accessibile, anche se vagamente applicabile,   informazioni per controllare la soluzione dei problemi   di esseri umani e macchine.

Mentre un algoritmo è un metodo che contiene insieme finito di istruzioni utilizzate per risolvere un problema. Il metodo è stato dimostrato matematicamente o scientificamente a lavorare per il problema. Ci sono metodi formali e prove.

  

algoritmo euristico è un algoritmo che è in grado di produrre un   soluzione accettabile per un problema   molti scenari pratici, nel   la moda di un'euristica generale, ma   per i quali non v'è alcuna prova formale   la sua correttezza.

Answer 4

In realtà non credo che ci sia molto in comune tra di loro. Alcuni euristica uso algoritmo a loro logica (spesso per fare un minor numero di calcoli o di ottenere risultati più velocemente). Solitamente euristiche sono utilizzati nei cosiddetti algoritmi greedy.

L'euristica è una certa "conoscenza" che si assume è bene utilizzare al fine di ottenere la migliore scelta nel nostro algoritmo (quando una scelta deve essere assunto). Per esempio ... un'euristica negli scacchi potrebbe essere (sempre prendere la regina degli avversari, se è possibile, dal momento che sai che questo è il dato più forte). Euristica non ti garantiscono che vi condurrà alla risposta corretta, ma (se le ipotesi sono corrette) spesso ottenere risposta, che sono vicino ai migliori in tempi molto più brevi.

Answer 5

algoritmo è un insieme autonomo passo-passo delle operazioni da eseguire 4 , tipicamente interpretata come una sequenza finita di istruzioni (computer o umano) per determinare una soluzione ad un problema come: esiste un percorso da a a B, o qual è il percorso più piccolo tra a e B. In quest'ultimo caso, si potrebbe anche accontentarsi di un 'ragionevolmente vicino' soluzione alternativa.

Ci sono alcune categorie di algoritmi, di cui l'algoritmo euristico è uno. A seconda delle (provati) proprietà dell'algoritmo, in questo caso, cade in una di queste tre categorie (nota 1):

• esatta : la soluzione è dimostrato di essere un ottimale ( o esattamente soluzione) al problema di input
• ravvicinamento : la deviazione del valore della soluzione è dimostrato di essere mai più lontano dal valore ottimale di alcuni pre-definito limite (per esempio, non più del 50% maggiore del valore ottimale)
• euristica : l'algoritmo non è stato dimostrata ottimale, né in un pre-definito bound della soluzione ottimale

Si noti che un algoritmo di approssimazione è anche un euristico, ma con la proprietà più forte che c'è un dimostrato vincolato alla soluzione (valore) emette.

Per alcuni problemi, nessuno ha mai trovato un algoritmo 'efficiente' per calcolare le soluzioni ottimali (nota 2). Uno di questi problemi è il ben noto problema del commesso viaggiatore. algoritmo Christophides' per il problema del commesso viaggiatore, per esempio, veniva chiamato un euristica , in quanto non è stato provato che era meno di 50% della soluzione ottimale. Poiché è stato dimostrato, tuttavia, l'algoritmo Christophides' si riferisce più accuratamente come un algoritmo di approssimazione.

A causa di restrizioni su ciò che i computer possono fare, non è sempre possibile in modo efficiente trovare il migliore soluzione possibile. Se c'è abbastanza struttura in un problema, ci può essere un modo efficace per attraversare lo spazio delle soluzioni, anche se lo spazio delle soluzioni è enorme (vale a dire nel più breve problema del cammino).

euristiche sono in genere applicati per migliorare il tempo di esecuzione degli algoritmi, con l'aggiunta di 'informazioni esperto' o 'ipotesi plausibili' per guidare la direzione di ricerca. In pratica, un'euristica può anche essere un sub-routine per un algoritmo ottimale, per determinare dove cercare prima .

(nota 1) : Inoltre, gli algoritmi sono caratterizzati dal fatto che comprendono elementi casuali o non deterministici. Un algoritmo che esegue sempre allo stesso modo e produce la stessa risposta, si chiama deterministica.

(nota 2) : Questo è chiamato il P vs NP problema, ed i problemi che sono classificati come NP-completi e NP-hard è improbabile che avere un algoritmo 'efficiente'. Nota; come @Kriss accennato nei commenti, ci sono anche 'peggio' tipi di problemi, che possono avere bisogno di tempo esponenziale o lo spazio per il calcolo.

Ci sono diverse risposte che rispondono parte della domanda. Ho ritenuto loro meno completa e non sufficientemente preciso, e non ha deciso di modificare la risposta accettata fatta da @Kriss

Answer 6

euristiche sono algoritmi, quindi in questo senso non c'è nessuno, però, l'euristica adottare un approccio 'indovinare' alla soluzione dei problemi, ottenendo una risposta 'abbastanza buono', piuttosto che trovare una soluzione 'migliore possibile'.

Un buon esempio è dove si ha una molto difficile (leggi NP-completo) problema si desidera una soluzione per, ma non hanno il tempo per arrivare ad essa, in modo da avere per usare una buona soluzione abbastanza sulla base di un algoritmo euristico , come trovare una soluzione ad un problema del commesso viaggiatore utilizzando un algoritmo genetico.

Answer 7

Algoritmo è una sequenza di alcune operazioni che dato un input calcola qualcosa (una funzione) ed emette il risultato.

algoritmo può produrre un valori esatti o approssimati.

Si può anche calcolare un valore casuale che è con alta probabilità vicino al valore esatto.

Un algoritmo euristico utilizza alcune informazioni sui valori di ingresso e non calcola il valore esatto (ma potrebbe essere vicina al valore ottimale). In alcuni casi particolari, euristica può trovare soluzione esatta.

Answer 8

Un algoritmo è un insieme ben definito di istruzioni per risolvere un problema, Euristica coinvolgere utilizzando un approccio di apprendimento e di scoperta per raggiungere una soluzione.

Quindi, se si sa come risolvere un problema quindi utilizzare un algoritmo. Se avete bisogno di sviluppare una soluzione allora è euristica.

Answer 9

Un'euristica è di solito un'ottimizzazione o di una strategia che di solito fornisce una buona risposta abbastanza, ma non sempre e raramente la migliore risposta. Ad esempio, se si dovesse risolvere il problema del commesso viaggiatore con forza bruta, scartando una soluzione parziale una volta il suo costo supera quello della migliore soluzione attuale è un euristico: volte aiuta, altre volte non fa, e sicuramente doesn' t migliorare la (-oh grande notazione) tempo di esecuzione teorica dell'algoritmo

Answer 10

Credo euristica è più di un vincolo utilizzato in apprendimento basato Modello in artificiale intelligente dal momento che i futuri Stati soluzione sono difficili da prevedere.

Ma poi il mio dubbio dopo aver letto sopra risposte è "Come sarebbe euristica può essere applicata con successo utilizzando tecniche di ottimizzazione stocastica? O possono funzionare come algoritmi a pieno titolo quando viene utilizzato con Ottimizzazione stocastica?"

http://en.wikipedia.org/wiki/Stochastic_optimization

Answer 11

Una delle migliori spiegazioni che ho letto viene dal grande libro Code Complete , che ora cito:

  

Un'euristica è una tecnica che consente di cercare una risposta. Suo   i risultati sono soggetti al caso perché un'euristica solamente come dice   a guardare, non quello di trovare. Non vi dice come ottenere direttamente   dal punto A al punto B; potrebbe anche non sapere dove il punto A e   punto B sono. In effetti, un'euristica è un algoritmo in un vestito da clown.   E 'meno prevedibilità in grado, è più divertente, e viene fornito senza un di 30 giorni,   garanzia di rimborso.

     

Ecco un algoritmo per la guida a casa di qualcuno: Prendere l'autostrada 167   a sud di Puy-Allup. Prendere l'uscita South Hill Mall e guidare 4,5 miglia   sulla collina. Girare a destra al semaforo dal negozio di alimentari, e quindi   prendere la prima a sinistra. Girare nel vialetto della casa grande abbronzatura sul   sinistra, in 714 North Cedar.

     

Ecco un'euristica per arrivare a casa di qualcuno: trovare l'ultimo   lettera che abbiamo inviato. Partenza per la città nell'indirizzo di ritorno. quando   si arriva in città, chiedere a qualcuno dove la nostra casa è. Tutti sanno   noi-qualcuno sarà lieto di aiutarvi. Se non riesci a trovare nessuno, chiamaci   da un telefono pubblico, e noi verremo a prendere.

     

La differenza tra un algoritmo e di un'euristica è sottile, e la   due termini over-lap un po '. Ai fini di questo libro, il principale   differenza tra i due è il livello di riferimento indiretto dal   soluzione. Un algoritmo fornisce direttamente le istruzioni. UN   euristica spiega come scoprire le istruzioni per te, o   almeno dove cercare per loro.

Answer 12

Trovano una soluzione subottimale senza alcuna garanzia per quanto riguarda la qualità della soluzione trovata, è ovvio che ha senso per lo sviluppo di euristiche solo polinomi. L'applicazione di questi metodi è adatto per risolvere i problemi del mondo reale o grandi problemi così difficili dal punto di vista computazionale, che per loro non c'è nemmeno un algoritmo in grado di trovare una soluzione approssimata in tempo polinomiale.