heuristic suite

Suite heuristique

Note importante

Le projet n'est plus sous maintenance. Veuillez visiter Linq à A * pour la dernière version.

Aperçu

Heuristic Suite est une implémentation expérimentale d'une série d'algorithmes heuristiques dans la programmation générique. Le projet vise à fournir une infrastructure qui peut être appliquée à n'importe quel puzzle - tant que le puzzle peut être résolu avec l'algorithme.

Algorithmes implémentés:

• UN*
• Approfondissement itératif A * (Ida *)
• Meilleure première recherche
• Recursif Meilleure première recherche (RBFS)

La mise en œuvre est entièrement orientée objet et présente les avantages du mécanisme de comparaison du framework .NET intégré tel que ICOMPARER (T) et Iequality Comparer (T) pour créer une grande compatibilité avec .NET Standard et l'écosystème .NET entier. Le code source peut être facilement amené à d'autres plates-formes telles que Unity et Xamarin.

Résolution de puzzle avec algorithme

Afin d'appliquer l'algorithme au puzzle, des implémentations suivantes sont nécessaires:

1. Définition d'étape Le type qui définit l'étape du puzzle sera nécessaire pour implémenter l'interface ISTEP (TKEY). La propriété Key sert deux objectifs:

   • Pour tester si deux étapes sont équivalentes. Par exemple: même position sur le tableau.
   • Pour comparer deux étapes pour déterminer ce qui a un meilleur score. Par exemple: la distance entre la position A et l'objectif, et la distance entre la position B et l'objectif, plus la plus proche est mieux notée.

2. Les étapes de comparaison des étapes sont comparées les unes aux autres en fonction de la propriété Key pour déterminer quel meilleur score. La comparaison peut être effectuée d'une manière suivante:

   • L'implémentation icomparable (TKEY).
   • Une instance iCompparer (TKEY) personnalisée.
   • La fonction explicitement donnée H (n) où le paramètre n est la Key .

3. Les étapes disponibles à partir des informations actuelles de l'étape suivante peuvent être fournies en implémentant l'interface INextStepFactory(TKey, TStep) ou en fournissant le délégué NextStepFactory .

Après quoi, l'algorithme peut être exécuté en invoquant la méthode FindSolution avec les étapes from et goal paramètres. Si la solution existe, chacune des étapes peut être obtenue en appelant la méthode Enumerate . Les étapes peuvent être Reverse d avant le début de l'énumération.

Comparateur heuristique et comparateur heuristique discret

Le projet fournit HeuristicComparer et DiscreteHeuristicComparer pour différents scénarios de comparaison d'étapes.

• Si la propriété Key peut être directement comparée les unes aux autres sans la fonction H (n) explicite, par défaut, DiscreteHeuristicComparer sera utilisé pour une comparaison de pas plus rapide.
• Si la fonction H (n) est explicitement nécessaire afin de comparer chacune des étapes, l' HeuristicComparer sera utilisé pour effectuer l'estimation traditionnelle f (n) = g (n) + h (n) .

Préférence de la fonction heuristique

L'énumération de la production HeuristicFunctionPreference permettait aux utilisateurs de modifier l'équilibre de l'estimation F (n) = g (n) + h (n) . Lorsque deux étapes sont évaluées le même score, l'énumération décide quelle fonction, g (n) ou h (n) , sera considérée en premier. L'équilibre modifié peut affecter le comportement de l'algorithme heuristique.

Exemples

• Restauration de chemin (algorithmforce.example.pathfinding)

  L'exemple démontre le puzzle le plus courant et le plus traditionnel qui utilise des algorithmes heuristiques à résoudre.

• 8-puzzle (algorithmforce.example.eightpuzzle)

  L'exemple montre comment résoudre le 8-puzzle avec un algorithme heuristique. Les étapes initiales et d'objectifs du puzzle sont présentées ci-dessous:

• Puzzle de retournement des pièces (algorithmforce.example.coinsflipping)

  Cet exemple montre comment le jeu AI résout le puzzle de retournement des pièces. Dans le puzzle, seule une paire de pièces adjacentes peut être retournée en même temps. Les dix pièces qui sont la tête sont l'objectif. Le puzzle est inspiré par Brilliant.org.

Plus d'exemples seront ajoutés à l'avenir.

Plate-forme

Le projet cible actuellement .NET Core et .NET Framework 4.5 ou supérieur.