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

Mathématiques Discussion :

Parcours de tous les chemins d'un graphe


Sujet :

Mathématiques

  1. #21
    Nouveau membre du Club
    Homme Profil pro
    Inscrit en
    Octobre 2010
    Messages
    31
    Détails du profil
    Informations personnelles :
    Sexe : Homme

    Informations forums :
    Inscription : Octobre 2010
    Messages : 31
    Points : 33
    Points
    33
    Par défaut
    Citation Envoyé par pseudocode Voir le message
    Déjà, il faudrait un "return" à la fin du bloc d'affichage de la solution : inutile de continuer l'exploration si on a trouvé une solution.

    Ensuite, c'est quoi tous ces paramètres de la fonction ?
    mais il faut trouver la solution optimale pas n'importe la quelle..., ameliorer c'est en quelque sorte couper les branches qui ont des couts plus importantes qu'un autre d'une solution déjà parcouru...

    je vous remercie pour votre réponse, je vais essayer d'éliminer quelque parametres de ma fonction

  2. #22
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 51
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Points : 16 081
    Points
    16 081
    Par défaut
    Citation Envoyé par Faissall Voir le message
    mais il faut trouver la solution optimale pas n'importe la quelle..., ameliorer c'est en quelque sorte couper les branches qui ont des couts plus importantes qu'un autre d'une solution déjà parcouru...
    Oui, ca j'ai bien compris. Mais si on affiche la solution, c'est qu'on est au bout de la branche actuelle, ca ne sert a rien d'aller plus loin sur cette branche là. D'où le "return" pour arrêter la récursion, et revenir un cran en arrière pour explorer une autre branche.

    je vous remercie pour votre réponse, je vais essayer d'éliminer quelque parametres de ma fonction
    Je voulais juste savoir a quoi servaient ces paramètres.
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  3. #23
    Nouveau membre du Club
    Homme Profil pro
    Inscrit en
    Octobre 2010
    Messages
    31
    Détails du profil
    Informations personnelles :
    Sexe : Homme

    Informations forums :
    Inscription : Octobre 2010
    Messages : 31
    Points : 33
    Points
    33
    Par défaut
    Citation Envoyé par pseudocode Voir le message
    Oui, ca j'ai bien compris. Mais si on affiche la solution, c'est qu'on est au bout de la branche actuelle, ca ne sert a rien d'aller plus loin sur cette branche là. D'où le "return" pour arrêter la récursion, et revenir un cran en arrière pour explorer une autre branche.



    Je voulais juste savoir a quoi servaient ces paramètres.
    voici le code avec quelque commentaires:
    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
    	/* Ctemp : cout temporaire selon les sommets deja parcouru par path
    	 * cheminOpt[] : un tableau contenant les sommets du chemin optimale dans l'ordre
    	 * depth: sommet en cours d'exporation 
    	 * M est la matrice des cout entre sommets
    	 */
     
     
    	public void Branch_Bound(int Ctemp, int cheminOpt[], int position, int depth, int M[][]) 
    	{
    		    path[depth]=position;
     
    			// affiche la solution
    			if((depth==n-1)&&elementDif(path))
    			{
    				for(int i=0;i<=depth;i++)					
    					System.out.print(path[i]+" ");
     
    				int c=calculCout(path, M);
     
    				if(c<mCout)
    				{
    					mCout=c;		//mise à jours du cout optimale
    					Ctemp=c;		//mise à jours du Ctemp pour ne pas parcourir les branches de cout > Ctemp			
    					for(int k=0; k<M.length; k++)
    					cheminOpt[k]=path[k];
    				}					
    				System.out.print("\tc="+c+"\tmCout="+mCout);
    				System.out.println();				
    			}	
     
    		// sinon...
     
    		taboo[position]=true; // on pose un caillou
     
    		// on explore les chemins restants
    		for(int i=0;i<n;i++) 
    		{
    			if (taboo[i]) continue;
    			if(cout(path, M)<Ctemp)
    				Branch_Bound(Ctemp, cheminOpt, i, depth+1, M); 
    		}
     
    	taboo[position]=false; // on retire le caillou
    	}

  4. #24
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 51
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Points : 16 081
    Points
    16 081
    Par défaut
    Il y a une bonne raison pour passer Ctemp, cheminOpt et M en paramètre, plutôt que de les laisser en variable d'instance ?

    Je dis ca parce que ca serait plus simple pour ecrire le code
    Code java : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    // matrice d'adjacence
    int[][] M = new int[][] { /*... */ }
     
    // stockage du chemin pendant l'exploration recursive
    int[] path = new int[n];
     
    // meilleur chemin trouvé
    int[] bestpath = new int[n];
    int bestpathcost = Integer.MAX_VALUE;
     
    // verrou pour la recherche taboo
    boolean[] taboo = new boolean[n];

    Code java : 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
    // exploration recursive avec taboo
    void explore(int position, int depth, int cost) {
    	path[depth]=position;
     
    	// m-a-j du cout total du chemin actuel
    	if (depth>0)
    		cost += M[path[depth-1]][path[depth]];
     
    	// on a dépassé la consigne -> abandon
    	if (cost>bestpathcost) return;
     
    	// on est sur le sommet d'arrivé -> fini
    	if (position==target) {
    		// sauvegarde la nouvelle meilleure solution
    		bestpath=Arrays.copyOf(path, depth+1);
    		bestpathcost=cost;
    		return;
    	}
     
    	// sinon...
    	taboo[position]=true; // on pose un caillou
     
    	//on explore les chemins restants
    	for(int i=0;i<n;i++) {
    		if (M[position][i]==0 || taboo[i]) continue;
    		explore(i,depth+1,cost);
    	}
     
    	taboo[position]=false; // on retire le caillou
    }
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  5. #25
    Nouveau membre du Club
    Homme Profil pro
    Inscrit en
    Octobre 2010
    Messages
    31
    Détails du profil
    Informations personnelles :
    Sexe : Homme

    Informations forums :
    Inscription : Octobre 2010
    Messages : 31
    Points : 33
    Points
    33
    Par défaut
    Citation Envoyé par pseudocode Voir le message
    Il y a une bonne raison pour passer Ctemp, cheminOpt et M en paramètre, plutôt que de les laisser en variable d'instance ?

    Je dis ca parce que ca serait plus simple pour ecrire le code
    Code java : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    // matrice d'adjacence
    int[][] M = new int[][] { /*... */ }
     
    // stockage du chemin pendant l'exploration recursive
    int[] path = new int[n];
     
    // meilleur chemin trouvé
    int[] bestpath = new int[n];
    int bestpathcost = Integer.MAX_VALUE;
     
    // verrou pour la recherche taboo
    boolean[] taboo = new boolean[n];

    Code java : 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
    // exploration recursive avec taboo
    void explore(int position, int depth, int cost) {
    	path[depth]=position;
     
    	// m-a-j du cout total du chemin actuel
    	if (depth>0)
    		cost += M[path[depth-1]][path[depth]];
     
    	// on a dépassé la consigne -> abandon
    	if (cost>bestpathcost) return;
     
    	// on est sur le sommet d'arrivé -> fini
    	if (position==target) {
    		// sauvegarde la nouvelle meilleure solution
    		bestpath=Arrays.copyOf(path, depth+1);
    		bestpathcost=cost;
    		return;
    	}
     
    	// sinon...
    	taboo[position]=true; // on pose un caillou
     
    	//on explore les chemins restants
    	for(int i=0;i<n;i++) {
    		if (M[position][i]==0 || taboo[i]) continue;
    		explore(i,depth+1,cost);
    	}
     
    	taboo[position]=false; // on retire le caillou
    }
    merci beaucoup pour votre explication,
    j'ai essayer d'adapter ceci:
    Code java : 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
     
    public void Branch_Bound(int Ctemp, int cheminOpt[], int position,
     int depth, int M[][]) 
    {
        path[depth]=position;
     
        if (depth>0)
    	Ctemp += M[path[depth-1]][path[depth]]; // m-a-j cout temporaire
     
        // on a dépassé la consigne -> abandon
        if (Ctemp>mCout) return;   //cause du prb=>parcours qu'un chemin
     
         // affiche la solution
         if((depth==M.length-1)&&elementDif(path))
         {
    	for(int i=0;i<=depth;i++)					
                System.out.print(path[i]+" ");
     
                 int c=calculCout(path, M);
     
    	if(c<mCout)
    	{
    	    mCout=c;	//m a j du cout optimale
    	    Ctemp=c; 	//m a j du Ctemp pour parcourir que
    // les branches de cout < Ctemp pour ameliorer la sol			
    	for(int k=0; k<M.length; k++)
    	   cheminOpt[k]=path[k];
             }					
     
             System.out.print("\tc="+c+"\tmCout="+mCout);
    	 System.out.println();				
    	}	
     
    	// sinon...
     
    	taboo[position]=true; // on pose un caillou
     
    	// on explore les chemins restants
    	for(int i=0;i<n;i++) 
    	{
    	   if (taboo[i]) continue;
    		Branch_Bound(Ctemp, cheminOpt, i, depth+1, M); 
    	}
     
    	taboo[position]=false; // on retire le caillou
    }
    [/quote]

    mais comme toujours ça n'affiche que le premier chemin parcouru.
    a propos de:

  6. #26
    Nouveau membre du Club
    Homme Profil pro
    Inscrit en
    Octobre 2010
    Messages
    31
    Détails du profil
    Informations personnelles :
    Sexe : Homme

    Informations forums :
    Inscription : Octobre 2010
    Messages : 31
    Points : 33
    Points
    33
    Par défaut
    Citation Envoyé par Faissall Voir le message
    merci beaucoup pour votre explication,
    j'ai essayer d'adapter ceci:
    Code java : 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
     
    public void Branch_Bound(int Ctemp, int cheminOpt[], int position,
     int depth, int M[][]) 
    {
        path[depth]=position;
     
        if (depth>0)
    	Ctemp += M[path[depth-1]][path[depth]]; // m-a-j cout temporaire
     
        // on a dépassé la consigne -> abandon
        if (Ctemp>mCout) return;   //cause du prb=>parcours qu'un chemin
     
         // affiche la solution
         if((depth==M.length-1)&&elementDif(path))
         {
    	for(int i=0;i<=depth;i++)					
                System.out.print(path[i]+" ");
     
                 int c=calculCout(path, M);
     
    	if(c<mCout)
    	{
    	    mCout=c;	//m a j du cout optimale
    	    Ctemp=c; 	//m a j du Ctemp pour parcourir que
    // les branches de cout < Ctemp pour ameliorer la sol			
    	for(int k=0; k<M.length; k++)
    	   cheminOpt[k]=path[k];
             }					
     
             System.out.print("\tc="+c+"\tmCout="+mCout);
    	 System.out.println();				
    	}	
     
    	// sinon...
     
    	taboo[position]=true; // on pose un caillou
     
    	// on explore les chemins restants
    	for(int i=0;i<n;i++) 
    	{
    	   if (taboo[i]) continue;
    		Branch_Bound(Ctemp, cheminOpt, i, depth+1, M); 
    	}
     
    	taboo[position]=false; // on retire le caillou
    }
    mais comme toujours ça n'affiche que le premier chemin parcouru.
    a propos de:[/QUOTE]

    je voulais juste ajouter que quand je met if (Ctemp>mCout) return; en comentaire, ça marche mais ça n'ameliore pas la recherche...

  7. #27
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 51
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Points : 16 081
    Points
    16 081
    Par défaut
    Citation Envoyé par Faissall Voir le message
    mais comme toujours ça n'affiche que le premier chemin parcouru.
    tu es sûr de ton test " if((depth==M.length-1)&&elementDif(path)) " ?
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  8. #28
    Nouveau membre du Club
    Homme Profil pro
    Inscrit en
    Octobre 2010
    Messages
    31
    Détails du profil
    Informations personnelles :
    Sexe : Homme

    Informations forums :
    Inscription : Octobre 2010
    Messages : 31
    Points : 33
    Points
    33
    Par défaut
    Citation Envoyé par pseudocode Voir le message
    tu es sûr de ton test " if((depth==M.length-1)&&elementDif(path)) " ?
    oui, ça marche bien avec au premier Algo,
    if((depth==M.length-1) si parcours de tout les sommets
    &&elementDif(path)) si les element parcourus sont différents

  9. #29
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 51
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Points : 16 081
    Points
    16 081
    Par défaut
    En tous cas, ca marche avec ma version du post #24. Donc je suppose qu'il y a un problème de ton portage.
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  10. #30
    Nouveau membre du Club
    Homme Profil pro
    Inscrit en
    Octobre 2010
    Messages
    31
    Détails du profil
    Informations personnelles :
    Sexe : Homme

    Informations forums :
    Inscription : Octobre 2010
    Messages : 31
    Points : 33
    Points
    33
    Par défaut
    Citation Envoyé par pseudocode Voir le message
    En tous cas, ca marche avec ma version du post #24. Donc je suppose qu'il y a un problème de ton portage.
    vous l'avez essayé avec une matrice de cout ??!!!

  11. #31
    Nouveau membre du Club
    Homme Profil pro
    Inscrit en
    Octobre 2010
    Messages
    31
    Détails du profil
    Informations personnelles :
    Sexe : Homme

    Informations forums :
    Inscription : Octobre 2010
    Messages : 31
    Points : 33
    Points
    33
    Par défaut
    Citation Envoyé par pseudocode Voir le message
    En tous cas, ca marche avec ma version du post #24. Donc je suppose qu'il y a un problème de ton portage.
    j'ai amélioré mon programme, le parcours de certains chemin marche bien et ameliore comme prévu mais n'arrive pas à la solution optimale ,
    voici mon code si vous avez des remarques et merci beaucoup...
    Code java : 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
     
    public void Branch_Bound(int Ctemp, int cheminOpt[], int position,
     int depth, int M[][]) 
    {
       path[depth]=position;
     
       if (depth>0)
    	Ctemp=calculCout(path, M); // m-a-j cout temporaire
     
     
       // on a dépassé la consigne -> abandon
       if (Ctemp>mCout) return;	
     
       // affiche la solution
       if((depth==n-1))	//&&elementDif(path)
       {
    	for(int i=0;i<=depth;i++)					
    	     System.out.print(path[i]+" ");
     
    	 int c=calculCout(path, M);
     
             if(c<mCout)
    	 {
    	   mCout=c;	//maj du cout optimale
     
    	   for(int k=0; k<M.length; k++)
    	         cheminOpt[k]=path[k];
    	 }					
    	 System.out.print("\tc="+c+"\tmCout="+mCout);
    	 System.out.println();				
             }	
     
    	// sinon...	 
    	taboo[position]=true; // on pose un caillou
     
    	// on explore les chemins restants
    	for(int i=0;i<n;i++) 
    	{
    	    if (taboo[i]) continue;
    		Branch_Bound(Ctemp, cheminOpt, i, depth+1, M); 
    	}
     
    	taboo[position]=false; // on retire le caillou
    }

  12. #32
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 51
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Points : 16 081
    Points
    16 081
    Par défaut
    ca ne sert à rien de recalculer "int c=calculCout(path, M);" car on a déjà la valeur dans Ctemp

    Citation Envoyé par Faissall Voir le message
    le parcours de certains chemin marche bien et ameliore comme prévu mais n'arrive pas à la solution optimale
    Bah là, je ne vois pas comment c'est possible puisqu'on teste toutes les solutions possibles.

    (a moins d'une erreur dans calculCout() ?)
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  13. #33
    Nouveau membre du Club
    Homme Profil pro
    Inscrit en
    Octobre 2010
    Messages
    31
    Détails du profil
    Informations personnelles :
    Sexe : Homme

    Informations forums :
    Inscription : Octobre 2010
    Messages : 31
    Points : 33
    Points
    33
    Par défaut
    Citation Envoyé par pseudocode Voir le message
    ca ne sert à rien de recalculer "int c=calculCout(path, M);" car on a déjà la valeur dans Ctemp



    Bah là, je ne vois pas comment c'est possible puisqu'on teste toutes les solutions possibles.

    (a moins d'une erreur dans calculCout() ?)
    Code java : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
     
     
    public int calculCout(int t[], int M[][])
    {
    	int Cout=0; 
    	for(int i=1; i<t.length; i++)
    		Cout+=M[t[i-1]][t[i]];
    	return Cout;
    }
    c'est la même que j'utilise pour le premier algo_naif et ça marche...
    je crois que c'est "if (Ctemp>mCout) return;" que je dois changer...

  14. #34
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 51
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Points : 16 081
    Points
    16 081
    Par défaut
    Citation Envoyé par Faissall Voir le message
    c'est la même que j'utilise pour le premier algo_naif et ça marche...
    je crois que c'est "if (Ctemp>mCout) return;" que je dois changer...
    C'est surtout que tu ne passes pas "depth" à ta fonction calculCout(), donc tu calcules un cout pour un chemin invalide.

    Code java : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    public int calculCout(int t[], int depth, int M[][])
    {
    	int Cout=0; 
    	for(int i=1; i<=depth; i++)
    		Cout+=M[t[i-1]][t[i]];
    	return Cout;
    }
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  15. #35
    Nouveau membre du Club
    Homme Profil pro
    Inscrit en
    Octobre 2010
    Messages
    31
    Détails du profil
    Informations personnelles :
    Sexe : Homme

    Informations forums :
    Inscription : Octobre 2010
    Messages : 31
    Points : 33
    Points
    33
    Par défaut
    Citation Envoyé par pseudocode Voir le message
    C'est surtout que tu ne passes pas "depth" à ta fonction calculCout(), donc tu calcules un cout pour un chemin invalide.

    Code java : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    public int calculCout(int t[], int depth, int M[][])
    {
    	int Cout=0; 
    	for(int i=1; i<=depth; i++)
    		Cout+=M[t[i-1]][t[i]];
    	return Cout;
    }
    eh ouiiii chef, ça marche bien maintenant, je vous remercie, c'est très gentil

  16. #36
    Nouveau membre du Club
    Homme Profil pro
    Inscrit en
    Octobre 2010
    Messages
    31
    Détails du profil
    Informations personnelles :
    Sexe : Homme

    Informations forums :
    Inscription : Octobre 2010
    Messages : 31
    Points : 33
    Points
    33
    Par défaut Algorithme de Little pour la resolution d'un TSP
    voici un résumé de l'algorithme de Little pour la résolution de TSP:

    soit la matrice des couts entre villes suivante:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
            A       B      C       D       E       F
    A       ∞      0(2)    3       2      13       1
    B       2        ∞      2       8      0(6)    23
    C       3        11     ∞     0(0)    4       0(1)
    D      0(2)     1       0(2)    ∞      7       9
    E       13       5       6      0(2)    ∞       2
    F       16       1       6      0(1)    14      ∞
    1*On soustrait de chaque ligne le plus petit élément et on fait de même pour les colonnes. D’ou une première évaluation minimale de la longueur du chemin : 16 = 13 + 3. (16= somme des min des lignes puis des colonnes ou minorant).

    2*on choisit une arête aléatoirement BE par exemple et on explore la recherche avec une solution partielle de la branche droite contenant BE et une autre gauche ne contenant pas BE.
    la modification de la matrice droite est celle obtenue en modifiant la ligne B par des infinies, et la colonne E par des infinies aussi.
    par contre la matrice de l'exploration gauche consiste à modifier que l'élément BE de la matrice par l'infinie...
    **on refait les étapes 1 et 2 pour chaque noeud de l'arbre d'exploration, et on n'explore que les branches ayant un minorant < a une solution déjà trouvé.

    voici l'implémentation de cet algorithme en Java:
    Code java : 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
     
    public void solveTSP(int M[][], ArrayList<Arete> Sp, int minorant, int Sm)
    {
      minorant+=calculMinorant(M);  
     
      if(Sp.size()==M.length-1)   //condition d'arret
       {
         for(int i=0; i<Sp.size(); i++)   //les solutions trouvées
    	{
    	 System.out.print(Sp.get(i).l+" "+Sp.get(i).c+"\t");			
    	 }
    	 System.out.print("cout="+minorant);
    	 System.out.println();
    	 if(minorant<Sm)
    		Sm=minorant;
        }
     
        ArrayList<Arete> SpD=Sp;	//Solution partielle de l'exploration droite
        ArrayList<Arete>SpG=Sp; 	//... gauche		
     
        int Mr[][]=updateMat(M);	//Mr=M réduite en enlevant le min de 
    //chaque ligne puis des colonne     
     
        t=choixArete(Mr);  
     
       int MD[][]=new int[M.length][M.length];  //matrice d'exploration Droite
       int MG[][]=new int[M.length][M.length];  //matrice d'exploration Guauche
       MD=updateMatLC(t.l, t.c, Mr);      //réduction de la matrice droite
       MG=updateMatCase(t.l, t.c, Mr);	 // m-a-j ... gauche 
       SpD.add(t);	//ajout de l'arete choisie à la solution partielle droite
     
       if(minorant>Sm) return;	//sortir si solution partielle de cout > Sm
     
       solveTSP(MD, SpD, minorant, Sm ); //exploration droite
       solveTSP(MG, SpG, minorant, Sm);  //exploration gauche	
    }
    Problème: ce code ne donne pas la solution optimale
    Question: comment corriger ou améliorer mon programme ??
    toutes vos remarques sont les bienvenues

  17. #37
    Nouveau membre du Club
    Homme Profil pro
    Inscrit en
    Octobre 2010
    Messages
    31
    Détails du profil
    Informations personnelles :
    Sexe : Homme

    Informations forums :
    Inscription : Octobre 2010
    Messages : 31
    Points : 33
    Points
    33
    Par défaut
    Pseudocode vous avez une idée ??

  18. #38
    Membre à l'essai
    Inscrit en
    Octobre 2006
    Messages
    14
    Détails du profil
    Informations forums :
    Inscription : Octobre 2006
    Messages : 14
    Points : 18
    Points
    18
    Par défaut
    Citation Envoyé par pseudocode Voir le message
    Houla... c'est exxxxxtremement compliqué.

    Non, je plaisante. Ca consiste a poser des petits cailloux le long du chemin pour éviter de passer 2 fois au meme endroit. Un petit exemple:

    On modélise le graphe
    Code java : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    // nombre de sommets dans le graphe
    int n=5;
     
    // matrice d'adjacence du graphe 
    int[][] adjacencymatrix = new int[][] {
    	new int[] {1,1,1,0,0}, //    1
    	new int[] {1,1,1,1,0}, //  / | \
    	new int[] {1,1,1,1,0}, // 0  |  3 - 4
    	new int[] {0,1,1,1,1}, //  \ | /
    	new int[] {0,0,0,1,1}, //    2
    };

    On définit les quelques variables utilisées par notre algorithme:
    Code java : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    // stockage du chemin pendant l'exploration recursive
    int[] path = new int[n];
     
    // verrou pour la recherche taboo (tous initialisés à "false" par défaut)
    boolean[] taboo = new boolean[n];
     
    // sommets de départ/arrivé souhaités
    int source=0;
    int target=4;

    Et enfin l'algorithme de parcours recursif:
    Code java : 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
    void explore(int position, int depth) {
    	path[depth]=position;
     
    	// on est sur le sommet d'arrivé -> fini
    	if (position==target) {
    		// affiche la solution
    		for(int i=0;i<=depth;i++) System.out.print(path[i]+" ");
    		System.out.print("\n");
    		return;
    	}
     
    	// sinon...
     
    	taboo[position]=true; // on pose un caillou
     
    	// on explore les chemins restants
    	for(int i=0;i<n;i++) {
    		if (adjacencymatrix[position][i]==0 || taboo[i]) continue;
    		explore(i,depth+1);
    	}
     
    	taboo[position]=false; // on retire le caillou
    }

    on appelle l'algorithme avec "explore(source,0);" pour lui dire de commencer à explorer à partir du noeud 'source'. Ce qui nous donne les 4 chemins possibles entre les sommets "0" et "4":

    0 1 2 3 4
    0 1 3 4
    0 2 1 3 4
    0 2 3 4
    bonjour
    le code est bien écrit sauf que je voudrai savoir si on peux mettre une condition d’arrêt pour avoir le premier chemin ou même si on stock chaque chemin à part (dans un tableau de chemins par exemple);

  19. #39
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 51
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Points : 16 081
    Points
    16 081
    Par défaut
    Citation Envoyé par marwa_rades Voir le message
    bonjour
    le code est bien écrit sauf que je voudrai savoir si on peux mettre une condition d’arrêt pour avoir le premier chemin ou même si on stock chaque chemin à part (dans un tableau de chemins par exemple);
    Oui. On peut.
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  20. #40
    Membre à l'essai
    Inscrit en
    Octobre 2006
    Messages
    14
    Détails du profil
    Informations forums :
    Inscription : Octobre 2006
    Messages : 14
    Points : 18
    Points
    18
    Par défaut
    bonjour
    j'ai implémenté le code en c# et je l'utilisais pour afficher le premier chemin,tous les chemin et le chemin le plus cours et tt va bien sauf que si je l'utilise pour un grand nombre de données le programme prend trrrrrrrrrrop de temps et même parfois il ne donne pas de réponse quelqu’un a une idée?

+ Répondre à la discussion
Cette discussion est résolue.
Page 2 sur 3 PremièrePremière 123 DernièreDernière

Discussions similaires

  1. Tous les chemins d'un graphe
    Par Raikyn dans le forum Algorithmes et structures de données
    Réponses: 8
    Dernier message: 05/12/2013, 15h33
  2. tous les chemins dans un graphe
    Par tunnour dans le forum Mathématiques
    Réponses: 3
    Dernier message: 29/12/2009, 17h48
  3. Parcours d'un arbre : examiner tous les chemins possibles
    Par Molos dans le forum Algorithmes et structures de données
    Réponses: 6
    Dernier message: 06/04/2009, 18h22
  4. graphe orienté : parcours de tous les noeuds
    Par Lily_ dans le forum Algorithmes et structures de données
    Réponses: 3
    Dernier message: 03/10/2007, 12h48
  5. [Graphe] Extraire tous les chemins de toutes tailles.
    Par Choupi dans le forum Algorithmes et structures de données
    Réponses: 2
    Dernier message: 10/05/2006, 16h47

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