Recherche espace d'états [Résolu]

[Lyadrielle]

Bonsoir,

Voici le lien menant au TP que je dois faire en lisp. (http://www.fichier-pdf.fr/2012/11/19/tp02-a12/)

Je dois donc faire une recherche dans un espace d'états.

J'ai recherché 8 règles permettant de regrouper tous les états possibles pour les deux récipients :

1 : (x < 4, y) -> (4 y)
2 : (x > 0, y) -> (0 y)
3 : (x, y < 3) -> (x 3)
4 : (x, y > 0) -> (x 0)
5 : (x > 0, x+y < 4) -> (0 x+y)
6 : (x+y < 5, y > 0) -> (x+y 0)
7 : (x < 4, x+y > 4) -> (4 y-(4 - x))
8 : (x+y > 3, y < 3) -> (x-(3 - y) 3)

Ma fonction 'actions' permet de lister les règles possibles pour un état donné :

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
(defun actions (etat)
  
  (let ((regle))
   
   (if (AND (< (car etat) 4) (OR (equal (cadr etat) 0) (equal (cadr etat) 1) (equal (cadr etat) 2) (equal (cadr etat) 3)))
    (progn (format t "Regle R1 ~&")
    (setq regle 'R1)
      (push regle *regles*)))
    
   (if (AND (> (car etat) 0) (OR (equal (cadr etat) 0) (equal (cadr etat) 1) (equal (cadr etat) 2) (equal (cadr etat) 3)))
    (progn (format t "Regle R2 ~&")
    (setq regle 'R2)
      (push regle *regles*)))
    
   (if (AND (OR (equal (car etat) 0) (equal (car etat) 1) (equal (car etat) 2) (equal (car etat) 3) (equal (car etat) 4)) (< (cadr etat) 3))
    (progn (format t "Regle R3 ~&")
    (setq regle 'R3)
      (push regle *regles*)))
    
   (if (AND (OR (equal (car etat) 0) (equal (car etat) 1) (equal (car etat) 2) (equal (car etat) 3) (equal (car etat) 4)) (> (cadr etat) 0))
   (progn (format t "Regle R4 ~&")
    (setq regle 'R4)
     (push regle *regles*)))
    
   (if (AND (> (car etat) 0) (< (+ (car etat) (cadr etat)) 4))
    (progn (format t "Regle R5 ~&")
    (setq regle 'R5)
      (push regle *regles*)))
    
   (if (AND (< (+ (car etat) (cadr etat)) 5) (> (cadr etat) 0))
   (progn (format t "Regle R6 ~&")
    (setq regle 'R6)
     (push regle *regles*)))
    
   (if (AND (< (car etat) 4) (> (+ (car etat) (cadr etat)) 4))
    (progn (format t "Regle R7 ~&")
    (setq regle 'R7)
      (push regle *regles*)))
    
  (if (AND (> (+ (car etat) (cadr etat)) 3) (< (cadr etat) 3))
   (progn (format t "Regle R8 ~&")
    (setq regle 'R8)
    (push regle *regles*)))
  
    (setq *regles* (reverse *regles*))
    ))

Ma fonction 'resultat' permet de calculer, pour une règle donnée et un état donné, l'état suivant :

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
(defun resultat (etat regle)
  (declare (special etat))
  
  (let ((x (car etat)) (y (cadr etat)))
    
  (pushnew (list x y) *etatsVisites* :test #'equal)  
     
  (cond ((equal regle 'R1)
        (setq x 4))
        
        ((equal regle 'R2)
        (setq x 0))
        
        ((equal regle 'R3)
        (setq y 3))
        
        ((equal regle 'R4)
        (setq y 0))
        
        ((equal regle 'R5)
        (setq y (+ (eval x) (eval y))))
        
        ((equal regle 'R6)
        (setq x (+ (eval x) (eval y))))
        
        ((equal regle 'R7)
         (setq x 4)
         (setq y (- (eval y) (- 4 (eval x)))))
  
        ((equal regle 'R8)
         (setq x (- (eval x) (- 3 (eval y))))
         (setq y 3))
        )
    
   (list x y)))

Ces deux fonctions marchent bien.

Ce n'est pas le cas de ma troisième fonction que je n'arrive pas à coder =/

Cette fonction doit retourner la liste des états suivants (suivant l'état actuel) non encore visités.

Voici ce que j'ai tenté :

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
(defun successeurs (etat *etatsVisites*)
  
  (declare (special etat))
  
  (let ((liste_actions nil)(liste nil)(liste_member nil))
    
    (setq liste_actions (actions etat))
    
    (dolist (regle liste_actions)
      
      (setq liste (resultat etat regle))
      (setq liste_member (member liste *etatsVisites* :test #'equal))

      (if (member liste *etatsVisites* :test #'equal)
          (prog2 (format t "Etat déjà visité~&")
              (pop (member liste *etatsVisites* :test #'equal)))
          (pushnew liste *etatsNonVisites* :test #'equal))
      )
    
      *etatsNonVisites*  
    ))

Le problème est que, même si je supprime l'élément déjà visité de liste_member, quand j'afficherai *etatsNonVisites*, il ne sera pas modifié et je ne sais pas comment faire >< !

Voici mes variables globales :

Code :

1
2
3
4
(setq *regles* ())

(setq *etatsVisites* ())
(setq *etatsNonVisites* ())

Pour les deux autres qu'il me reste à faire, je ne sais pas encore très bien comment m'y prendre mais je vais y réfléchir.

Merci à vous par avance.

Bonne soirée

[jack-ft]

Envoyé par Lyadrielle

Bonsoir,

Voici le lien menant au TP que je dois faire en lisp. (http://www.fichier-pdf.fr/2012/11/19/tp02-a12/)

Je me souviens avoir fait ça (pour m'amuser, il y a une dizaine d'années)

avec un résultat comme ça:

Code :

1
2
3
4
5
6
7
8
(bs-solve '((3 . 0) (5 . 0) (8 . 8)) 4 "Buckets")
=>
(0 0 8) [3 -> 2] (0 5 3)
(0 5 3) [2 -> 1] (3 2 3)
(3 2 3) [1 -> 3] (0 2 6)
(0 2 6) [2 -> 1] (2 0 6)
(2 0 6) [3 -> 2] (2 5 1)
(2 5 1) [2 -> 1] (3 4 1)

et l'arbre complet des transitions possibles:

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
(0 0 8) [3 -> 2] (0 5 3)
    (0 5 3) [3 -> 1] (3 5 0)
        (3 5 0) [2 -> 3] (3 0 5)
            (3 0 5) [3 -> 2] (3 5 0)
            (3 0 5) [1 -> 3] (0 0 8)
            (3 0 5) [1 -> 2] (0 3 5)
                (0 3 5) [3 -> 2] (0 5 3)
                (0 3 5) [3 -> 1] (3 3 2)
                    (3 3 2) [3 -> 2] (3 5 0)
                    (3 3 2) [2 -> 3] (3 0 5)
                    (3 3 2) [1 -> 3] (0 3 5)
                    (3 3 2) [1 -> 2] (1 5 2)
                        (1 5 2) [3 -> 1] (3 5 0)
                        (1 5 2) [2 -> 3] (1 0 7)
                            (1 0 7) [3 -> 2] (1 5 2)
                            (1 0 7) [3 -> 1] (3 0 5)
                            (1 0 7) [1 -> 3] (0 0 8)
                            (1 0 7) [1 -> 2] (0 1 7)
                                (0 1 7) [3 -> 2] (0 5 3)
                                (0 1 7) [3 -> 1] (3 1 4)
                                    (3 1 4) [3 -> 2] (3 5 0)
                                    (3 1 4) [2 -> 3] (3 0 5)
                                    (3 1 4) [1 -> 3] (0 1 7)
                                    (3 1 4) [1 -> 2] (0 4 4)
                                        (0 4 4) [3 -> 2] (0 5 3)
                                        (0 4 4) [3 -> 1] (3 4 1)
                                            (3 4 1) [3 -> 2] (3 5 0)
                                            (3 4 1) [2 -> 3] (3 0 5)
                                            (3 4 1) [1 -> 3] (0 4 4)
                                            (3 4 1) [1 -> 2] (2 5 1)
                                                (2 5 1) [3 -> 1] (3 5 0)
                                                (2 5 1) [2 -> 3] (2 0 6)
                                                    (2 0 6) [3 -> 2] (2 5 1)
                                                    (2 0 6) [3 -> 1] (3 0 5)
                                                    (2 0 6) [1 -> 3] (0 0 8)
                                                    (2 0 6) [1 -> 2] (0 2 6)
                                                        (0 2 6) [3 -> 2] (0 5 3)
                                                        (0 2 6) [3 -> 1] (3 2 3)
                                                            (3 2 3) [3 -> 2] (3 5 0)
                                                            (3 2 3) [2 -> 3] (3 0 5)
                                                            (3 2 3) [1 -> 3] (0 2 6)
                                                            (3 2 3) [1 -> 2] (0 5 3)
                                                        (0 2 6) [2 -> 3] (0 0 8)
                                                        (0 2 6) [2 -> 1] (2 0 6)
                                                (2 5 1) [2 -> 1] (3 4 1)
                                                (2 5 1) [1 -> 3] (0 5 3)
                                        (0 4 4) [2 -> 3] (0 0 8)
                                        (0 4 4) [2 -> 1] (3 1 4)
                                (0 1 7) [2 -> 3] (0 0 8)
                                (0 1 7) [2 -> 1] (1 0 7)
                        (1 5 2) [2 -> 1] (3 3 2)
                        (1 5 2) [1 -> 3] (0 5 3)
                (0 3 5) [2 -> 3] (0 0 8)
                (0 3 5) [2 -> 1] (3 0 5)
        (3 5 0) [1 -> 3] (0 5 3)
    (0 5 3) [2 -> 3] (0 0 8)
    (0 5 3) [2 -> 1] (3 2 3)
(0 0 8) [3 -> 1] (3 0 5)

[Lyadrielle]

En effet, c'est pas mal ^^''

J'ai finalement fini de coder la fonction sur les états successeurs et j'ai également fait les fonctions de parcours en largeur et profondeur.

Pour ceux que ça intéresse, contactez-moi.