Skip to content

Latest commit

 

History

History
39 lines (33 loc) · 1.65 KB

README.md

File metadata and controls

39 lines (33 loc) · 1.65 KB

puzzleOfDoom

Etude du problème:

  • Un puzzle est composé de 256 pièces.

  • Chaque pièce est composée de 4 faces

  • Chaque pièce peut être disposée sur le plateau suivant un axe x ou y

  • Chaque pièce peut être tournée

  • Différentes méthodes de résolution du puzzle ont déjà été exploités :

    • Equerre => Triangle => Carré
    • Bordure => intérieur
  • Différents algorithmes :

    • tabu search
    • backtrack

Etude des possibilités

  • Différentes îles:
    • Une par mutation:
      • rotation mutation => un gène tourné
      • swap mutation => échange deux gènes
      • swap & rotate => échange deux gènes et les tournes
      • rotate region mutation => prend une région >= 4 gènes et la tourne
      • swap region mutation => échange deux régions
      • region inversion mutation => inverse la position des gènes dans une région
      • row and column inversion mutation => swap deux gènes cote à cote
      • scramble mutation => garde un coin du plateau et mélange le reste
    • Une par croisement:
      • region exchange crossover => clone les deux parents et échange deux régions
      • uniform crossover => même chose que region exchange, sauf qu'on crée un template de régions 1 et 2 et on attribut les gènes correspondants au parent 1 ou 2 en fonction du template
      • rotation crossover => même chose que region exchange avec de la rotation
    • Une par choix de départ (0, 1 ou 5 indices)

Faire tourner chaque algo-genetic en solo pour calculer la fiabilité de chaque algo

Notation du projet

  • La cotation du projet se fait sur le nombre de bords de pièces qui matchent.
  • Le score maximal à atteindre pour la soutenance est 480
  • Le score maximal trouvé est de 467