rech-larg.lisp

;;;;;;;;;;;;;;;;;;;;;;;;; VERSION COMMENTEE ;;;;;;;;;;;;;;;;;;;;;;;;;

; Fonction de service permettant d'afficher le chemin menant à un état 'etat'
;
; Entrées : 
;	'etat' : l'état final 
;	'peres' : le tableau des pères : ce tableau contient des couples (fils;père) permettant de retrouver le père de chaque noeud
;	'racine' : la racine de l'arbre 

; Sortie : affiche le chemin menant à l'état demandé

(defun print-chemin(etat peres racine)
	; variable contenant le chemin
	(setq chemin nil)
	; on ajoute l'état cible au chemin
	(push etat chemin)

	; on cherche les états menant à 'etat'
	(loop
		; tant qu'on n'est pas à la racine, on continue
		(if (not(equal etat (car racine)))
			(progn
				; on ajoute le père de chaque noeud au chemin puis on cherche le père du père...
				(setq etat (cadr (assoc etat peres)))
   				(push etat chemin)
     		)
     		; on a atteint la racine, on affiche le chemin
     		(prog1
     			(print chemin)
				(return-from nil)
			)
		)
	)
)

; Fonction effectuant la recherche en largeur 
;
; Entrée : l'état initial, dans notre cas l'état (0;0)
; Sortie : le plus court chemin menant à chaque solution
;
; Exemple : (rech-larg '((0 0)))

; Pour cette recherche, nous nous basons sur le principe des files.
; On retire le premier noeud de la file, on le visite, puis on ajoute ses fils à la file et ainsi de suite.
; De cette manière, on visitera à chaque fois un noeud et ses voisins puis leurs fils dans le bon ordre. 

(defun rech-larg(etat)
	; variable contenant notre file, on l'initialise avec l'état initial
	(setq a_visiter etat)
	; variable contenant les états visités
	(setq history nil)
	; variable contenant le tabeau des pères, les couples (fils, père), ce tableau nous sera utile pour retrouver le chemin menant à un noeud
	(setq peres nil)

	; on va parcourir l'arbre jusqu'à ce que la file soit vide, c'est-à-dire jusqu'à ce que tous les noeuds soit visités
	(loop
		(if (not (null a_visiter))
			; la file n'est pas vide
			(progn
				; variable contenant la tête de la file, le noeud à visiter
				(setq current (car a_visiter))
				; on ajoute ce noeud aux noeuds visités
				(push current history)
				; on teste si ce noeud est un noeud solution 
				(if (= (car current) 2)	
					; auquel cas, on veut renvoyer le chemin qui mène à ce noeud
					(progn
						(print-chemin current peres etat)
						; pour voir le tableau des pères
						;(print peres)
					)
					; si ce n'est pas un noeud solution, on se contente d'ajouter ses fils à la file
					(progn
						; on utilise la fonction de service 'successeurs' définie précédemment
						; s représente le fils du noeud 'current'
						(dolist (s (successeurs current history) t)
							; on ajoute le fils à la fin de la file, d'où l'utilisation de '(cdr(last a_visiter))'
							(push s (cdr(last a_visiter)))
							; on ajoute chaque couple (fils,père) au tableau des pères
							(push (list s current) peres)
						)
					)
				)
				; on retire la tête de file, le noeud qui vient d'être visité
				(pop a_visiter)
			)
			; la file est vide, on sort de la boucle
			(return-from nil)
		)
	)
)