MOORE TES Déc.2013

 

                              FEUILLE     D'EXERCICES SUR MOORE- Dijskra

 

       EXERCICE 1

                          Moore       

   Trouver le plus court chemin de A à C.

--------------------------------------------------------------------------------------------------------------

  REPONSE:

  TABLEAU  DE MOORE  

   A      B        C         D         E        F          G        CHOIX DU CHEMIN         Sommet sélectionné   
    0    ∞    ∞    ∞    ∞      ∞      ∞

   A   

 A dans la colonne de F est le point inscrit le plus bas

        A
IIIIIII    10 A     ∞    ∞   10 A   6 A  ∞

                F  ↑

F dans la colonne de E est le point inscrit le plus bas

       F
IIIIIII   10 A   ∞

6 + 4 = 10 F

au lieu de  ∞ 

 6 + 2 = 8 F

 au lieu de 10 A

IIIIIII

  6 + 3 =9 F

au lieu de ∞ 

        E     ↑

E  dans la colonne de D est le point le plus bas

       E
IIIIIII

8+3= 11E

On garde 10A 

 ∞

8+1 = 9 E

au lieu de 10 F

IIIIIII IIIIIII      9 F

       D    ↑

D dans la colonne de C est le point le plus bas 

        D

On puvait sélectionner G 

au lieu de D

IIIIIII On garde 10A

9+1=10  D

au lieu de ∞ 

IIIIIII IIIIIII IIIIIII 9+1 =10 D              C    ↑

    C

  L'objectif est C 

IIIIIII   IIIIIII IIIIIII IIIIIII IIIIIII  IIIIIII    
IIIIIII   IIIIIII IIIIIII IIIIIII IIIIIII  IIIIIII    
IIIIIII   IIIIIII IIIIIII IIIIIII IIIIIII  IIIIIII    


 Attention " Sommet sélectionné" ne signifie pas  sommet adopté pour la chaîne

  "Sommet sélectionné " veut dire qu'on barre toutes les cases en dessous.

  ICI le plus court chemin est depoids  10.

           Il n'est pas unique.

      On a en remontant :   C  D E F A

        Conclusion:    L'un des chemeins le plus court de A à C est A - F - E - D - C.

                                    Son poids est  10   

                                   Sa longueur est  4   

                            Moore1

------------------------------------------------------------------------------------------------------------

             EXERCICE 2

           Graphe1

              Donner la plus courte chaîne de E à S et son poids.

-------------------------------------------------------------------------------------------------------------------------------------------

     REPONSE:

                 Tableau de Moore:

  A     B       C     D        E      S      Sommets retenus     Sommet sélectionné ( pas forcément retenu )    
 ∞   ∞   ∞  ∞   0              E
  3E   1 E  ∞  ∞ IIIIII  ∞            E           B 

 1 +1=2 B

au lieu de 3 E

IIIIII

1+3=4 B

au lieu de ∞ 

1 + 5 = 6 B

au lieu de ∞

IIIIII  ∞            B↑              A
IIIIII IIIIII

 2+3=5A

On garde 4 B

1 + 5 = 6 B IIIIII  ∞            C  ↑              C
IIIIIIIIIIII IIIIII IIIIIIIIIIII

 4+ 1=5 C

au lieu de  6 B

IIIIII

4 + 3 = 7 C

au lieu de ∞  

            D ↑

               D


IIIIIIIIIIII IIIIII IIIIIIIIIIII IIIIIIIIIIII IIIIII

 5+1=6D

au lieu de 7C

             S ↑              S
IIIIIIIIIIII IIIIII IIIIIIIIIIII IIIIIIIIIIII IIIIII IIIIIIIIIIII    
IIIIIIIIIIII IIIIII IIIIIIIIIIII IIIIIIIIIIII IIIIII IIIIIIIIIIII    

     En remontant on a :  S D C B E

            Conclusion:

                Le plus court chemin est E-B-C-D-S

                Son poids est 6

-----------------------------------------------------------------------------------------------