Discussion :

[nir63]

bonjour tous le monde.

svp, j'ai besoin de votre aide pour programme le chemin minimum dans une 6 période et 6 de demande.

voila une image qui explique un peu le probleme



et V(i,l) est un tableau de double dimension,

je veux faire un programme qui commence à savoir le chemin minimun sachant que le début sera de periode 6 et demande 4 V(6,4).

svp vraiment j'ai besoin de votre aide pour programme le chemin minimum!!!!????

j'ai un progamme de calculer de V(i,l) je ne sais pas si je dois le poser??

[wax78]

Dijkstra ne serait pas une bonne idée ? http://fr.wikipedia.org/wiki/Algorithme_de_Dijkstra

[nir63]

je en sais pas si il va me donner une meilleur résultat

[wax78]

Un meilleur résultat que quoi ? Tu ne dis pas ce que tu utilises comme algorithme et en plus tu ne donnes pas de code en exemple donc difficile à dire.

[nir63]

moi meme, je ne sais pas ce que je dois utilisé comme un algorithme Dijkstra ou Bellman.??????

la déférence entre eux, c'est que algorithme Dijkstra est un algorithme de passé vers future, par contre Bellman de future vers le passé.

voiala le code

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
public static void main(String[] args) {
 
          int CoutStockage[]  = {0, 0, 0, 2, 3, 5, 7};                                       
          int Demandei[]  = {0, 9, 17, 14, 18, 11, 17};                                 
          int CoutFabrication[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 20, 22, 25, 30, 33, 37, 40};    
          int p = 6;         
          int Xmax=16;      
          int Xmin=10;       
          int Sinit=3;       
          int Smin=3;        
          int Smax=6; 
          int Resultat[][] = new int[p+1][Smax+1];
          int Kmin = 0, Kmax = 0;    
          int M, N, C;
 
             // periode 1 à faire 
             for (int i=1;i<2;i++){
            	 System.out.println("\n periode : "+i);
                  //Pour l de SMin à SMax faire 
                  for (int l=Smin;l<=Smax;l++){
                	  System.out.println("\n   l de : "+l);
                          M =  Demandei[i]+l-Xmax;
                          N =  Demandei[i]+l-Xmin;
 
                      // Calculer Kmax    
                      if(M > Sinit){ 
                    	  System.out.println("\n     Kmin est : "+M);
                      }
                      else {
                           Kmin = Sinit; 
                           System.out.println("\n     Kmin est : "+Kmin);
                      }
                      // Calculer Kmin      
                      if(N < Sinit){ 
                    	  System.out.println("\n     Kmax est : "+N);
                      }
                      else {
                            Kmax = Sinit;
                            System.out.println("\n     Kmax est : "+Kmax);
                      }
                      // Calculer le cout de mois
                      if(Kmax < Kmin){
                              System.out.println("\n\tCout(V"+(+i+","+l)+ ") = +1000 ");//Ce cout ne peut pas etre calculer, Il est jusqu'à l'infinis
                      }
                          else if(Kmax > Kmin){
                                  System.out.println("\n\tCout(V"+(+i+","+l)+ ") = +1000");
                          }                  
                              else{
                                      C = CoutStockage[l]+CoutFabrication[l+Demandei[i]-Sinit];
                                       Resultat[i][l] = C;
                                      System.out.println("\n\tCout(V"+(+i+","+l)+ ") = "+Resultat[i][l]) ;
                              }
                  }
             }
 
             // Pour i = 2 à P faire :
             for (int i=2;i<=p;i++){
            	 System.out.println("\n periode : "+i);
                  //Pour l de SMin à SMax faire 
                  for (int l=Smin;l<=Smax;l++){
                	  System.out.println("\n   l de : "+l);
                          M =  Demandei[i]+l-Xmax;
                          N =  Demandei[i]+l-Xmin;
 
	                      if(M > Smin){ 
	                      	  Kmin=M;
	                       	  System.out.println("\n     Kmin est : "+M);
	                      }
	                      else {
	                          Kmin = Smin; 
	                          System.out.println("\n     Kmin est : "+Kmin);
	                      }
	                      // Calculer Kmax      
	                      if(N < Smax){ 
	                       	  Kmax=N;
	                       	  System.out.println("\n     Kmax est :  "+N);
	                      }
	                      else {
	                          Kmax = Smax;
	                          System.out.println("\n     Kmax est : "+Kmax);
	                      }
 
 
	                      if(Kmax > Kmin){
	                      // Pour k de Kmin à Kmax faire :
	                    	  int minc=-1;
	                    	  for(int k =Kmin; k<=Kmax;k++){
	                    		  if (Resultat[i-1][k]== 0){
	                    			  System.out.println("\n\tCout(V"+(+i+","+k)+ ") = +1000 ");
	                    		  }
	                    		  else{
		                    		  C = CoutStockage[l]+CoutFabrication[l+Demandei[i]-k] + Resultat[i-1][k];
			                    		  if ( minc==-1 || C<minc) {
			                    		        minc=C;
			                    		   }
		                    		  Resultat[i][l] = C;
		                    		  int Xi= l+Demandei[i]-k;
		                    	      System.out.println("\n\tCout(V"+(+i+","+k)+ ") = "+Resultat[i][l]
		                    	  	   +" = "+ CoutStockage[l]+" + "+CoutFabrication[l+Demandei[i]-k]+" + "+Resultat[i-1][k]) ;
		                    	      //System.out.println("\n\tLe Xi = "+Xi);
			                    	      if (minc!=-1) {
			                    	    	   Resultat[i][l] = minc;
			                    	      }
			                     }
 
	                    	  }
	                    	  System.out.println("\n\tLe Cout(V"+(+i+","+l)+ ") = "+Resultat[i][l]);
	                      }  
                          else if(Kmax == Kmin){
                        	  for(int k =Kmin; k<=Kmax;k++){
                        		  int Xi= l+Demandei[i]-k;
    	                    	  C = CoutStockage[l] + CoutFabrication[l+Demandei[i]-k] + Resultat[i-1][k] ;
    	                    	  Resultat[i][l] = C;
    	                    	  System.out.println("\n\tCout(V"+(+i+","+k)+ ") = "+Resultat[i][l]
                                  	+" = "+ CoutStockage[l]+" + "+CoutFabrication[l+Demandei[i]-k]+" + "+Resultat[i-1][k]);
    	                    	  //System.out.println("\n\tLe Xi = "+Xi);
    	                    	  System.out.println("\n\tLe Cout(V"+(+i+","+l)+ ") = "+Resultat[i][l]);
                        	  }
                          }                  
                              else{
                                      System.out.println("\n\tCout(V"+(+i+","+l)+ ") = +1000 ");
 
                              }
                  }
             }

[wax78]

Ok, peut être que la première étapes serait de demander l'avis des algorithmiciens (sur le fourm) afin de voir selon ton problème quel serait le meilleur a choisir. Et ensuite tu pourras revenir, sauf si une personne qui connaitrait la reponse passerais par ici.

[dinobogan]

Tout dépend du volume de données.
L'algorithme de Dijkstra te donnera toujours le chemin le plus court.
Mais si tu n'as que très peu de données, tu peux utiliser un algorithme systématique qui va parcourir toutes les combinaisons jusqu'à trouver le plus court chemin.
Mais tu donnes tellement peu d'info que je ne peux pas t'en dire plus.

[Nico02]

Bon mes cours d'algo sont loin mais si je dis pas de bêtise, Dijkstra s'applique uniquement sur un graphe non orienté à l'inverse de Bellmond-Ford (après on peu toujours transformer un graphe non orienté). Donc un premier point à prendre en compte.

Après je crois pas qu'on puisse dire qu'un algoest "mieux" qu'un autre, chacun à ces particularités et s'applique plus ou moins bien selon le contexte dans lequel on s'en sert. Par exemple Dijkstra est très gourmand sur de gros graphe mais te sors toujorus la bonne réponse.

Mais vu que je comprends pas très bien tes besoin je n'engagerai aucune réponse

Sion y'a A* aussi qui existe pour le plus cours chemin.

[nir63]

c'est tous les informations que j'ai, dans le premier message j'ai poster une solution de mon programme (le tableau).

notre profs n'as pas dit quelle type d’algorithme quand dois utilisé

[nir63]

Nico02
mes besoins est tres claire dans le premier message, bon voila la solution de mon programme

je cherche l’algorithme et même pour programmer le plus chemin court qui est en couleur rouge.
pour le type d'algorithme que je dois utilisé , aucun aidé

[thelvin]

J'ignore ce qui te fait penser qu'il y a quoi que ce soit de clair là-dedans. Pour une recherche de chemin il faut un graphe. Un graphe c'est un ensemble d'états et un ensemble de transitions entre deux états. Il n'y a rien de ce genre ici.

En tout cas, répéter la même chose est inutile.

[bretus]

Bon mes cours d'algo sont loin mais si je dis pas de bêtise, Dijkstra s'applique uniquement sur un graphe non orienté à l'inverse de Bellmond-Ford (après on peu toujours transformer un graphe non orienté). Donc un premier point à prendre en compte.

Dijkstra s'applique sur un graphe orienté ou non orienté pour trouver le plus court chemin allant d'un sommet A à un sommet B (quand on visite un sommet, on peut parcourir seulement les arcs sortants dans le cas d'un graphe orienté ou affecter un poid différent pour le parcours : cost, reverse_cost)

Bellman-Ford s'applique quand à lui au cas où les poids des arcs sont négatifs (en gros, tu remontent le temps en parcourant un arc dans un calcul d'itinéraire : C'est pas courant).

Voir ici : http://pcaboche.developpez.com/artic...s/?page=page_2

Après je crois pas qu'on puisse dire qu'un algoest "mieux" qu'un autre, chacun à ces particularités et s'applique plus ou moins bien selon le contexte dans lequel on s'en sert.

Juste remarque. Après, Disjtra est souvent la base pour la recherche d'un plus court chemin dans un graphe entre un sommet A et un sommet B.

A* est une heuristique de Disjtra (au niveau du choix du prochain sommet atteint à visiter) où on s'appuie sur une notion de distance entre les sommets pour ne pas trop s'éloigner de la cible (grosso modo, avec Dijstra, on fait un parcours concentrique)

PS : Sur le schéma, je n'arrive pas à voir ce qui est modélisé sous forme d'un sommet et ce qui est modélisé sous forme d'un arc (En gros, qu'est-ce qui fait qu'on a le droit de passer de droite à gauche et vis versa?). Il n'y a que les arcs du plus court chemin. J'ai vaguement l'impression qu'il suffit de trouver la valeur minimum dans le "bloc cible" et qu'il n'est même pas nécessaire de faire appel à la notion de graphe.

[nir63]

mercii pour ta réponse, je veux savoir de mon cas, quelle type d'algorithme que je dois utilisé ??

[nir63]

voila une autre solution sachant que le graphe est le cout, et pour les valeur des arcs sont xi



d’après mais recherché j'ai vu que je dois utilisé algorithme de Belman sachant que il permet de commencer de fin jusqu'à le début, mais j'ai besoin de votre aide pour adapter l'algorithme à mon problème.

[dinobogan]

On est de bonne volonté pour t'aider mais on te demande d'expliquer clairement ce qui te pose problème, et surtout quelles sont les données en entrées et ce que tu cherches à obtenir.
De ton côté, tu es persuadé que nous avons assez d'informations pour te répondre et tu t'obstines à poser toujours la même question.
Sachant que personne ici ne possède de boule de cristal pour deviner ton problème, seul toi peux débloquer la discussion.

[Invité]

Salut,

ça n'a rien à voir avec le calcul d'un chemin optimal puisque le "chemin" que tu sembles chercher est imposé par la valeur de départ choisie.

C'est dû au fait que les V(i,l) sont tous distincts 2 à 2 et que l'ensemble des V(i-1,k) est toujours sous-ensemble des V(i-1,l) :

V(6,4) -> V(5,5)
V(5,5) -> V(4,3)
V(4,3) -> V(3,5)
V(3,5) -> V(2,3)
V(2,3) -> V(1,4)
V(1,4) -> V(0,3)

donc à chaque pas de ton algorithme, le V(i,l) est unique...

La donne serait différente si tu avais plusieurs valeurs de V(5,5), V(4,3), V(3,5), etc dans ta colonne de gauche. Là, oui, ça commencerait à ressembler à la recherche d'un chemin optimum.

En résumé, chemin optimum impose choix du chemin, ce qui n'est pas le cas apparemment dans ton problème (enfin, tel qu'il est expliqué).

Ca ressemble plus à un exercice sur le stockage de données à multi-dimensions.

Steph

[nir63]

IP_Steph

oui c'est ça, c'est un stockage de données à multi-dimensions.

sachant que pour chaque ligne est un minimum de entre 3 ou 4 période

mon problème est un problème de dimensionnement de lot.

dans un 6 période, on doit aboutir à un stock de 4 en fin de période 6.

mon tableau ici résumer le stockage des produit dans un 6 période et 4 demande
sachant que i est le période et pour l le demande

pour les plusieurs valeurs de V(5,5), V(4,3), V(3,5), oui j'ai des plusieurs valeurs de tous les ligne, mais dans le tableau, on a choisi le minimum pour faciliter la simplification, même pour que le chemin minimum soit plus simple à trouver.

[Invité]

Corrige tes texte dans un français correcte, peut-être qu'après quelqu'un comprendra ton problème.