Veuillez expliquer la différence entre les algorithmes "d'escalade" et "gourmands".Quelle est la différence entre les algorithmes "hill climbing" et "cupide"?
Il semble que les deux sont similaires, et j'ai un doute que "l'escalade" est un algorithme; ça semble être une optimisation. Est-ce correct?
Les algorithmes ascendants et gloutons sont tous les deux des heuristiques qui peuvent être utilisés pour des problèmes d'optimisation. Dans un problème d'optimisation , nous cherchons généralement une combinaison optimale ou l'ordre des éléments de problème. Une combinaison ou un ordre donné est une solution. Dans les deux cas, une solution peut être évaluée pour la comparer à d'autres solutions. Dans un heuristique heuristique, vous commencez avec une solution initiale. Générer une ou plusieurs solutions voisines Choisissez le meilleur et continuez jusqu'à ce qu'il n'y ait pas de meilleures solutions voisines. Cela donnera généralement une solution. En escalade, nous devons savoir comment évaluer une solution et comment générer un «voisin». Heuristique, nous avons besoin de savoir quelque chose de spécial sur le problème à l'étude. Un algorithme gourmand utilise l'information pour produire une solution unique.
Un bon exemple d'un problème d'optimisation est un sac à dos 0-1. Dans ce problème, il y a un sac à dos avec une certaine limite de poids, et un tas d'objets à mettre dans le sac à dos. Chaque article a un poids et une valeur. L'objectif est de maximiser la valeur des objets dans le sac tout en gardant le poids sous la limite.
Un algorithme glouton sélectionnerait des objets de plus haute densité et les placerait jusqu'à ce que le sac à dos soit plein. Par exemple, par rapport à une brique, un diamant a une valeur élevée et un petit poids, donc nous mettrons le diamant en premier.
Voici un exemple où un algorithme glouton échouerait: que vous avez une capacité 100. havresac avec vous disposez des éléments suivants:
l'algorithme glouton serait mis dans le diamant, puis être fait, ce qui donne une valeur de 1000. Mais la solution serait d'inclure les 5 pièces d'or, donnant la valeur 1050.L'algorithme d'escalade en montagne générerait une solution initiale - il suffit de choisir au hasard certains éléments (s'assurer qu'ils sont sous la limite de poids). Puis évaluez la solution - c'est-à-dire, déterminez la valeur. Générer une solution voisinePar exemple, essayez d'échanger un objet contre un autre (assurez-vous que vous êtes toujours sous la limite de poids). Si cette valeur est plus élevée, utilisez cette sélection et recommencez.
L'escalade n'est pas un algorithme glouton.
Oui, vous avez raison. L'escalade est une technique d'optimisation mathématique générale (voir: http://en.wikipedia.org/wiki/Hill_climbing). Un algorithme glouton est un algorithme qui choisit simplement le meilleur choix qu'il voit à ce moment et le prend. Un exemple de ceci est de faire des changements tout en minimisant le nombre de pièces (au moins avec USD). Vous prenez le maximum de la plus haute dénomination de pièce de monnaie, puis la plus élevée de la plus haute suivante, jusqu'à ce que vous atteigniez le montant nécessaire. De cette manière, l'escalade est un algorithme glouton.
Votre conclusion semble trompeuse. L'algorithme glouton que vous avez décrit construit la solution avec avidité, tandis que l'heuristique d'escalade atteint un optima local avec avidité. La seule différence est que l'étape gourmande dans le premier implique la construction d'une solution tandis que l'étape gourmande dans l'escalade implique la sélection d'un voisin (recherche locale gourmande). L'escalade est une heuristique gloutonne. Si vous voulez distinguer un algorithme d'une heuristique, je vous suggère de lire la réponse de Mikola, qui est plus précise. –