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

• un algorithme est généralement déterministe et il est prouvé qu'il donne un résultat optimal
• une heuristique n'a aucune preuve d'exactitude, implique souvent des éléments aléatoires et peut ne pas donner de résultats optimaux.

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

Il y a quelques chevauchements: "algorithmes génétiques" est un terme accepté, mais à proprement parler, ce sont heuristiques, pas algorithmes.

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

Heuristique 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 rapidement arriver à une solution qui est espéré être proche du meilleur possible réponse, ou "solution optimale". Les heuristiques sont des "règles de pouce", suppositions instruites, jugements intuitifs ou tout simplement du bon sens. Une heuristique est une façon générale de résoudre un problème. Heuristiques comme un nom est un autre nom pour les méthodes heuristiques.

En termes plus précis, heuristiques stand pour les stratégies utilisant facilement accessible, mais vaguement applicable, informations pour contrôler la résolution de problèmes dans les êtres humains et les machines.

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

Algorithme Heuristique est un algorithme qui est capable de produire une solution acceptable à un problème dans de nombreux scénarios pratiques, dans le la mode d'un général de l'heuristique, mais pour lesquels il n'existe pas de preuve formelle de de son exactitude.

En fait, je ne pense pas qu'il y ait beaucoup de points communs entre eux. Certains algorithmes utilisent des heuristiques dans leur logique (souvent pour faire moins de calculs ou obtenir des résultats plus rapides). Habituellement, les heuristiques sont utilisées dans les algorithmes cupides.

L'heuristique est une "connaissance" que nous supposons bonne à utiliser afin d'obtenir le meilleur choix dans notre algorithme (quand un choix doit être pris). Exemple ... une heuristique aux échecs pourrait être (prenez toujours la Reine des adversaires si vous le pouvez, puisque vous sachez que c'est le chiffre le plus fort). Les heuristiques ne vous garantissent pas que vous conduirez à la bonne réponse, mais (si les hypothèses sont correctes) obtiennent souvent des réponses qui sont proches du meilleur dans un temps beaucoup plus court.

Les heuristiques sont des algorithmes, donc en ce sens il n'y en a pas, cependant, les heuristiques adoptent une approche "conjecture" de la résolution de problèmes, donnant une réponse "assez bonne", plutôt que de trouver une solution "meilleure possible".

Un bon exemple est celui où vous avez un problème très dur (lire NP-complete) pour lequel vous voulez une solution mais n'avez pas le temps d'y arriver, donc vous devez utiliser une solution assez bonne basée sur un algorithme heuristique, comme trouver une solution à un problème de vendeur ambulant en utilisant un algorithme heuristique. algorithme génétique.

Algorithme est une séquence de certaines opérations qui donné une entrée calcule quelque chose (une fonction) et génère un résultat.

Algorithme peut donner une valeur exacte ou approximative.

Il peut également 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 ne calcule pas la valeur exacte (mais peut être proche de optimale). Dans certains cas particuliers, heuristique peut trouver une solution exacte.

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

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

Un algorithme {[2] } est un ensemble d'opérations étape par étape autonome à effectuer 4, généralement interprété comme une séquence finie d'instructions (informatiques ou humaines) pour déterminer une solution à un problème tel que: y a-t-il un chemin de A à B, ou quel est le plus petit chemin entre A et B. Dans ce dernier cas, vous pourriez également être satisfait d'une solution alternative "raisonnablement proche".

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

• Exact: la solution s'avère être une solution optimale (ou exacte) au problème d'entrée
• Approximation: Il est prouvé que la déviation de la valeur de la solution n'est jamais plus éloignée de la valeur optimale qu'une limite prédéfinie (par exemple, jamais plus de 50% plus grande que la valeur optimale valeur)
• heuristique: l'algorithme n'a pas été prouvé pour être optimal, ni dans une limite prédéfinie de la solution optimale

Notez qu'un algorithme d'approximation est également une heuristique, mais avec la propriété la plus forte qu'il existe une liaison prouvée à la solution (valeur) qu'il génère.

Pour certains problèmes, personne n'a jamais trouvé un algorithme "efficace" pour calculer les solutions optimales (note 2). L'un de ces problèmes est le voyage bien connu Problème De Voyageur De Commerce. L'algorithme de Christophides pour le problème du vendeur ambulant, par exemple, était appelé une heuristique , car il n'était pas prouvé qu'il était à moins de 50% de la solution optimale. Comme il a été prouvé, cependant, L'algorithme de Christophides est plus précisément appelé un algorithme d'approximation.

En Raison de restrictions sur ce que les ordinateurs peuvent faire, il n'est pas toujours possible de efficace trouver la meilleurs solution possible. Si 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 (c'est-à-dire dans le problème du chemin le plus court).

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

(note 1): De plus, les algorithmes sont caractérisés par l'inclusion d'éléments aléatoires ou non déterministes. Un algorithme qui s'exécute toujours de la même manière et produit la même réponse, est appelé déterministe.

(note 2) : Ceci est appelé le problème P vs NP, et les problèmes qui sont classés comme NP-complete et NP-hard sont peu susceptibles d'avoir un algorithme "efficace". Note; comme @Kriss l'a mentionné dans les commentaires, il y a même des types de problèmes "pires", qui peuvent nécessiter un temps exponentiel ou de l'espace de calcul.

Il y a plusieurs réponses qui répondent à une partie de la question. Je les ai jugés moins complets et pas assez précis, et j'ai décidé de ne pas modifier la réponse acceptée faite par @ Kriss

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 vendeur ambulant avec la force brute, rejeter une solution partielle une fois que son coût dépasse celui de la meilleure solution actuelle est une heuristique: parfois cela aide, d'autres fois ce n'est pas le cas, et cela n'améliore certainement pas le temps d'exécution théorique (notation big-oh) de l'algorithme

Je pense que L'heuristique est plus une contrainte utilisée dans le modèle basé sur L'apprentissage dans Artificial Intelligent puisque les futurs états de solution sont difficiles à prédire.

Mais alors mon doute après avoir lu les réponses ci-dessus est "Comment L'heuristique peut-elle être appliquée avec succès en utilisant des Techniques D'optimisation Stochastique? ou peuvent-ils fonctionner comme des algorithmes à part entière lorsqu'ils sont utilisés avec L'optimisation Stochastique?"

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

L'une des meilleures explications que j'ai lues vient du grand livre Code Complete , que je cite maintenant:

Une heuristique est une technique qui vous aide à chercher une réponse. Son les résultats sont sujets au hasard car une heuristique vous indique seulement comment pour look, pas de quoi trouver. Il ne vous dit pas comment obtenir directement du point A au point B; il pourrait même ne pas savoir où le point A et point B sont. En effet, une heuristique est un algorithme dans un costume de clown. C'est moins prédire-mesure, il est plus amusant, et il vient sans un 30-jour, garantie de retour.

Voici un algorithme pour conduire chez quelqu'un: prendre L'autoroute 167 sud à Puyallup. Prenez la sortie South Hill Mall et conduisez 4,5 miles en haut de la colline. Tournez à droite au feu près de l'épicerie, puis prendre la première à gauche. Tournez dans l'allée de la grande maison de bronzage sur à gauche, au 714 North Cedar.

Voici une heuristique pour se rendre à la maison de quelqu'un: Trouver le dernier lettre que nous avons envoyé vous. Conduire à la ville à l'adresse de retour. Lorsque vous arrivez en ville, demandez à quelqu'un où est notre maison. Tout le monde le sait nous-quelqu'un sera heureux de vous aider. Si vous ne trouvez personne, appelez-nous d'un téléphone public, et nous viendrons vous chercher.

La différence entre un algorithme et une heuristique est subtile, et deux termes sur-tour un peu. 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. Un heuristique vous indique comment découvrir les instructions pour vous-même, ou au moins où chercher pour eux.

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évelopper des heuristiques uniquement polynomiales. L'application de ces méthodes est appropriée pour résoudre des problèmes réels ou de gros problèmes si maladroits du point de vue du calcul que pour eux il n'y a même pas un algorithme capable de trouver une solution approximative en temps polynomial.