Quelle est la différence entre une heuristique et un algorithme?

Question

Quelle est la différence entre une heuristique et un algorithme?

Answer 1

Un algorithme est la description d'une solution automatisée à un problème . Ce que l'algorithme n'est défini avec précision. La solution pourrait ou ne pourrait pas être le meilleur possible, mais vous savez dès le départ quel genre de résultat que vous obtiendrez. Vous mettez en oeuvre l'algorithme en utilisant un langage de programmation pour obtenir (une partie de) un programme .

Maintenant, certains problèmes sont difficiles et vous pouvez ne pas être en mesure d'obtenir une solution acceptable dans un temps acceptable. Dans ce cas, vous pouvez souvent obtenir une solution pas trop mal beaucoup plus rapidement, en appliquant des choix arbitraires (suppositions éclairées). Qui est une heuristique

Une heuristique est toujours une sorte d'un algorithme, mais qui ne sera pas explorer tous les états possibles du problème, ou va commencer par explorer les plus probables.

Des exemples typiques sont des jeux. Lors de l'écriture d'un programme de jeu d'échecs que vous pouvez imaginer d'essayer tous les mouvements possibles à un certain niveau de profondeur et d'appliquer une fonction d'évaluation au conseil d'administration. Une heuristique exclurait les branches complètes qui commencent par évidemment mauvais coups.

Dans certains cas, vous n'êtes pas la recherche de la meilleure solution, mais pour une solution adaptée une certaine contrainte. Une bonne heuristique aiderait à trouver une solution dans un court laps de temps, mais peut aussi ne pas trouver si les seules solutions sont dans les états qu'il a choisi de ne pas essayer.

Answer 2

• Un algorithme est généralement déterministe et éprouvée pour obtenir un résultat optimal
• Une heuristique n'a pas la preuve de l'exactitude, implique souvent des éléments aléatoires, et ne peut pas donner des résultats optimaux.

De nombreux problèmes pour lesquels aucun algorithme efficace pour trouver une solution optimale est connue ont des approches heuristiques qui donnent des résultats optimaux à court très rapidement.

Il y a des chevauchements: « algorithmes génétiques » est un terme accepté, mais à proprement parler, ce sont heuristiques, pas des algorithmes

.

Answer 3

Heuristique, en un mot est une « supposition ». Wikipedia explique bien. A la fin, une méthode « d'acceptation générale » est considérée comme une solution optimale au problème spécifié.

  

Heuristic est un adjectif pour   techniques basées sur l'expérience qui aident   dans la résolution de problèmes, l'apprentissage et   Découverte. Une méthode heuristique est utilisée   de venir rapidement à une solution qui est   espériez être proche de la meilleure possible   réponse, ou « solution optimale ».   Heuristiques sont des « règles de base »,   suppositions éclairées, les jugements intuitifs   ou tout simplement le bon sens. Une heuristique est   d'une manière générale de résoudre un problème.   Heuristiques comme un nom est un autre nom   des méthodes heuristiques.

     

En termes plus précis, heuristiques   reposer les stratégies utilisant facilement   accessible, bien que vaguement applicable,   informations pour contrôler la résolution problème   des êtres humains et machines.

Alors qu'un algorithme est une méthode contenant ensemble fini d'instructions utilisées pour résoudre un problème. La méthode a été mathématiquement ou scientifiquement prouvé à travailler pour le problème. Il existe des méthodes formelles et des preuves.

  

algorithme heuristique est un algorithme qui est capable de produire un   solution acceptable au problème dans   de nombreux scénarios pratiques, dans le   la mode d'une heuristique générale, mais   pour lesquels il n'y a pas de preuve formelle de   son exactitude.

Answer 4

En fait, je ne pense pas qu'il y ait beaucoup de choses en commun entre eux. Certains utilisent des technologies heuristiques de l'algorithme dans leur logique (souvent de faire moins de calculs ou d'obtenir des résultats plus rapides). Habituellement heuristiques sont utilisés dans les soi-disant algorithmes gloutons.

Heuristique est une « connaissance » que nous supposons est bon d'utiliser afin d'obtenir le meilleur choix dans notre algorithme (quand doit être pris un choix). Par exemple ... un heuristiques dans les échecs pourrait être (toujours prendre les reine des adversaires si vous le pouvez, puisque vous savez c'est la figure plus forte). Heuristiques ne vous garantissent pas qui vous mènera à la bonne réponse, mais (si les hypothèses sont correctes) souvent obtenir réponse qui sont proches du meilleur dans le temps beaucoup plus court.

Answer 5

algorithme est un ensemble d'opérations étape par étape autonome à effectuer 4 , généralement interprétée comme une séquence d'instructions par ordinateur (ou humain) finie pour déterminer une solution à un problème tel que: il est un chemin de a à B, ou ce qui est le plus petit chemin entre a et B. Dans ce dernier cas, vous pourriez aussi se contenter d'une solution de rechange « raisonnablement proche » solution.

Il y a certaines catégories d'algorithmes, dont l'algorithme heuristique est un. En fonction des propriétés (prouvées) de l'algorithme dans ce cas, il tombe dans une de ces trois catégories (note 1):

• Exact : la solution est avérée être un optimale ( ou exactement solution) au problème d'entrée
• Approximation : la déviation de la valeur de la solution est prouvé être jamais plus loin de la valeur optimale que certains lié prédéfini (par exemple, jamais plus de 50% supérieure à la valeur optimale)
• Heuristique : l'algorithme n'a pas été avérée être optimale, ni dans une limite de la solution optimale prédéfinie

Notez qu'un algorithme d'approximation est aussi une heuristique, mais avec la propriété plus forte qu'il ya un prouvé lié à la solution (valeur) il émet.

Pour certains problèmes, Noone n'a jamais trouvé un algorithme « efficace » pour calculer les solutions optimales (note 2). L'un de ces problèmes est le problème du voyageur de commerce bien connu. L'algorithme de Christophides pour le voyageur de problème, par exemple, utilisé pour être appelé heuristique , car il n'a pas été prouvé qu'il était à moins de 50% de la solution optimale. Comme il a été prouvé, cependant, l'algorithme de Christophides est appelé plus précisément comme un algorithme d'approximation.

En raison des restrictions sur ce que les ordinateurs peuvent faire, il est toujours possible de efficacement trouver meilleur solution possible. S'il y a assez de structure dans un problème, il peut y avoir un moyen efficace de traverser l'espace de solution, même si l'espace de solution est énorme (par exemple dans le problème du plus court chemin).

heuristiques sont généralement appliqués pour améliorer le temps d'exécution des algorithmes, en ajoutant pour guider la direction de recherche « informations expert » ou « suppositions éclairées ». Dans la pratique, une heuristique peut également être une sous-routine pour un algorithme optimal pour déterminer où chercher premier .

(note 1) : En outre, les algorithmes sont caractérisés par le fait qu'ils comprennent des éléments aléatoires ou non-déterministes. Un algorithme qui exécute toujours de la même manière et produit la même réponse, est appelée déterministe.

(note 2) : Ceci est appelé le P vs NP problème, et les problèmes qui sont classés comme NP-complets et NP-dur ne sont pas susceptibles d'avoir un algorithme 'efficace'. Remarque; comme @Kriss mentionné dans les commentaires, il y a même des types « pire » des problèmes, ce qui peut avoir besoin de temps exponentielle ou de l'espace pour calculer.

Il y a plusieurs réponses qui répondent partie de la question. Je les estimais moins complète et pas assez précis, et décidé de ne pas modifier la réponse acceptée faite par @Kriss

Answer 6

heuristiques sont des algorithmes, donc dans ce sens il n'y a pas, cependant, heuristiques adopter une approche « conjecture » pour la résolution de problèmes, ce qui donne une réponse « assez bonne », plutôt que de trouver une solution « mieux possible ».

Un bon exemple est l'endroit où vous avez un problème très difficile (lire NP-complet) vous voulez une solution pour mais ne pas le temps d'arriver à lui, doivent donc utiliser une assez bonne solution basée sur un algorithme heuristique , comme la recherche d'une solution à un problème du voyageur de commerce en utilisant un algorithme génétique.

Answer 7

algorithme est une séquence de certaines opérations qui reçoit une entrée calcule quelque chose (fonction) et délivre en sortie un résultat.

L'algorithme peut donner une valeur exacte ou approximative.

Il peut aussi calculer une valeur aléatoire qui est avec une forte probabilité proche de la valeur exacte.

Un algorithme heuristique utilise un aperçu des valeurs d'entrée et calcule pas la valeur exacte (mais peut être proche de l'optimum). Dans certains cas particuliers, heuristique peut trouver la solution exacte.

Answer 8

Un algorithme est un ensemble clairement défini d'instructions pour résoudre un problème, Heuristique impliquent une approche d'utilisent l'apprentissage et la découverte pour parvenir à une solution.

Donc, si vous savez comment résoudre un problème puis utilisez un algorithme. Si vous avez besoin de développer une solution alors il est heuristiques.

Answer 9

Une heuristique est généralement une optimisation ou une stratégie qui fournit généralement une assez bonne réponse, mais pas toujours et rarement la meilleure réponse. Par exemple, si vous deviez résoudre le problème du voyageur de commerce avec la force brute, en rejetant une solution partielle une fois son coût est supérieur à celui de la meilleure solution actuelle est une heuristique: il est parfois utile, d'autres fois il ne le fait pas, et il doesn certainement » t améliorer le plan théorique (grand-oh notation) temps d'exécution de l'algorithme

Answer 10

Je pense que Heuristique est plus d'une contrainte utilisée dans l'apprentissage basé sur un modèle en intelligence artificielle puisque les états futurs de solution sont difficiles à prévoir.

Mais mon doute après avoir lu ci-dessus réponses est « Comment peut Heuristique être appliquée avec succès en utilisant des techniques d'optimisation stochastiques, ou peuvent-ils fonctionner comme des algorithmes à part entière lorsqu'ils sont utilisés avec Stochastique optimisation? »

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

Answer 11

L'une des meilleures explications que j'ai lu vient du grand livre code complet , que je cite maintenant:

  

Une heuristique est une technique qui vous aide à chercher une réponse. Ses   les résultats sont soumis au hasard, car une heuristique vous indique seulement comment   pour regarder, pas quoi trouver. Il ne vous dit pas comment obtenir directement   du point A au point B; il peut même pas savoir où le point A et   point B sont. En effet, une heuristique est un algorithme dans un costume de clown.   Il est moins prévisibles en, il est plus amusant, et il est sans 30 jours,   garantie de remboursement.

     

Voici un algorithme pour la conduite à la maison de quelqu'un: Prendre l'autoroute 167   au sud de Puy-Allup. Prendre la sortie South Hill Mall et conduire 4,5 miles   en haut de la colline. Tourner à droite à la lumière par l'épicerie, puis   prendre la première à gauche. Tourner dans l'allée de la grande maison bronzage sur   la gauche, au 714 North Cedar.

     

Voici une heuristique pour se rendre à la maison de quelqu'un: Trouvez la dernière   lettre que nous vous envoyé par la poste. Conduire à la ville à l'adresse de retour. Quand   vous arrivez à la ville, demandez à quelqu'un où notre maison est. Tout le monde sait   nous-quelqu'un sera heureux de vous aider. Si vous ne pouvez pas trouver quelqu'un, appelez-nous   à partir d'un téléphone public, et nous viendrons vous chercher.

     

La différence entre un algorithme et une heuristique est subtile, et la   deux termes un peu plus de tours. Aux fins de ce livre, le principal   la différence entre les deux est le niveau d'indirection de la   Solution. Un algorithme vous donne les instructions directement. UNE   heuristique vous indique comment découvrir les instructions pour vous-même, ou   au moins où chercher.

Answer 12

Ils trouvent une solution sous-optimale, sans aucune garantie quant à la qualité de la solution trouvée, il est évident qu'il est logique de développement de heuristiques ne polynôme. L'application de ces méthodes est adaptée pour résoudre des problèmes réels du monde ou de gros problèmes si difficiles du point de vue de calcul que pour eux il n'y a même pas un algorithme capable de trouver une solution approchée en temps polynomial.