IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Exercices Python Discussion :

Plus court Chemin Labyrinthe


Sujet :

Exercices Python

  1. #1
    Nouveau Candidat au Club
    Homme Profil pro
    Étudiant
    Inscrit en
    mai 2020
    Messages
    3
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Hauts de Seine (Île de France)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : mai 2020
    Messages : 3
    Points : 1
    Points
    1
    Par défaut Plus court Chemin Labyrinthe
    Bonjour,

    J'ai un exo à réaliser en Python mais je suis un peu perdu.

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    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
    59
    60
    61
    62
    63
     
    labyrinth = [[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
                 [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0],
                 [1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1],
                 [1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1],
                 [1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1],
                 [1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1],
                 [1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1],
                 [1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1],
                 [1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1],
                 [1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1],
                 [1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1],
                 [1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1],
                 [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1],
                 [1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1],
                 [1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1],
                 [1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1],
                 [1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1],
                 [1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1],
                 [1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1],
                 [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
                 [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]]
     
    class Labyrinth:
     
        def __init__(self, labyrinth, begin, end):
            self.__labyrinth = labyrinth
            self.__begin = begin
            self.__end = end
            self.__solution = []
     
        def set_solution(self, solution):
            self.__solution = solution
     
        def __str__(self):
            r = ""
            for y, line in enumerate(labyrinth):
                r += "\n"
                for x, c in enumerate(line):
                    if c == 1:
                        r += u"\u2588" + u"\u2588"
                    elif (x, y) == self.__begin:
                        r += 'b '
                    elif (x, y) == self.__end:
                        r += ' e'
                    elif (x, y) in self.__solution:
                        r += '::'                    
                    else:
                        r += '  '
            return r
     
        def find_solution(self):
            """
            This method must return the shortest solution of the labyrinth.
            It's represented as the list of all the coordinates of the path's cells
            """
            return [(0, 19), (1, 19), (1, 18), (1, 17), (2, 17), (3, 17), (3, 16), (3, 15), (4, 15), (5, 15), (6, 15), (7, 15), (7, 16), (7, 17), (7, 18), (7, 19), (8, 19), (9, 19), (10, 19), (11, 19), (12, 19), (13, 19), (14, 19), (15, 19), (16, 19), (17, 19), (18, 19), (19, 19), (19, 18), (19, 17), (18, 17), (17, 17), (16, 17), (15, 17), (15, 16), (15, 15), (15, 14), (15, 13), (16, 13), (17, 13), (17, 12), (17, 11), (17, 10), (17, 9), (17, 8), (17, 7), (17, 6), (17, 5), (17, 4), (17, 3), (17, 2), (17, 1), (18, 1), (19, 1), (20, 1)]
     
    l = Labyrinth(labyrinth, (0, 19), (20, 1))
    solution = l.find_solution()
     
    l.set_solution(solution)
    print(l)
    Les 1 représentent les murs et les 0 les endroits où l'on peut passer.
    Le but est de remplir la fonction find_solution qui renvoie la liste des coordonnées du plus court chemin pour résoudre le labyrinthe.
    Je pense que la façon la plus simple est d'utiliser le BFS mais je ne vois pas comment l'implémenter.

    Merci d'avance,

  2. #2
    Expert éminent sénior
    Homme Profil pro
    Architecte technique retraité
    Inscrit en
    juin 2008
    Messages
    17 532
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Manche (Basse Normandie)

    Informations professionnelles :
    Activité : Architecte technique retraité
    Secteur : Industrie

    Informations forums :
    Inscription : juin 2008
    Messages : 17 532
    Points : 30 251
    Points
    30 251
    Par défaut
    Salut,

    Citation Envoyé par Tomqu Voir le message
    Je pense que la façon la plus simple est d'utiliser le BFS mais je ne vois pas comment l'implémenter.
    C'est un exercice assez connu. Chercher un peu sur Internet avec les mots clefs "python maze graph" devrait récupérer quelques sources d'inspiration.

    - W
    Architectures post-modernes.
    Python sur DVP c'est aussi des FAQs, des cours et tutoriels

  3. #3
    Nouveau Candidat au Club
    Homme Profil pro
    Étudiant
    Inscrit en
    mai 2020
    Messages
    3
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Hauts de Seine (Île de France)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : mai 2020
    Messages : 3
    Points : 1
    Points
    1
    Par défaut
    Citation Envoyé par wiztricks Voir le message
    Salut,



    C'est un exercice assez connu. Chercher un peu sur Internet avec les mots clefs "python maze graph" devrait récupérer quelques sources d'inspiration.

    - W
    J'ai commencé par transformer mon labyrinthe en un dictionnaire avec comme clés chaque coordonné et valeur ses voisins.

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    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
     
    dictvoisins=dict()
     
            for y,line in enumerate(labyrinth):
                for x,c in enumerate(line):
                    voisins=[]
     
                    try:
     
     
                        if labyrinth[x-1][y]==0:
                            if x-1>=0  :
     
                                voisins.append((y,x-1))
                        if labyrinth[x][y-1]==0:
     
                            if y-1>=0:
                                voisins.append((y-1,x))
                        if labyrinth[x+1][y]==0:
                            if x+1<=len(labyrinth):
     
                                voisins.append((y,x+1))
                        if labyrinth[x][y+1]==0:
     
                            if y+1<=len(labyrinth):
                                voisins.append((y+1,x))
     
                    except IndexError:
                        continue
     
                    dictvoisins[(y,x)]=voisins
    Mais lorsque j'exécute, je ne comprends pas pourquoi il ne va pas jusqu'à 20 (mon labyrinthe étant 21*21)
    Il s'arrête à 19 donc je n'ai par exemple pas la clé (0,20) ou (20,3)

  4. #4
    Expert éminent sénior
    Homme Profil pro
    Architecte technique retraité
    Inscrit en
    juin 2008
    Messages
    17 532
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Manche (Basse Normandie)

    Informations professionnelles :
    Activité : Architecte technique retraité
    Secteur : Industrie

    Informations forums :
    Inscription : juin 2008
    Messages : 17 532
    Points : 30 251
    Points
    30 251
    Par défaut
    Salut,

    Si cachez la misère sous le tapis avec:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
         try:
         ....
         except IndexError:
                continue
    çà fait des choses étranges.

    Et çà veut surtout dire que vous n'avez pas trop réfléchit à ce que vous vouliez avant de coder.

    - W
    Architectures post-modernes.
    Python sur DVP c'est aussi des FAQs, des cours et tutoriels

  5. #5
    Nouveau Candidat au Club
    Homme Profil pro
    Étudiant
    Inscrit en
    mai 2020
    Messages
    3
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Hauts de Seine (Île de France)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : mai 2020
    Messages : 3
    Points : 1
    Points
    1
    Par défaut
    En effet, le IndexError était juste un test, il n'était pas la au départ.
    Mon problème est de créer le dictionnaire avec les voisins de chaque sommet (représenté par ses coordonnés).
    J'ai surtout du mal avec la gestion des bords.

  6. #6
    Expert éminent sénior
    Homme Profil pro
    Architecte technique retraité
    Inscrit en
    juin 2008
    Messages
    17 532
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Manche (Basse Normandie)

    Informations professionnelles :
    Activité : Architecte technique retraité
    Secteur : Industrie

    Informations forums :
    Inscription : juin 2008
    Messages : 17 532
    Points : 30 251
    Points
    30 251
    Par défaut
    Salut,

    Citation Envoyé par Tomqu Voir le message
    J'ai surtout du mal avec la gestion des bords.
    Vous pouvez fabriquer une fonction qui retourne la liste des cases voisines pour chaque (i, j), puis vous filtrez les cases "valides", puis vous récupérer les cases accessibles.

    Vous pouvez aussi ajouter des des bords (des cases inaccessibles) au tableau, ce qui évite un tas de tests.

    C'est plus un problème d'algo. que de code.

    - W
    Architectures post-modernes.
    Python sur DVP c'est aussi des FAQs, des cours et tutoriels

Discussions similaires

  1. Plus court chemin labyrinthe
    Par lalala8434 dans le forum C++
    Réponses: 1
    Dernier message: 06/08/2019, 21h29
  2. Calcul de plus court chemin dans un graphe
    Par Elmilouse dans le forum Prolog
    Réponses: 6
    Dernier message: 21/03/2010, 20h26
  3. N plus courts chemin dans un graphe
    Par MLK jr dans le forum Algorithmes et structures de données
    Réponses: 6
    Dernier message: 13/03/2006, 00h32
  4. [algo] plus courts chemins (au pluriel !!)
    Par ADSL[fx] dans le forum Algorithmes et structures de données
    Réponses: 9
    Dernier message: 18/01/2006, 14h40
  5. Réponses: 2
    Dernier message: 21/03/2004, 18h57

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo