Génération et résolution de labyrinthes - Historique des versions

C.robert : /* Sortir d'un labyrinthe à l'aide du parcours en profondeur */

2017-07-06T03:16:22Z

Sortir d'un labyrinthe à l'aide du parcours en profondeur

← Version précédente		Version du 6 juillet 2017 à 03:16
Ligne 222 :		Ligne 222 :
	Voici un exemple pour expliquer la méthode :		Voici un exemple pour expliquer la méthode :

	[[Fichier:sortie.jpg]]		[[Fichier:sortie.jpg\|400px\|]]

	Dans un premier temps, on oriente les arêtes. Un sommet ne peut avoir qu'un seul père. Le tableau joint au graphe donne pour chaque sommet son père (1 est son propre père). Ce sommet 1 correspond à l'entrée du labyrinthe, et 7 à sa sortie. Nous cherchons donc à déterminer le chemin menant de 1 à 7. Pour cela, on regarde dans le tableau le père de 7; il s'agit de 4. Le père de 4 est 2, et celui de 2 est 1. La solution du labyrinthe est donc : 1 > 2 > 4 > 7.		Dans un premier temps, on oriente les arêtes. Un sommet ne peut avoir qu'un seul père. Le tableau joint au graphe donne pour chaque sommet son père (1 est son propre père). Ce sommet 1 correspond à l'entrée du labyrinthe, et 7 à sa sortie. Nous cherchons donc à déterminer le chemin menant de 1 à 7. Pour cela, on regarde dans le tableau le père de 7; il s'agit de 4. Le père de 4 est 2, et celui de 2 est 1. La solution du labyrinthe est donc : 1 > 2 > 4 > 7.

C.robert : /* Sortie d'un labyrinthe */

2017-07-06T03:13:56Z

Sortie d'un labyrinthe

@@ Ligne 217 : / Ligne 217 : @@
 Il est assez connu qu'en longeant les murs d'un labyrinthes, on parvient à en sortir. Il faut pour cela que ce labyrinthe soit parfait.
 On peut parcourir le labyrinthe avec l'algorithme de parcours en profondeur vu précédemment. Cela revient à avancer tant qu'on le peut, et à retourner en arrière lorsqu'on est dans une impasse. Cette méthode n'est pas la plus courte. Le chemin le plus court peut être déterminé avec une file de priorité, par exemple avec l'algorithme de parcours en largeur.
 ----
 ==Sources==
 <ul>

C.robert le 6 juillet 2017 à 02:13

2017-07-06T02:13:27Z

← Version précédente		Version du 6 juillet 2017 à 02:13
Ligne 5 :		Ligne 5 :
	<li>Etudiant : Candice ROBERT</li>		<li>Etudiant : Candice ROBERT</li>
	</ul>		</ul>
	''Les programmes sont réalisés ~~avec~~ ~~sage~~''		''Les programmes sont réalisés en python et utilisent des librairies écrites par M Provencal''

	== Approche mathématique des labyrinthes ==		== Approche mathématique des labyrinthes ==

C.robert : /* Algorithme de Prim */

2017-07-06T02:10:55Z

Algorithme de Prim

← Version précédente		Version du 6 juillet 2017 à 02:10
Ligne 180 :		Ligne 180 :
	La fonction principale :		La fonction principale :
	<pre>		<pre>



	def algoPrim(G) :		def algoPrim(G) :
	attribuerPoids(G)		attribuerPoids(G)

C.robert : /* Algorithme de Prim */

2017-07-06T02:10:35Z

Algorithme de Prim

@@ Ligne 165 : / Ligne 165 : @@
 À chaque répétition, on ajoute à l'arbre le sommet libre accessible de poids minimal.
 On s'arrête quand l'arbre est recouvrant.
 <pre>
-Initialiser un dictionnaire poids
+    poids = {}
-   poids[u]= oo
+        poids[(u,v)]= x
-   pere[u] = None
+        poids[(v,u)]= x
 </pre>

C.robert : /* parcoursProfondeur2 */

2017-07-06T02:02:27Z

parcoursProfondeur2

← Version précédente		Version du 6 juillet 2017 à 02:02
Ligne 156 :		Ligne 156 :

	[[Fichier:Maze(parcoursP_ac_aléa).png]]		[[Fichier:Maze(parcoursP_ac_aléa).png]]

			Nous avons donc pu voir que ces deux méthodes, bien qu'elles permettent effectivement de construire des labyrinthes, ont leurs limites. Le dernier résultat obtenu avec parcoursProfondeur2 se rapproche de ce qu'on souhaiterait obtenir, mais nous allons voir d'autres méthodes de générations de labyrinthe, afin de déterminer laquelle est la plus efficace.

	====Arbre couvrant minimum====		====Arbre couvrant minimum====

C.robert : /* Ajout d'aléatoire sur les deux dernières méthodes */

2017-07-06T01:58:21Z

Ajout d'aléatoire sur les deux dernières méthodes

@@ Ligne 96 : / Ligne 96 : @@
 Pour rendre les labyrinthes obtenus moins réguliers, nous avons ajouté un aspect aléatoire (dans l'ordre de sélection des voisins des sommets). Voici donc les nouvelles versions de parcoursLargeur ainsi que de parcoursProfondeur:
-=====ParcoursLargeur2=====
+=====parcoursLargeur2=====
 <pre>
@@ Ligne 127 : / Ligne 127 : @@
 [[Fichier:Maze(parcoursL_ac_aléa).png]]
 ====Arbre couvrant minimum====

C.robert : /* Algorithmes de construction de l'arbre couvrant */

2017-07-06T01:55:26Z

Algorithmes de construction de l'arbre couvrant

← Version précédente		Version du 6 juillet 2017 à 01:55
Ligne 91 :		Ligne 91 :

	[[Fichier:Maze(parcoursP_ss_aléa).png]]		[[Fichier:Maze(parcoursP_ss_aléa).png]]

			====Ajout d'aléatoire sur les deux dernières méthodes====

			Pour rendre les labyrinthes obtenus moins réguliers, nous avons ajouté un aspect aléatoire (dans l'ordre de sélection des voisins des sommets). Voici donc les nouvelles versions de parcoursLargeur ainsi que de parcoursProfondeur:

			=====ParcoursLargeur2=====

			<pre>
			def parcoursLargeur2(G):
			"""Ce programme choisi les voisins aléatoirement"""
			vu = set()
			L = deque() # insérer : L.append( ), retirer : L.popleft()
			A = Graph()
			A.add_vertices( G.vertices() )
			A.set_pos( G.get_pos() ) # juste pour l'affichage

			s = (0,0)
			vu.add(s)
			L.append(s)

			while len(L)>0:
			u = L.popleft()
			voisins = G.neighbors(u)
			for x in range(0,len(G.neighbors(u))):
			v = random.choice(voisins)
			if v not in vu:
			A.add_edge(u, v)
			L.append(v)
			vu.add(v)
			voisins.remove(v)
			return A
			</pre>

			Le labyrinthe obtenu :

			[[Fichier:Maze(parcoursL_ac_aléa).png]]

	====Arbre couvrant minimum====		====Arbre couvrant minimum====

C.robert : /* Parcours en profondeur du graphe */

2017-07-06T01:48:44Z

Parcours en profondeur du graphe

← Version précédente		Version du 6 juillet 2017 à 01:48
Ligne 69 :		Ligne 69 :
	[[Fichier:profondeur.gif]]		[[Fichier:profondeur.gif]]

	Voici le programme :
	<pre>		<pre>
	def parcoursProfondeur(G) :		def parcoursProfondeur(G) :
	vu = set()		vu = set()
	A = Graph()		A = Graph()
			A.add_vertices( G.vertices() )
			A.set_pos( G.get_pos() )
	s = (0,0)		s = (0,0)
	parcoursProfondeurRec(G,s,A,vu)		parcoursProfondeurRec(G,s,A,vu)
			return A

	def parcoursProfondeurRec(G,u,A,vu):		def parcoursProfondeurRec(G,u,A,vu):
Ligne 81 :		Ligne 83 :
	for v in G.neighbors(u):		for v in G.neighbors(u):
	if v not in vu:		if v not in vu:
	A.add_edge(u, v)		A.add_edge(u,v)
	vu.add(v)		vu.add(v)
	parcoursProfondeurRec(G,u,A,vu) #Ici le ~~programme~~ ~~fait~~ ~~appel~~ ~~à lui même~~		parcoursProfondeurRec(G,v,A,vu) # Ici la fonction s'appelle elle-même !
	</pre>		</pre>

			Et un résultat obtenu :

			[[Fichier:Maze(parcoursP_ss_aléa).png]]

	====Arbre couvrant minimum====		====Arbre couvrant minimum====

C.robert : /* Parcours en largeur du graphe */

2017-07-06T01:45:46Z

Parcours en largeur du graphe

← Version précédente		Version du 6 juillet 2017 à 01:45
Ligne 59 :		Ligne 59 :

	Et un résultat obtenu à partir de cette fonction :		Et un résultat obtenu à partir de cette fonction :

			[[Fichier:Maze_(parcoursL_ss_aléa).png]]

			Bien qu'il soit complètement régulier, il s'agit bien d'un labyrinthe parfait. Nous l'améliorerons plus tard.

	====Parcours en profondeur du graphe====		====Parcours en profondeur du graphe====

Génération et résolution de labyrinthes - Historique des versions

C.robert : /* Sortir d'un labyrinthe à l'aide du parcours en profondeur */

C.robert : /* Sortie d'un labyrinthe */

C.robert le 6 juillet 2017 à 02:13

C.robert : /* Algorithme de Prim */

C.robert : /* Algorithme de Prim */

C.robert : /* parcoursProfondeur2 */

C.robert : /* Ajout d'aléatoire sur les deux dernières méthodes */

C.robert : /* Algorithmes de construction de l'arbre couvrant */

C.robert : /* Parcours en profondeur du graphe */

C.robert : /* Parcours en largeur du graphe */

C.robert : /* Sortir d'un labyrinthe à l'aide du parcours en profondeur */

C.robert : /* Sortie d'un labyrinthe */

C.robert : /* Algorithme de Prim */

C.robert : /* Algorithme de Prim */

C.robert : /* parcoursProfondeur2 */

C.robert : /* Ajout d'aléatoire sur les deux dernières méthodes */

C.robert : /* Algorithmes de construction de l'arbre couvrant */

C.robert : /* Parcours en profondeur du graphe */

C.robert : /* Parcours en largeur du graphe */