BDD IA Web services Architecture Info. Ubi.

M1

Recherche en largeur, profondeur, etc.

http://emmanuel.adam.free.fr/site -> TD BackTracking

A partir de nombres N = ( ... ) appliquer des actions A afin que N x A' = But avec But = nombre entier positif

A = (aO, ..., an) avec ai ∈ {0, 1}. A chaque étape -> choix d'une action

Parcours largeur

Ex N = (5, 12, 6, 9). Le but = 26 avec A = (0, 0, 0, 0)

O
  - 5
    - 17
      - 23
        - 32
      - 26
       - 32
    - 11
      - 23
        - 32
      - 20
        - 32
    - 14
      - 26
        - 32
      - 20
        - 32
  - 12
    - 17
    - 18
    - 21
  - 6
    - 11
    - 18
    - 15
  - 9
    - 14
    - 21
    - 15
      - 20
      - 27

Note : les valeurs en dessous sont clairement pas sûres. ¯\_(ツ)\_/¯

5 12 6 9 12 6 9 17 11 14 6 9 17 11 14 18 21
nl = (0000) (1000) (0100) (0010) (0001) (0100) (0010) (0000) (1100) (1010) (1001) (0010) (0001) (1100) (1001) (0100) (0100) (1101)
nc = Ø

Pour le parcours en profondeur ?

Les fils d'un noeud sont en tête de nl

5 12 6 9 17 11 14 12 6 9 6 9 17 11 14 18 21
nl = (0000) (1000) (0100) (0010) (0001) (1000) (1010) (0001) (0100) (0010) (0001) (1110) (1101) (1010) (1001) (0100) (0010) (0001)
nc = Ø (0000) (0100) (1000) (0000) (0000) (1100)

Parcours en profondeur avec but = 18

5 12 6 9 18 11 14 12 6 9 21 26 11 12 6 9
nl = (0000) (1111) (1101) (1010) (1001) (0010) (0001) (1011) (1001) (0100) (0100) (0010) (0001)
nc = Ø (0000) (1000) (1100) (1110) (0000) (1000) (1100) (1110) (1010) (0000) (1000) (1100) (1110) (1010) (1011) (1001) (0100)

Parcours en largeur avec but = 18

5 12 6 9 18 6 9 17 11 14 21 26 11 12 6 9
nl = (0000) (1111) (1101) (1010) (1001) (0010) (0001) (0100) (0010) (0001) (1100) (1010) (1101) (0010) (0001) (1100) (1010) (0001) (0100) (0101)
nc = Ø (0000) (0000) (1000) (0000) (1000) (0100)

Au niveau de l'implémentation de l'algorithme, il faut prendre en compte le fait que l'on crée des noeuds pour pouvoir faire de la mesure de performances. En Java par exemple, on pourrait avoir un attribut static qui calculerait le nombre de noeuds créés en tout lors de l'exécution du progamme.