510 lines
18 KiB
Text
510 lines
18 KiB
Text
|
STRUCTURES DES DONNEES
|
|||
|
|
----------------------
|
|||
|
|
|
|||
|
|
Un GRAPHE est repr<70>sent<6E> par soit une liste d'adjacence soit une matrice
|
|||
|
|
d'adjacence. Une matrice d'adjacence est un tableau <20> 2 dimension contenant des
|
|||
|
|
bool<EFBFBD>ens tandis qu'une liste d'adjacence est un tableau de hash dont chacun
|
|||
|
|
contenant comme cl<63>s les sommets atteints.
|
|||
|
|
|
|||
|
|
Un CHOCOBAR est repr<70>sent<6E> par plusieurs fa<66>ons diff<66>rentes afin de pouvoir
|
|||
|
|
comparer les m<>thodes plus efficaces d'une impl<70>mentation aux autres.
|
|||
|
|
a/ Par une liste des "points de ruptures".
|
|||
|
|
b/ Par un tableau d'entiers de 8 bits.
|
|||
|
|
c/ Par un entier de 64-bit.
|
|||
|
|
|
|||
|
|
Une STRATEGIE est un tableau d'entiers, un entier x index<65> <20> la position i du
|
|||
|
|
tableau signifie que si le joueur concern<72> se trouve <20> la configuration i alors
|
|||
|
|
il doit choisir la configuration x comme son coup.
|
|||
|
|
|
|||
|
|
Une STRATEGIE GAGNANTE est une strat<61>gie d'un joueur qui effectue le PREMIER
|
|||
|
|
coup et celle-ci garantit que quel que soit les <20>tats choisis par l'adversaire
|
|||
|
|
alors l'adversaire perdra.
|
|||
|
|
|
|||
|
|
REMARQUE SUR LES DIFFERENTES IMPLEMENTATIONS DE CHOCHOBAR
|
|||
|
|
---------------------------------------------------------
|
|||
|
|
|
|||
|
|
Il est <20>vident que ces trois diff<66>rentes impl<70>mentations ne distinguent que la
|
|||
|
|
mani<EFBFBD>re de g<>n<EFBFBD>rer le graphe de jeu : vitesse de construction du graphe et
|
|||
|
|
espace occup<75> pour cette g<>n<EFBFBD>ration.
|
|||
|
|
|
|||
|
|
a/ Un POINT DE RUPTURE est une paire d'entiers repr<70>sentant un point <20> partir du
|
|||
|
|
duquel tous les carr<72>s <20> droite et en bas de ceci sont d<>j<EFBFBD> mang<6E>s. Un <20>tat de
|
|||
|
|
jeu peut en effet contenir plusieurs point de ruptures.
|
|||
|
|
|
|||
|
|
L'espace occup<75> par un <20>tat de jeu est alors au pire = taille 2 entiers X nombre
|
|||
|
|
de colonnes de la barre de chocolat car une barre de chocolat ne peut pas avoir
|
|||
|
|
plus que (nombre de colonnes) point de ruptures.
|
|||
|
|
|
|||
|
|
Cette impl<70>mentation est r<>alis<69>e par Glenn ROLLAND.
|
|||
|
|
|
|||
|
|
b/ Un TABLEAU DE CHAR. Un <20>tat de jeu est alors repr<70>sent<6E> par une liste
|
|||
|
|
d'entiers marquant les carr<72>s mang<6E>s de chaque colonne de la barre de chocolat.
|
|||
|
|
Afin d'avoir un entier de 8 bits on utiliser le type char de Java.
|
|||
|
|
|
|||
|
|
Ceci dit, l'espace occup<75> par un <20>tat de jeu = nombre de colonnes de la barre de
|
|||
|
|
chocolat X taille d'un entier.
|
|||
|
|
|
|||
|
|
Cette approche est r<>alis<69>e par INDRAWATI.
|
|||
|
|
|
|||
|
|
c/ Un ENTIER DE 64-BIT. De m<>me principe qu'en (b) on stocke toujours le nombre
|
|||
|
|
de carr<72>s mang<6E>s de chaque colonne mais au lieu d'utiliser un tableau alors on
|
|||
|
|
utilise un entier de 64 bits pour "cartographier" ces colonnes.
|
|||
|
|
|
|||
|
|
Cette approche est r<>alis<69>e par INDRAWATI.
|
|||
|
|
|
|||
|
|
Dans ce cas, un <20>tat de jeu prend un espace de taille un entier de 64 bits.
|
|||
|
|
|
|||
|
|
Cette derni<6E>re impl<70>mentation a rendu possible la g<>n<EFBFBD>ration de configuration de
|
|||
|
|
jeu de taille assez grande puisque l'on a aucun espace perdu pour cr<63>er les
|
|||
|
|
<EFBFBD>tats : pour une barre de taille (mxn) alors un "cartographie" un <20>tat par un
|
|||
|
|
tableau de n entiers en base(m+1). Ceci dit, la taille maximale de barre de
|
|||
|
|
chocolat que l'on peut calculer est de (mxn) telle que (m+1)^n <= 2^64.
|
|||
|
|
|
|||
|
|
On estime que cette taille est suffisante puisque lors des tests on a trouv<75> que
|
|||
|
|
de toute fa<66>on sans d<>passer cette limitation on n'a pas assez d'espace de
|
|||
|
|
m<EFBFBD>moire pour stocker notre graphe (avec liste d'adjacence ni matrice
|
|||
|
|
d'adjacence), on ne risque donc en aucun cas d'<27>tre bloqu<71> <20> cause de la
|
|||
|
|
structure de donn<6E>es de ChocoBar.
|
|||
|
|
|
|||
|
|
GENERATION DE GRAPHE
|
|||
|
|
--------------------
|
|||
|
|
|
|||
|
|
Afin d'<27>conomiser l'espace de m<>moire utilis<69> au cours du d<>roulement de
|
|||
|
|
programme, on supprime la liste des <20>tats une fois que le graphe du jeu aura <20>t<EFBFBD>
|
|||
|
|
g<EFBFBD>n<EFBFBD>r<EFBFBD>.
|
|||
|
|
|
|||
|
|
a/ Avec une liste de POINTS DE RUPTURES
|
|||
|
|
|
|||
|
|
L'algorithme a <20>t<EFBFBD> impl<70>ment<6E> par Glenn ROLLAND.
|
|||
|
|
|
|||
|
|
Il s'agit d'un algorithme r<>cursif dans lequel on g<>n<EFBFBD>re en une seule passe les
|
|||
|
|
<EFBFBD>tats et le graphe. On commence par une ChocoBar vide, et on "mange"
|
|||
|
|
r<EFBFBD>cursivement les points inf<6E>rieurs droits jusqu'<27> atteindre le sommet
|
|||
|
|
sup<EFBFBD>rieur gauche.
|
|||
|
|
|
|||
|
|
On d<>finit dans la suite de cette section le type ChocoBar comme une liste de
|
|||
|
|
couples d'entiers. On consid<69>rera de plus que les variables E et V sont
|
|||
|
|
globales.
|
|||
|
|
|
|||
|
|
D'autre part, dans le pseudo-code suivant, le chocobar et son index seront
|
|||
|
|
confondus, mais dans notre impl<70>mentation, le temps de calcul de l'index d'un
|
|||
|
|
chocobar donn<6E> est en O(min(m,n)). La r<>cup<75>ration du chocobar correpondant <20>
|
|||
|
|
un index se fait en temps constant. Chaque ajout d'<27>l<EFBFBD>ment <20> l'ensemble V du
|
|||
|
|
graphe n<>cessite le calcul de l'index du chocobar. De m<>me, chaque
|
|||
|
|
v<EFBFBD>rification d'existance d'un <20>l<EFBFBD>ment dans V n<>cessite ce calcul.
|
|||
|
|
|
|||
|
|
Cette impl<70>mentation n<>cessite de maintenir aussi bien une liste des sommets
|
|||
|
|
incidents que des sommets adjactents <20> un sommet donn<6E> pour avoir une
|
|||
|
|
complexit<EFBFBD> en temps petite.
|
|||
|
|
|
|||
|
|
|
|||
|
|
Pour commencer, voici quelques fonctions simples dont le d<>tail ne sera pas donn<6E>:
|
|||
|
|
|
|||
|
|
chocobar.addBreakPoint(m,n)
|
|||
|
|
// fonction qui ajoute le breakpoint (m,n) <20> la liste des points (tri<72>s) du
|
|||
|
|
// chocobar en un temps O(min(m,n)), soit O(n)
|
|||
|
|
|
|||
|
|
chocobar.getBreakLine()
|
|||
|
|
// fonction qui renvoie la ligne frontiere entre la partie mang<6E>e et la
|
|||
|
|
// partie non-mang<6E>e de la tablette de chocolat. Les points de la liste
|
|||
|
|
// sont des carr<72>s non-mang<6E>s et incluent les bordures inf<6E>rieure et droite
|
|||
|
|
// de la tablette lorsque celle-ci est pleine. Elle se calcule
|
|||
|
|
// en O(m+n), ce qui est <20>quivalent <20> O(n)
|
|||
|
|
|
|||
|
|
chocobar.equals(c)
|
|||
|
|
// fonction qui compare les deux listes de points de chocobar et c
|
|||
|
|
// Sa temps de calcul est min(m,n), soit une complexit<69> de O(n)
|
|||
|
|
|
|||
|
|
Et ensuite les fonctions permettant la g<>n<EFBFBD>ration du graphe et des <20>tats:
|
|||
|
|
|
|||
|
|
global (V,E) <- (vide,vide)
|
|||
|
|
global etatInitial <- vide
|
|||
|
|
global etatFinal <- vide
|
|||
|
|
|
|||
|
|
//fonction d'initialisation de la g<>n<EFBFBD>ration du graphe
|
|||
|
|
debut genChoco(m: entier, n:entier)
|
|||
|
|
etatInitial <- ChocoBar(m, n)
|
|||
|
|
V <- etatInitial
|
|||
|
|
genChocoFromPoint(etatInitial,m-1,n-1)
|
|||
|
|
renvoyer configGraph
|
|||
|
|
fin genChoco
|
|||
|
|
|
|||
|
|
Comme on le constate, genChoco ne fait que l'initialisation du graphe
|
|||
|
|
avec l'<27>tat initial et aucun arc, suivi d'un appel <20> la fonction
|
|||
|
|
r<EFBFBD>cursive genChocoFromPoint.
|
|||
|
|
La complexit<69> de genChoco est donc <20>gale <20> celle de O(genChocoFromPoint)
|
|||
|
|
plus une constante.
|
|||
|
|
|
|||
|
|
|
|||
|
|
//fonction qui construit une configuration de jeu <20> partir d'un <20>tat donn<6E>
|
|||
|
|
//en mangeant le carr<72> de coordonn<6E>es (m, n)
|
|||
|
|
debut genChocoFromPoint(oldCBar: ChocoBar, m: entier, n: entier)
|
|||
|
|
currentCBar <- oldCBar
|
|||
|
|
currentCBar.addBreakPoint(m, n) //on mange le carr<72> (m, n)
|
|||
|
|
si currentCBar = Exception "d<>ja mang<6E>" alors
|
|||
|
|
sortir
|
|||
|
|
fin si
|
|||
|
|
si currentCBar = Exception "invalide" alors
|
|||
|
|
sortir
|
|||
|
|
fin si
|
|||
|
|
si V inclus currentCBar alors
|
|||
|
|
E <- E U {(oldCBar,currentCBar)}
|
|||
|
|
retourner
|
|||
|
|
sinon
|
|||
|
|
V <- V U {currentCBar}
|
|||
|
|
si isFinalConfig(currentCBar) alors
|
|||
|
|
etatFinal <- currentCBar
|
|||
|
|
fin si
|
|||
|
|
constructArcsFromAncestorsTo(oldCBar,currentCBar) ***** expliquer *****
|
|||
|
|
frontline <- chocobar.getBreakLine()
|
|||
|
|
pour chaque p=(x,y) dans frontline, faire
|
|||
|
|
genChocoFromPoint(currentCBar,x,y)
|
|||
|
|
fin pour
|
|||
|
|
fin si
|
|||
|
|
fin genChocoFromPoint
|
|||
|
|
|
|||
|
|
Cette fonction va s'appeller r<>cursivement |V| fois (pour chaque
|
|||
|
|
chocobar possible) au total. Chaque appel de la fonction co<63>te
|
|||
|
|
O(addBreakpoint)+ O(V inclus currentCBar) + O(isFinalConfig) +
|
|||
|
|
O(constructArcsFromAncestorsTo) + O(breakline).
|
|||
|
|
Or isFinalConfig est une fonction qui teste en temps constant
|
|||
|
|
si la configuration est la chocobar <20> 1 <20>l<EFBFBD>ment dans le coin
|
|||
|
|
sup<EFBFBD>rieur gauche.
|
|||
|
|
|
|||
|
|
|
|||
|
|
// fonction qui dit si sonCB est une configuration accessible <20>
|
|||
|
|
// partir de fatherCB
|
|||
|
|
debut isNextOf(fatherCB,sonCB) : booleen
|
|||
|
|
pour chaque p=(i,j) appartenant <20> la liste de breakpoint de sonCB
|
|||
|
|
fatherCopy <- fatherCB
|
|||
|
|
fatherCopy.addBreakPoint(i,j)
|
|||
|
|
si fatherCopy = father alors
|
|||
|
|
retourner vrai
|
|||
|
|
sinon
|
|||
|
|
retourner faux
|
|||
|
|
fin si
|
|||
|
|
fin isNextOf
|
|||
|
|
|
|||
|
|
La v<>rification de l'accessibilit<69> d'un <20>tat <20> partir d'un autre
|
|||
|
|
n<EFBFBD>cessite |sonCB| ajouts de breakpoints suivi de comparaisons de listes.
|
|||
|
|
Or |sonCB| = min(m,n), O(addBreakPoint)=O(n) et O(equals)=O(n).
|
|||
|
|
On a donc O(isNextOf) = O(n^3)
|
|||
|
|
|
|||
|
|
|
|||
|
|
// fonction qui remplit le graphe <20> partir d'une configuration vers
|
|||
|
|
// tous ses ancetres possibles...
|
|||
|
|
debut constructArcsFromAncestorsTo(fatherCB: ChocoBar, sonCB:ChocoBar)
|
|||
|
|
si isNextOf(fatherCB,sonCB) alors
|
|||
|
|
E <- E U {(fatherCB,sonCB)}
|
|||
|
|
pour tout ancetreCB appartenant <20> incident fatherCB dans V,
|
|||
|
|
faire
|
|||
|
|
constructArcsFromAncestorsTo(ancetreCB,sonCB)
|
|||
|
|
fin pour
|
|||
|
|
sinon
|
|||
|
|
retourner
|
|||
|
|
fin si
|
|||
|
|
fin constructArcsFromAncestorsTo
|
|||
|
|
|
|||
|
|
La somme du nombre d'ancetreCB trouv<75>s sur tous les appels de
|
|||
|
|
constructArcsFromAncestorsTo est |V|, et pour chacun d'eux on appelle
|
|||
|
|
isNextOf. La complexit<69> d'un appel (r<>cursif) <20> cette fonction
|
|||
|
|
est donc de |V|*O(isNextOf), soit O( |V| * n^3 ).
|
|||
|
|
|
|||
|
|
|
|||
|
|
La complexit<69> totale de la construction du graphe et des <20>tats est donc <20>gale <20>
|
|||
|
|
O(genChocoFromPoint)
|
|||
|
|
= |V| * ( O(addBreakpoint)+ O(V inclus currentCBar) +
|
|||
|
|
O(isFinalConfig) + O(constructArcsFromAncestorsTo) + O(breakline) )
|
|||
|
|
= O( |V| * ( n + |V|*n^3 + n))
|
|||
|
|
= O( (n^3) * (|V|^2) + (|V|*n) )
|
|||
|
|
|
|||
|
|
|
|||
|
|
b/ Avec un tableau de ENTIER de 8BIT
|
|||
|
|
|
|||
|
|
L'algorithme a <20>t<EFBFBD> impl<70>ment<6E> par INDRAWATI.
|
|||
|
|
|
|||
|
|
On g<>n<EFBFBD>re d'abord toutes les configurations possibles du jeu de ChocoBar de
|
|||
|
|
taille (m x n) avec m le nombre de lignes et n lenombre de colonnes : c'est
|
|||
|
|
une g<>n<EFBFBD>ration d'une suite d'entiers de longueur n en ordre lexicographique
|
|||
|
|
particulier.
|
|||
|
|
|
|||
|
|
genChoco(m: entier, n: entier)
|
|||
|
|
V <- genEtat(m, n)
|
|||
|
|
E <- vide
|
|||
|
|
pour i de 0 <20> longeur(V) faire
|
|||
|
|
pour j de i+1 <20> longeur(V) faire
|
|||
|
|
si estFils(V[j], V[i]) alors
|
|||
|
|
E <- E U {(i, j)}
|
|||
|
|
fin si
|
|||
|
|
fin pour
|
|||
|
|
fin pour
|
|||
|
|
renvoyer (V, E) //c'est notre graphe
|
|||
|
|
|
|||
|
|
genEtat(m: entier, n: entier)
|
|||
|
|
pour i de 0 <20> (n-1) faire
|
|||
|
|
init[i] <- 0
|
|||
|
|
final[i] <- m
|
|||
|
|
fin pour
|
|||
|
|
etatCourant <- init
|
|||
|
|
tabEtat[0] <- init
|
|||
|
|
i <- 1
|
|||
|
|
etatFinal <- final
|
|||
|
|
tant que etatCourant != etatFinal faire
|
|||
|
|
pour j de 0 <20> (n-1) faire
|
|||
|
|
gen[j] <- etatCourant[j]
|
|||
|
|
fin pour
|
|||
|
|
gen[n-1] <- gen[n-1] + 1
|
|||
|
|
si gen[n-1] > m alors
|
|||
|
|
retenue <- vrai
|
|||
|
|
fin si
|
|||
|
|
j <- (n-1)
|
|||
|
|
tant que (gen[j] > m) faire
|
|||
|
|
si j=0 alors
|
|||
|
|
arreter tant que
|
|||
|
|
fin si
|
|||
|
|
gen[j-1] <- gen[j-1] + 1
|
|||
|
|
j <- (j - 1)
|
|||
|
|
fin tant que
|
|||
|
|
si retenue est vrai alors
|
|||
|
|
pour cpt de j <20> (n-1) faire
|
|||
|
|
gen[cpt] <- gen[j]
|
|||
|
|
fin pour
|
|||
|
|
fin si
|
|||
|
|
etatCourant <- gen
|
|||
|
|
tabEtat[i] <- gen
|
|||
|
|
i <- i+1
|
|||
|
|
fin tant que
|
|||
|
|
tabEtat[i] <- etatFinal
|
|||
|
|
renvoyer tabEtat
|
|||
|
|
|
|||
|
|
estFils(fils: tableau d'entiers, pere: tableau d'entiers)
|
|||
|
|
eaten <- -1
|
|||
|
|
pour i de 0 <20> longeur(fils) faire
|
|||
|
|
si fils[i] < pere[i] alors
|
|||
|
|
renvoyer faux
|
|||
|
|
fin si
|
|||
|
|
si eaten = -1 alors
|
|||
|
|
si fils[i] = pere[i] alors
|
|||
|
|
continuer
|
|||
|
|
sinon
|
|||
|
|
eaten <- i
|
|||
|
|
fin si
|
|||
|
|
sinon si pere[i] != fils[i] et fils[i] != eaten alors
|
|||
|
|
renvoyer faux
|
|||
|
|
fin si
|
|||
|
|
fin pour
|
|||
|
|
si eaten != -1 alors
|
|||
|
|
renvoyer vrai // fils est bien un etat suivant du pere
|
|||
|
|
sinon
|
|||
|
|
renvoyer faux // pere identique au fils
|
|||
|
|
fin si
|
|||
|
|
|
|||
|
|
Soit la taille de la barre de chocolat du jeu est de m lignes et n colonnes
|
|||
|
|
et on souhaite g<>n<EFBFBD>rer tous les <20>tats possibles dont chacun nous co<63>te O(n) en
|
|||
|
|
temps. Ceci fera un total de O(n*|V|). De m<>me pour la complexit<69> en espace
|
|||
|
|
puisqu'un <20>tat est d<>crit par n entiers.
|
|||
|
|
|
|||
|
|
Pour v<>rifier si un <20>tat peut <20>tre atteint <20> partir d'un autre <20>tat donn<6E> alors
|
|||
|
|
on doit comparer les 2n entiers d<>crivant ces deux <20>tats. Une comparaison co<63>te
|
|||
|
|
donc O(n).
|
|||
|
|
|
|||
|
|
Etant donn<6E> que les <20>tats sont g<>n<EFBFBD>r<EFBFBD>s en ordre lexicographique alors on est s<>r
|
|||
|
|
que les candidats des <20>tats adjacents <20> un <20>tat index<65> par i sont ceux index<65>
|
|||
|
|
par des entiers sup<75>rieur i. Le nombre de v<>rifications qu'il faut effectuer
|
|||
|
|
sont alors = somme des entiers de 1 <20> |V| = 1/2
|
|||
|
|
* |V| * (|V|+1). Chacune de ces v<>rifications co<63>te O(n), la construction des
|
|||
|
|
ar<EFBFBD>tes co<63>te en total O(n*(|V|^2)).
|
|||
|
|
|
|||
|
|
Tout cela conduit <20> un co<63>t total en temps de g<>n<EFBFBD>ration de graphe en
|
|||
|
|
O(n*(|V|^2))+O(n*|V|).
|
|||
|
|
|
|||
|
|
ATTENTION: A la fin de g<>n<EFBFBD>ration de graphe on supprime la liste des
|
|||
|
|
configurations, il nous reste que l'espace occup<75> par la matrice d'adjacence ou
|
|||
|
|
la liste d'adjacence du graphe.
|
|||
|
|
|
|||
|
|
c/ Avec un ENTIER de 64BIT
|
|||
|
|
|
|||
|
|
C'est le m<>me algo que pour le b/.
|
|||
|
|
|
|||
|
|
PARTIE DE JEU
|
|||
|
|
-------------
|
|||
|
|
|
|||
|
|
Cet algorithme a <20>t<EFBFBD> concu par INDRAWATI.
|
|||
|
|
|
|||
|
|
// C'est une fonction de simulation qui affiche le d<>roulement de jeu
|
|||
|
|
// selon strat<61>gie des deux joueurs
|
|||
|
|
simulation(G: graphe, SA: strategie de A, SB: strategie de B)
|
|||
|
|
courant <- etat initial de G
|
|||
|
|
final <- etat final de G
|
|||
|
|
tant que courant != final faire
|
|||
|
|
coupA <- SA[courant]
|
|||
|
|
afficher "A a boug<75> vers coupA"
|
|||
|
|
si coupA == final alors
|
|||
|
|
afficher "A a perdu"
|
|||
|
|
quitter
|
|||
|
|
fin si
|
|||
|
|
courant <- SB[coupA]
|
|||
|
|
afficher "B a boug<75> vers courant"
|
|||
|
|
fin tant que
|
|||
|
|
afficher "B a perdu"
|
|||
|
|
|
|||
|
|
En terme de complexit<69>, ici on consid<69>re plut<75>t en temps puisque l'espace
|
|||
|
|
utilis<EFBFBD> est statique : par d<>finition de STRATEGIE il est <20>gal au nombre des
|
|||
|
|
sommets du graphe, donc O(|V|).
|
|||
|
|
|
|||
|
|
En ce qui concerne de temps, au pire des cas on parcourt le chemin de longueur
|
|||
|
|
maximale de l'<27>tat intial vers l'<27>tat final. Ce chemin d<>pendra, <20> son tour, du
|
|||
|
|
graphe de jeu (peut-<2D>tre donn<6E> par l'utilisateur, ce n'est donc pas
|
|||
|
|
d<EFBFBD>terministe), tout ce que l'on sait c'est que ce chemin < |V|.
|
|||
|
|
|
|||
|
|
TEST DE STRATEGIE
|
|||
|
|
-----------------
|
|||
|
|
|
|||
|
|
Cet algorithme a <20>t<EFBFBD> <20>crit par INDRAWATI.
|
|||
|
|
|
|||
|
|
// C'est une fonction qui teste si S est une strat<61>gie gagnante ou non
|
|||
|
|
isWinningStrategy(G: graphe, S: strategie)
|
|||
|
|
courant <- etat initial de G
|
|||
|
|
final <- etat final de G
|
|||
|
|
etatsATraiter <- {courant}
|
|||
|
|
etatsTraites <- vide
|
|||
|
|
tant que etatsATraiter != vide faire
|
|||
|
|
etat <- enfiler etatsATraiter
|
|||
|
|
si etat == final alors
|
|||
|
|
continuer
|
|||
|
|
fin si
|
|||
|
|
etatsTraites <- etatsTraites U {etat}
|
|||
|
|
coup <- S[etat]
|
|||
|
|
si coup == final
|
|||
|
|
renvoyer faux
|
|||
|
|
fin si
|
|||
|
|
advers <- les sommets adjacents <20> coup
|
|||
|
|
pour les sommets i contenus dans advers faire
|
|||
|
|
si i n'est pas contenu dans etatsTraites alors
|
|||
|
|
etatsATraiter <- etatsATraiter U {i}
|
|||
|
|
fin si
|
|||
|
|
fin pour
|
|||
|
|
fin tant que
|
|||
|
|
renvoyer vraie
|
|||
|
|
|
|||
|
|
En espace on sait qu'<27> tout moment un sommet est contenu soit dans l'ensemble
|
|||
|
|
etatsATraiter soit dans l'ensemble etatsTraites, l'espace occup<75> est alors egal
|
|||
|
|
au nombre des sommets du graphe. L'espace occup<75> est alors O(|E|).
|
|||
|
|
|
|||
|
|
En temps, on sait que l'on visite tous les coups possibles de l'adversaire et on
|
|||
|
|
ne visite qu'un coup quand c'est notre tour. Ceci dit, on ne visite qu'une
|
|||
|
|
partie des sommets du graphe. La complexit<69> est alors inf<6E>rieure <20> O(|V|).
|
|||
|
|
|
|||
|
|
REMARQUE : x->y
|
|||
|
|
x->z
|
|||
|
|
x->t
|
|||
|
|
On ne peut pr<70>dire combien d'arr<72>tes que l'on a <20> chaque sommet puisque le
|
|||
|
|
graphe peut <20>tre donn<6E> par l'utilisateur et le sommet choisi est <20>galement
|
|||
|
|
d<>cid<69> par l'utilisateur.
|
|||
|
|
|
|||
|
|
CONSTRUCTION DE STRATEGIE GAGNANTE
|
|||
|
|
----------------------------------
|
|||
|
|
|
|||
|
|
Cet algorithme a <20>t<EFBFBD> <20>crit par INDRAWATI.
|
|||
|
|
|
|||
|
|
L'approche choisie est de trouver le chemin gagnant le PLUS COURT partant de
|
|||
|
|
l'<27>tat initial vers l'<27>tat final. Ceci dit que la strat<61>gie ne peut pas <20>tre
|
|||
|
|
appliqu<EFBFBD>e <20> une simulation si le joueur qui lui est associ<63>e ne fait pas le
|
|||
|
|
PREMIER coup.
|
|||
|
|
|
|||
|
|
// C'est une fonction qui renvoie un tableau d'entiers (une strat<61>gie gagnante)
|
|||
|
|
constructWinningStrategy(G: graphe)
|
|||
|
|
final <- etat final de G
|
|||
|
|
start <- etat initial de G
|
|||
|
|
sommetsATraiter <- vide
|
|||
|
|
pour i de 1 au ((nombre de sommets de G) - 1) faire
|
|||
|
|
S[i]=0
|
|||
|
|
sommetsATraiter <- sommetsATraiter U {sommet i}
|
|||
|
|
fin pour
|
|||
|
|
etatsGagnants <- {final}
|
|||
|
|
etatsPerdants <- vide
|
|||
|
|
tant que (S[start]==0) faire
|
|||
|
|
sommet <- tete de sommetsATraiter
|
|||
|
|
test_perdant <- withOnlyEdges(sommet, etatsGagnants, g)
|
|||
|
|
si test_perdant != -1 alors
|
|||
|
|
enfiler sommet de sommetsATraiter
|
|||
|
|
etatsPerdants <- etatsPerdants U {sommet}
|
|||
|
|
S[sommet] <- test_perdant
|
|||
|
|
nuvo <- les sommets ayant un arc vers le sommet sommet
|
|||
|
|
pour tout sommet i dans nuvo
|
|||
|
|
etatsGagnants <- etatsGagnants U {i}
|
|||
|
|
S[i] <- sommet
|
|||
|
|
fin pour
|
|||
|
|
pour tout sommet i dans sommetsATraiter faire
|
|||
|
|
si i est contenu dans nuvo
|
|||
|
|
enlever i de sommetsATraiter
|
|||
|
|
fin si
|
|||
|
|
fin pour
|
|||
|
|
fin si
|
|||
|
|
fin tant que
|
|||
|
|
renvoyer S
|
|||
|
|
|
|||
|
|
// C'est une fonction qui renvoie -1 si sommet src a au moins un sommet adjacent
|
|||
|
|
// qui n'est pas contenu dans dest
|
|||
|
|
withOnlyEdges(src: entier, dest: liste d'entiers, G: graphe)
|
|||
|
|
//si graphe est repr<70>sent<6E> par une matrice alors il faut parcourir
|
|||
|
|
//toute la ligne de src
|
|||
|
|
//si c'est une liste d'adjacence suffit de prendre la liste index<65>e par src
|
|||
|
|
adjacents <- {sommets adjacents <20> src}
|
|||
|
|
ret <- -1
|
|||
|
|
pour tout sommet i contenu dans adjacents faire
|
|||
|
|
si i n'est pas contenu dans dest alors
|
|||
|
|
renvoyer -1
|
|||
|
|
sinon si ret == -1 alors
|
|||
|
|
ret <- i
|
|||
|
|
fin si
|
|||
|
|
fin pour
|
|||
|
|
renvoyer ret
|
|||
|
|
|
|||
|
|
Par hypoth<74>se du jeu de ChocoBar, on sait que le joueur qui commence est le
|
|||
|
|
gagnant et que l'on peut lui trouver une strat<61>gie gagnante. Ceci veut dire que
|
|||
|
|
l'on arrivera <20> d<>cider une suite des coups <20> partir de l'<27>tat initial vers
|
|||
|
|
l'<27>tat final en gagnant le jeu.
|
|||
|
|
|
|||
|
|
ATTENTION: Cet algo ne marche donc pas pour les graphes qui ne respectent pas
|
|||
|
|
les r<>gles de ChocoBar.
|
|||
|
|
|
|||
|
|
On d<>finit alors ETAT GAGNANT comme <20>tant un <20>tat qui peut m<>ner <20> un <20>tat
|
|||
|
|
perdant. En effet, si un joueur se trouve dans cet <20>tat alors il peut choisir
|
|||
|
|
son coup et logiquement il va choisir un <20>tat perdant pour le passer <20> son
|
|||
|
|
adversaire.
|
|||
|
|
|
|||
|
|
Un ETAT PERDANT, par contre, est l'<27>tat qui ne peut que mener aux <20>tats
|
|||
|
|
gagnants. C'est l'<27>tat dans lequel on souhaite placer l'adversaire afin de
|
|||
|
|
bloquer ses choix.
|
|||
|
|
|
|||
|
|
Donc, partant de l'<27>tat final de jeu, on sait que celui qui trouve cet <20>tat
|
|||
|
|
avant de d<>cider de jouer est le gagnant, l'<27>tat final est donc un sommet
|
|||
|
|
gagnant. A chaque it<69>ration on essaie de trouver un ou plusieurs <20>tats perdants.
|
|||
|
|
Au pire des cas on ne trouve qu'un <20>tat perdant que l'on enl<6E>vera de l'ensemble
|
|||
|
|
des <20>tats <20> traiter. On en enl<6E>vera <20>galement les <20>tats gagnants obtenus <20>
|
|||
|
|
partir de cet <20>tat perdant. Ce "backtracking" est effectu<74> jusqu'au d<>but du
|
|||
|
|
graphe (<28>tat initial).
|
|||
|
|
|
|||
|
|
Na<EFBFBD>vement on peut dire que l'on a, <20> chaque <20>tape d'it<69>ration, au moins un <20>tat
|
|||
|
|
perdant et un <20>tat gagnant (car cet <20>tat perdant provient surement d'un autre
|
|||
|
|
coup) et d'un coup on enl<6E>ve ces deux <20>tats (au pire) de l'ensemble restant <20>
|
|||
|
|
traiter et on doit faire donc 1/2 * (|V|) it<69>rations dans le pire des cas. A
|
|||
|
|
chaque it<69>ration on visite tous les <20>tats non trait<69>s jusqu'<27> ce que l'on trouve
|
|||
|
|
un <20>tat perdant. Ceci dit qu'au maximal on effectue O(|V|^2 + |V|) visites.
|
|||
|
|
|
|||
|
|
Or, en r<>alit<69> on s'arr<72>te beaucoup plus t<>t car d<>s que l'on puisse d<>cider
|
|||
|
|
quel coup <20> choisir <20> partir de l'<27>tat intial alors on s'arr<72>te car on a d<>j<EFBFBD>
|
|||
|
|
trouv<EFBFBD> le chemin gagnant le plus court partant du d<>but de jeu. Ce chemin se
|
|||
|
|
composera uniquement par un ensemble d'arr<72>tes de la forme (etat_gagnant -> etat
|
|||
|
|
perdant).
|
|||
|
|
|
|||
|
|
Il existe des <20>tats non trait<69>s <20> la sortie de cet algo. Ce sont des <20>tats par
|
|||
|
|
lesquels on ne passera jamais car quand on a plusieurs choix (tous perdants)
|
|||
|
|
<EFBFBD> partir d'un sommet gagnant alors on doit quand m<>me en choisir qu'un seul
|
|||
|
|
(par d<>finition de STRATEGIE).
|
|||
|
|
|
|||
|
|
En terme de l'espace occup<75> on en a besoin de O(|V|) : |V| pour stocker la
|
|||
|
|
strat<EFBFBD>gie sous forme d'un tableau et |V| pour stocker les <20>tats non-trait<69>s +
|
|||
|
|
les <20>tats trait<69>s (<28>tats perdants + <20>tats gagnants = tous les etats).
|