Partage
  • Partager sur Facebook
  • Partager sur Twitter

Explication sur le code de force brute

Sujet résolu
    29 mars 2022 à 7:16:10

    Bonjour,

    j'ai trouvé cette très bonne vidéo, sur l'exercice du sac à dos:

    https://www.youtube.com/watch?v=wDsZhd1wEuk&t=929s&ab_channel=Algomius

    Mais je n'arrive pas à comprendre quelque chose sur le code de la version force brute. Le voici:

    def sacADos_force_brute(capacite, elements, elements_selection=[]):
        if elements:
            val1, lstVal1 = sacADos_force_brute(capacite, elements[1:], elements_selection)
            val = elements[0]
            if val[1] <= capacite: 
                val2, lstVal2 = sacADos_force_brute(capacite - val[1], elements[1:], elements_selection + [val])
                if val1 < val2:
                    return val2, lstVal2
            return val1, lstVal1
        else:
            return sum([i[2] for i in elements_selection]), elements_selection
        
    # Nom, poids, Valeur
    ele = [('Montre', 2, 1),
            ('Boule', 3, 1),
            ('Portrait', 6, 20)]
    
    print('Algo force', sacADos_force_brute(7, ele))

    Pourquoi par exemple 'val1' donne la valeur de l'objet de la liste(l'indice 2 de la liste), et pourquoi 'lstVal1' donne la liste de cet objet ?

    • Partager sur Facebook
    • Partager sur Twitter
      29 mars 2022 à 9:54:44

      il faut regarder la ligne 11: le 1er élément retourné est un nombre correspondant à une somme, et le 2nd est une liste

      et la fonction est une fonction récurrente.

      • Partager sur Facebook
      • Partager sur Twitter
        29 mars 2022 à 11:37:44

        Ok merci. Je comprends mieux.

        Il y a un dernier truc sur lequel je bloque encore un peu. Cette fonction récursive sort toutes les possibilités qui peuvent rentrer dans le sac, elle compare les valeurs avec val1 et val2. Mais je ne comprends pas comment elle compare toutes les valeurs entre elles. Je vois qu'elle compare la valeur actuelle avec la valeur précédente, mais en faisant un print de sortie, je ne vois pas comment elle compare toutes les combinaisons entre elles au final.

        En fait, la première fois qu'elle s'appelle elle même (à la ligne 3), elle ne fait rien, c'est ça (car le premier print du return donne '0 []')?

        -
        Edité par DamienZeh 29 mars 2022 à 12:08:24

        • Partager sur Facebook
        • Partager sur Twitter
          29 mars 2022 à 13:29:37

          elle compare le poids du 1er objet à la capacité fournie. la magie c'est la récursivité, on appelle à nouveau la fonction, avec la nouvelle capacité et avec la liste des éléments sans le 1er; donc de manière récursive on parcourt la liste des éléments.
          • Partager sur Facebook
          • Partager sur Twitter
            29 mars 2022 à 14:29:43

            Oui je comprends ça, ok.

            Mais par exemple(je me sers du degub pour parcourir le code et essayer de mieux le comprendre) sur la liste de 3 éléments, il va d'abord supprimer le premier, on boucle, il supprime le deuxième, on boucle, puis il supprime le dernier. 

            Et donc la on va dans le else pour en sortir '0[]'. Jusqu'a la, je comprends.

            Mais pourquoi ensuite on repart avec le dernier élément(Portait) dans la liste ? Je ne comprends pas, puisque juste avant, on avait la liste vide.

            -
            Edité par DamienZeh 29 mars 2022 à 14:31:21

            • Partager sur Facebook
            • Partager sur Twitter
              29 mars 2022 à 18:06:25

              on ne supprime pas, on fait appel (Appel1) à la même fonction mais en partant de l'élément suivant (ligne 3), qui va à son tour s'appeler (Appel2) en partant de l'élément suivant (qui sera donc ici le dernier), on va encore appeler (Appel3) la fonction, comme elements sera vide, on retournera la somme du poids (ici 0,[]).

              On poursuit ensuite le programme, donc ligne 4, si le poids du denier element de la liste (qui est à ce moment element[0]) est inférieur à la capacité, on s'appelle en passant la nouvelle capacité, le tableau des éléments (sans l'élément courant) et un elements_selection correspondant à l'élément courant.

              Comme dans cet appel, elements est vide, on va dans le else, donc on va retourner la somme des éléments_selection, donc le poids de l'objet, la liste elements_selection (soit 6,[('Portrait',6,20)]); val1 valant 0 et val2 valant 6, on retourne val2 et lstVal2, soit 6,[('Portrait',6,20)]

              Ces valeurs correspondent (si je ne me suis pas perdu) à val1,lstVal1 du second appel (donc Appel2) de la ligne 3 et on poursuit le programme pour cet appel

              • Partager sur Facebook
              • Partager sur Twitter
                29 mars 2022 à 18:46:10

                On se rend au else quand on a testé toutes les combinaisons.

                Si Ça n'est pas trop long, tu pourrais afficher les valeurs intermédiaires (valeurs, tableaux,, etc)

                -
                Edité par PierrotLeFou 29 mars 2022 à 18:55:05

                • Partager sur Facebook
                • Partager sur Twitter

                Le Tout est souvent plus grand que la somme de ses parties.

                  29 mars 2022 à 22:51:55

                  Popopoooo ...ok! Donc ça y est je crois que je vois!

                  Donc au premier appel, 'element[1:]'vaut le second objet, donc ('Boule', 3, 1), on le boucle une deuxième fois, et donc  'element[1:]' vaut ('Portrait', 6, 20), on le boucle une troisième fois, et donc 'element[1:]' vaut ([]), et on passe au else....mais en fait 'element[0]' vaut bien ('Portrait', 6, 20) et pas ([]), c'est bien ça ? Et oui comme tu dis,  'element[1:] ne supprime pas, il parcourt, c'est tout. donc  'element[0]' vaut bien le dernier élément.

                  C'est ça qui me perturbait.

                  Merci beaucoup de t'être embêté à écrire tout ça, c'est très gentil, merci!

                  Bon sang, en tant que débutant, ce n'est pas du tout évident, le récursif et l'algo en force brute en même temps...:waw:

                  -
                  Edité par DamienZeh 29 mars 2022 à 22:55:39

                  • Partager sur Facebook
                  • Partager sur Twitter
                    30 mars 2022 à 8:13:00

                    DamienZeh a écrit:

                    Donc au premier appel, 'element[1:]'vaut le second objet, donc ('Boule', 3, 1), on le boucle une deuxième fois, et donc  'element[1:]' vaut ('Portrait', 6, 20), on le boucle une troisième fois, et donc 'element[1:]' vaut ([]), et on passe au else....mais en fait 'element[0]' vaut bien ('Portrait', 6, 20) et pas ([]), c'est bien ça ?

                    Non ! :D

                    Utilise ton interpréteur pour tes tests,

                    >>> ele
                    [('Montre', 2, 1), ('Boule', 3, 1), ('Portrait', 6, 20)]
                    >>> ele[1:]
                    [('Boule', 3, 1), ('Portrait', 6, 20)]
                    



                    • Partager sur Facebook
                    • Partager sur Twitter

                    Celui qui trouve sans chercher est celui qui a longtemps cherché sans trouver.(Bachelard)
                    La connaissance s'acquiert par l'expérience, tout le reste n'est que de l'information.(Einstein)

                      30 mars 2022 à 10:48:05

                      et il n'y a pas de boucles ^^, on appelle 3 fois la ligne 3 à la inception (le film): on plonge dans un rêve (n°1) dans lequel on plonge dans un rêve (n°2 qui est le même que le n°1 ici) dans lequel on plonge dans un rêve (n°3); quand on sort du n°3, on est dans le n°2 et on peut poursuivre ce rêve; ensuite on sort du rêve n°2 et on est toujours dans le n°1, il faut sortir du n°1 pour refaire surface (et rien n'empêche de repartir dans un autre rêve quand on revient au rêve précédent)
                      • Partager sur Facebook
                      • Partager sur Twitter
                        30 mars 2022 à 18:21:57

                        ok...J'aime l'explication à la Nolan;). C'est clair. Merci.

                        -
                        Edité par DamienZeh 30 mars 2022 à 18:24:04

                        • Partager sur Facebook
                        • Partager sur Twitter
                          30 mars 2022 à 18:39:24

                          Si tu veux voir pourquoi ça s'appelle "force brute", je te donne un vieux problème que je devais résoudre.
                          On a un ensemble de 1000 bandes magnétiques remplies entre 1% et 100%
                          Trouver le plus grand nombre de bandes qu'on peut fusionner pour en générer une (ne dépassant pas 100%).
                          J'ai utilisé une méthode approximative car ma machine n'avait pas de pile, donc pas de récursivité efficace.
                          Il suffit de donner 1 comme valeur à chaque bande:
                          from random import randint
                          pool = [('UM'+str(i+1+10000)[-4:], randint(1, 100), 1) for i in range(1000)]
                          Et on appelle la fonction avec une capacité de 100
                          Tu verras que c'est relativement long à exécuter.

                          -
                          Edité par PierrotLeFou 30 mars 2022 à 18:59:07

                          • Partager sur Facebook
                          • Partager sur Twitter

                          Le Tout est souvent plus grand que la somme de ses parties.

                          Explication sur le code de force brute

                          × Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
                          • Editeur
                          • Markdown