Skip to content

README.md

Latest commit

 

History

History
102 lines (63 loc) · 3.92 KB

README.md

File metadata and controls

102 lines (63 loc) · 3.92 KB

Metaheuristic

🧐 Problème des n-reines — Résolution par heuristiques

📌 Description

Ce projet aborde la résolution du problème des n-reines pour un échiquier de taille n × n avec n > 3, à l’aide de deux heuristiques classiques :

  1. Hill Climbing (Amélioration continue, version greedy)
  2. Recuit simulé (Simulated Annealing)

Chaque reine occupe une case différente par ligne et par colonne, donc les conflits potentiels concernent uniquement les diagonales.

⚙️ Langage et environnement

  • Langage : Python 3.10+ recommandé
  • Environnement : Jupyter Notebook ou tout interpréteur Python compatible

📦 Dépendances logicielles

Le projet repose sur les bibliothèques Python suivantes :

pip install numpy matplotlib
  • numpy : gestion des tableaux et des permutations
  • matplotlib : affichage graphique des échiquiers

🧮 Contenu

Le programme implémente deux approches :

1. 🔼 Hill Climbing (greedy)

  • Utilise des permutations aléatoires comme états initiaux.
  • Explore tous les voisins en échangeant deux colonnes.
  • Accepte uniquement un meilleur voisin à chaque itération.
  • Peut rester bloqué dans un optimum local (plateau ou colline non globale).

2. 🔥 Recuit simulé

  • Commence également par une permutation aléatoire.
  • Explore un voisin aléatoire à chaque itération.
  • Peut accepter une dégradation temporaire de la solution avec une probabilité dépendant de la "température" simulée.
  • Plus robuste face aux optima locaux grâce à cette capacité d’exploration.

📟 Rapport et ressenti

Ce travail nous a permis de mieux comprendre le rôle des heuristiques dans la recherche de solutions optimales (ou quasi-optimales) dans des espaces d’états très vastes.

  • L’implémentation du hill climbing est simple et rapide, mais peu efficace pour des tailles de plateau plus grandes (n > 10) à cause de son caractère purement avide.
  • Le recuit simulé, plus complexe, permet de sortir des optima locaux en acceptant temporairement des solutions moins bonnes, ce qui lui donne un net avantage dans les situations complexes.
  • Le choix de voisinage (permutation de deux éléments dans la permutation représentant la solution) est pertinent et conserve l’unicé ligne/colonne.

📊 Comparaison des performances

Méthode Temps / Itérations Conflits finaux Sensibilité au point de départ
Hill Climbing Rapide 1–3 (souvent non nul) Très sensible (optima locaux fréquents)
Recuit simulé Modéré 0 (souvent) Moins sensible (bonne exploration)

🔧 Influence des paramètres

  • Hill climbing :

    • Répéter l'algorithme plusieurs fois (Limite) améliore les chances de trouver une solution correcte.
    • Ne gère pas l’aléatoire une fois lancé (pas de retour en arrière possible).

  • Recuit simulé :

    • Le paramètre Tlimit (nombre d’itérations) influence fortement la qualité : une valeur trop basse mène à un échouement prématuré.
    • La probabilité d’acceptation des mauvaises solutions diminue avec le temps, simulant un refroidissement naturel.

✅ Conclusion

  • Le hill climbing est efficace sur de petits échiquiers, mais rapidement limité dès que n augmente.
  • Le recuit simulé, bien qu’un peu plus lent, est plus fiable et robuste face aux difficultés dues à la structure du problème.
  • Pour des échiquiers de taille moyenne à grande, il est préférable d’utiliser une meta-heuristique comme le recuit simulé.

📸 Exemple d’affichage

L’échiquier s’affiche à l’aide de matplotlib, avec :

  • ♛ noires : reines sans conflit
  • ♛ rouges : reines en conflit

Author

👤 HONGBO Bryan