Partage
  • Partager sur Facebook
  • Partager sur Twitter

Entre les filets du BackTracking

    21 juin 2019 à 10:57:58

    Bonjour a tous , 

    Je dois effectuer un BackTracking dans le cadre de l'exercice suivant : 

    Nous cherchons a creer une coalition de partis politiques avec le maximum de mandats possibles 

    Je possède un tableau de booléen can_collaborate[N][N] qui me permet de savoir qui veut etre dans la coalition , un tableau mandates[N] qui nous donne le nombre de mandat par parti politique.

    Mon BackTracking marche mais ne fait pas tout les cas possibles ( me renvoie une coalition possible mais pas la plus grande possible )

    int max_coalition(int mandates[], bool can_collaborate[][N],
                      int max_parties[N])
    {
        bool chosen[N] ;
        for (int i=0;i<N;i++)
            chosen[i]=false;
        for (int i=0;i<N;i++)
            max_parties[i]=-1;
    
    
        int sum_to_check = 60;
        max_coalition_aux (mandates,can_collaborate,max_parties,chosen,0,&sum_to_check);
    
        return countParties(chosen);
    }
    
    
    bool max_coalition_aux (int mandates[], bool can_collaborate[][N],
                           int max_parties[N],bool chosen[N],int current,int *sum) {
    
    
        if (current == N)
            return IsLegalCoallition(mandates, can_collaborate, chosen);
    
        int highestIdOpened = 0;
        for (int i = 0; i < current; ++i)
            highestIdOpened = max(highestIdOpened, max_parties[i]);
    
        int partiId;
        for (partiId = 0; partiId <= highestIdOpened + 1; ++partiId) {
    
            if (chosen[partiId] != false)
                continue;
    
            if (isLegalPlacement(can_collaborate, chosen, current)) {
    
                chosen[partiId] = true;
    
                max_parties[current] = partiId;
    
                if (max_coalition_aux(mandates, can_collaborate, max_parties,
                                      chosen, current + 1, sum) == true) {
                    placeParties(chosen, max_parties, mandates, sum);
                    return true;
                }
            }
            chosen[partiId] = false;
            max_parties[current] = -1;
        }
        return max_coalition_aux(mandates, can_collaborate, max_parties,
                                 chosen, current + 1, sum);
    }

    Exemple : Dans le cas 

    20 14 30 16 40
    1 1 1 0 1
    1 1 1 1 1
    1 1 1 1 0
    0 1 1 1 1
    1 1 0 1 1 
    je devrais recevoir {0,1,4} mais je reçois {0,1,2}
    • Partager sur Facebook
    • Partager sur Twitter
      21 juin 2019 à 11:58:16

      Faut déboguer - essaie de trouver un exemple minimal qui te permet de trouver le problème. C'est à dire, un exemple que tu peux facilement faire à la main - et tu vérifies avec des print et/ou débogueur que tout se passe comme tu veux dans l'implémentation de ton algorithme.
      • Partager sur Facebook
      • Partager sur Twitter
        21 juin 2019 à 12:45:20

        oui justement jai essaye de debuger apres avoir trouve le {0,1,2} il s'arrete considérant avoir trouve la configuration requise
        • Partager sur Facebook
        • Partager sur Twitter
          21 juin 2019 à 13:16:39

          BellahsenRaphael a écrit:

          oui justement jai essaye de debuger apres avoir trouve le {0,1,2} il s'arrete considérant avoir trouve la configuration requise


          Du coup tu as déjà une piste pour chercher ! :) Tu n'as plus qu'à chercher maintenant pourquoi il "pense avoir trouvé la configuration requise"

          Met des printf dans les fonctions adéquates, et cherche à savoir pourquoi il s'arrête, puis une fois que tu sais pourquoi il s'arrête, remonte progressivement jusqu'à trouver la vraie raison.

          -
          Edité par potterman28wxcv 21 juin 2019 à 13:17:51

          • Partager sur Facebook
          • Partager sur Twitter

          Entre les filets du BackTracking

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