Présentation ludique de la recherche opérationnelle pour la fête de la science 2007

DONG XiaoguangHONG Liang

OULDBABA FadelWANG Min

Tuteur : Audrey Dupont

Plan

• Présentation du projet • Organisation du travail• Les différents jeux à réaliser

• Planning prévisionnel• Conclusion

Jeu «8-Dames» Jeu « Noël » (problème couplage) Jeu « Quinze » (jeu de Nim) Jeu « Supermarché » (problème sac à dos)

Présentation

• Objectif du projet

• Intérêt du projet

• Spécifications techniques • JAVA• PHP + MySQL

• Schéma de l’interface web 

• Jeu « 8-Dames »

• Jeu « Noël » (problème couplage)

• Jeu « Quinze » (jeu de Nim)

• Jeu « Supermarché » (problème sac à dos)

Quatre jeux à réaliser

Spécifications techniques

• JAVA

• PHP + MySQL

Schéma de l’interface web

Organisation du travail

• Organisation du projet Comprendre les problèmes du projetAnalyse du projet ( les jeux, la conception

du site)

• Organisation du groupe Travail individuelTravail commun

Organisation du groupe

Groupe 2 (notre groupe)Problème Couplage Problème Sac à dosN reinesLes jeux de Nim

Groupe 1Plus court cheminVoyageur de commerceColoration de grapheSudoku

Groupe 1 et Groupe 2Définition de l’architecture technique et spécifications techniqueConception des interfaces graphiquesModélisation un base de donnéesMise en place des jeux

Jeu «8-Dames»

• Présentation du problème

• Modélisation “CSP ” du problème

• Algorithme: le Backtracking

• Difficultés de cette technique

• Résolution du CSP par recherche locale

Présentation du jeu

Modélisation CSP du jeu• Variables: X={X1,X2,X3,X4,X5,X6,X7,X8}.• Domaines : D(X1) = D(X2) = D(X3) = D(X4) = D(X5) =

D(X6) = D(X7) = D(X8) = {1, 2, 3, 4, 5, 6, 7,8}• Contraintes :• 1-les reines doivent être sur des lignes différentes:• Clig = {Xi ≠ Xj | i,j∈{1,2; 3; 4; 5; 6; 7; 8}; i≠ j}• 2-les reines doivent être sur des diagonales

montantes différentes:• Cdm = { Xi+i ≠ Xj + j | i; j ∈{1; 2; 3; 4; 5; 6; 7; 8} i ≠ j}• 3-es reines doivent être sur des diagonales

descendantes différentes:Cdd ={Xi-i ≠ Xj-j | i, j ∈ {1; 2; 3; 4; 5; 6; 7; 8} i ≠ j}

Algorithme: le Backtracking

Résolution par recherche locale algorithme Min Conflit

Jeu « Noël »

• Description du jeu

• Génération de données

• Algorithme du problème couplage

Description du jeu

Couplages dans un Graphe biparti• On suppose que le graphe G=(X,E) est biparti

c’est à dire qu’il exist une Partition des sommets en deux sous ensembles Y et Z tels que toute arête a une extrémité dans Y et l’ autre dans Z

• Le problème se ramène alors à un problème de flot sur un réseau construit à partir de G

• On ajoute deux sommets s et t on relie s à tous les sommets de Y et tous les Sommets de Z à t, on oriente les arêtes de Y vers Z, la capacité est de 1 pour tous Les arcs.

FORD-FULKERSON

• Initialisation• Démarrer du flot nul

• Étape 1• Chercher par Marquage une chaîne améliorante

• Étape 2• S'il existe une chaîne améliorante, augmenter le

flot suivant la chaîne, retour à l'étape 1.

• Étape 3 : STOP, le flot obtenu est OPTIMAL

Jeu «Quinze»

• Description du jeu

• Interface du jeu

• Algorithme

Description du jeu

• Deux joueurs doivent choisir tour à tour un nombre dans l'ensemble : 1, 2, 3, 4, 5, 6, 7, 8, 9.

• Le premier joueur qui obtient exactement le total 15, en additionnant trois de ses nombres, gagne.

Interface du jeu

AlgorithmePseudo code

A chaque tour:

Parcourir toutes les lignesSi le nombre 5 est disponible

alors l’ordinateur le prend premièrement

Si le joueur a pris 2 nombres de la même ligne

alors

l’ordinateur prend le nombre reste de la ligne

sinon

l’ordinateur prend le nombre dans la ligne où il possède les plus nombres

Si un joueur arrive à aligner ses 3 nombres alors la partie est fini

Fin

Jeu « Supermarché »

• Description du jeuProblème du sac à dos Règles du jeu

• Algorithme du problème sac à dos

• Génération des données

Algorithme approché simple

• On cherche tel que ai soit maximum tout en satisfaisant :

• Ou de manière équivalente des

entiers tels que :

,

1,2,...,I n

ii I

p P

0 1ix

1,i i

i n

x p P

1,

max i ii n

x a

Génération des données

Données Intervalle Contrainte

Poids ( )

poids(lait) poids(viande) poids(légume) poids(gâteau)

Valeur( )

Poids maximal

iP

ia

1 1

2 3

3 4

n n

i ii i

p p

1;6 5

2;12

Description du jeu

Légume

Viande

Lait

Gâteau

Chariot

Valeur €

PoidsKg

Poids maximal

Planning

Conclusion