Topic: LISP anyone? (Page 1 of 1)

;=========================================================================
;  ALGORITHME A*
;=========================================================================

(defun a* (taquinInit taquinFinal)
	(a*Interne 
				taquinFinal 
				(list (list taquinInit () (heuristique taquinInit taquinFinal) 0))
				()
	)
)


(defun a*Interne (taquinFinal ouverts fermes)
	(do 
			;; variables utilisées par la boucle
			(
				(etatCourant 					;variable
							(car ouverts) 	;valeur initiale
							(car ouverts)		;incrémentation
				)
			) 
			
			;; condition d'arrêt et résultat
			(
				;;condition d'arrêt
				(or (null ouverts) (equal (getTaquin etatCourant) taquinFinal)) 
				
				;; résultat
				(reverse (getChemin etatCourant))
			)
			
			
			; corps de la boucle
			
			(let* (
							;; on déclare 7 variables locales
							(taquinCourant		(getTaquin etatCourant))	; le taquin de l'état courant
							(gCourant					(getG etatCourant))				; le coût du chemin du l'état courant
							(cheminCourant    (getChemin etatCourant))	; le chemin de l'état courant
							
							; opérateurs : opérateurs applicables à l'état courant
							(operateurs				(operateursPossibles taquinCourant))
							
							; taquinsSuivantsEtOps contient les couples (op . taquin)
							;  où taquin est le taquin obtenu en applicant l'opérateur op au taquin de l'état courant
							(taquinsSuivantsEtOps   (mapcar (lambda (op) (cons op (taquinSuivant taquinCourant op))) operateurs))
							
							(ouvertsSansEtatCourant 		(cdr ouverts))
							
							; ouvertsEtFermes est le doublet constitué des listes ouverts et fermes 
							; enrichies des nouveaux états construits à l'aide des taquinsSuivants 
					 		; le taquin de l'état courant
							(ouvertsEtFermes			(completerOuvertsEtFermes taquinFinal gCourant cheminCourant taquinsSuivantsEtOps ouvertsSansEtatCourant fermes))

					 )
					 
					
							(setf ouverts (car ouvertsEtFermes))
							; on insère l'état courant dans la liste des états fermés
							(setf fermes  (inserer taquinCourant cheminCourant (getH etatCourant) gCourant (cdr ouvertsEtFermes)))
			)
	)	; fin de la boucle 
)



;-------------------------------------------------------------------------
;	(completerOuvertsEtFermes taquinFinal g chemin taquinsSuivantsEtOps ouverts fermes) 
;  retourne le doublet contenant les nouvelles valeurs des listes ouverts et fermes
; après insertion des nouveaux états
;-------------------------------------------------------------------------
(defun completerOuvertsEtFermes (taquinFinal g chemin taquinsSuivantsEtOps ouverts fermes)
	(cond
		;;Condition si l'etat dans le quel on se trouve n'apartient ni à ouverts ni à fermés
		(
		    (and (equal (taquinMembre (cdar taquinsSuivantsEtOps) ouverts) NIL) (equal (taquinMembre (cdar taquinsSuivantsEtOps)   fermes) NIL))
   		    (list (inserer (cdar taquinsSuivantsEtOps) (append (list (caar taquinsSuivantsEtOps)) chemin) (heuristique (cdar taquinsSuivantsEtOps) taquinFinal) (getG (cdar taquinsSuivantsEtOps)) ouverts) fermes)
		)
		(t (list ouverts fermes))
	
	)
	
)


;-------------------------------------------------------------------------
;	(insererEtOter taquinFinal taquin chemin h g listeEtats) 
;  insère le nouvel état correspondant au taquin dans la liste listeEtats après avoir
; ôter l'état de cette liste contenant ce même taquin
;-------------------------------------------------------------------------
(defun insererEtOter (taquin chemin h g listeEtats)
  ;; A COMPLETER
  (inserer taquin chemin h g (oter taquin listeEtats)) 
)

;-------------------------------------------------------------------------
;	(inserer taquin chemin h g listeEtats) 
;  insère le nouvel état correspondant au taquin dans la liste listeEtats
;-------------------------------------------------------------------------
(defun inserer (taquin chemin h g listeEtats)
	;; A COMPLETER
	(cond
		(
			(not (equal chemin NIL))
			(sort (append (list (list taquin chemin h g)) listeEtats) #'(lambda (x y) (< (+ (car x) (car(car x))) (+ (car y) (car(car y))))))	
		)
		(t (append (list (list taquin chemin h g)) listeEtats))
	)
)