Algo du facteur en JAVA

Algo du facteur en JAVA - Java - Programmation

Marsh Posté le 30-12-2005 à 16:09:49    

Voila, j'ai un exo a faire en java, il s'agit d'un facteur qui peut porter au max 5 kg, mais on ne sait pas combien de colis il y a à l'avance, le but du jeu est de tranporter le maximum de colis sans dépasser 5 KG et en meme temps limiter le nombres de voyages.
 
Si vous connaissez de la doc, un tut, code etc... cela me serait d'une grande utilité vu que je galere pas mal depuis pas mal de tps dessus :(
 
Merci d'avance !

Reply

Marsh Posté le 30-12-2005 à 16:09:49   

Reply

Marsh Posté le 30-12-2005 à 16:28:02    

s'il ne sait pas ce qu'il doit transporter, ca va être dur ...

Reply

Marsh Posté le 30-12-2005 à 17:14:18    

non mais ce que je veux dire c'est que par exemple il y a on va dire 150 colis, qui varient entre 10g et 4,5kg, et il faut faire le moins de trajet.
Ce que j'entendais par 'il ne sait pas ce qu'il doit transporter' c'etait plus a realiser avec n colis.
Voila, j'espere avoir ete clair cette fois ;)

Reply

Marsh Posté le 30-12-2005 à 17:42:48    

Essaye toutes les combinaisons possibles puis, si le facteur est toujours en vie, abats-le.
 
Bon, c'est bien amusant tout ça, mais tu t'es renseigné sur l'algo tout court, en dehors de Java ? Une fois que tu auras la partition, ce sera pas trop dur de la mettre en musique.
 
Que proposes-tu ?
 
[:petrus75]


Message édité par sircam le 30-12-2005 à 17:43:04

---------------
Now Playing: {SYNTAX ERROR AT LINE 1210}
Reply

Marsh Posté le 30-12-2005 à 18:36:26    

hummm ouais j'ai essayé de cherché en dehors du java, je cherche un algo  generique marchant avec n'importe quel langage...Mais bon je ne trouve pas :(
Niveau musique, attention je suis naze en composition :D

Reply

Marsh Posté le 31-12-2005 à 02:19:54    


C'est un dérivé d'un problème très connu en algorithmique qu'on appelle "problème du sac à dos". Ce problème appartient à la classe NP, c'est à dire qu'il n'existe aucun algorithme efficace permettant de la calculer.
 
En gros, t'emmerde meme pas à essayer de trouver des ptites techniques de shaolin pour arriver au bon résultat rapidement, ça ne servira à rien, laisse ça à ceux qui ont bac +8. La seule manière de faire, c'est de tester toutes les solutions et de choisir celle qui est la meilleure.
 
Imagine que t'as 3 objets A, B et C:
tu dois tester tout les cas suivants
A B C
A C B
B A C
B C A
C A B
C B A
et prendre le meilleur cas.
Donc tu dois reflechir à "comment tester tout les cas ?" et "comment connaitre le nombre de voyage d'un cas précis?" et aussi "comment prendre le plus petit de tout les cas?" (le dernier est pas trop dur)
 
Si t'as des questions n'hésite pas.

Reply

Marsh Posté le 31-12-2005 à 02:27:21    

bah je vais te dire oui meme si ta reponse me parait claire, mais je voulais savoir que pour cet exemple tu as pris 3 objets, mais imagine que tu en a n, tu fais ca comment ?
tu vas pas faire un truc du style :
A B C...N
N..B..C..A..
...
si ? Auquel cas ca sera lent comme algo ?
 
Merci de ta reponse

Reply

Marsh Posté le 31-12-2005 à 02:30:02    

oui ca sera "lent" mais t'as pas le choix [:spamafote]


---------------
Me: Django Localization, Yogo Puzzle, Chrome Grapher, C++ Signals, Brainf*ck.
Reply

Marsh Posté le 31-12-2005 à 03:19:10    

y'a eu une solution plus élégante postée à ce sujet ... une recherche sur sac à dos devrait donner le bon résultat :o

Reply

Marsh Posté le 31-12-2005 à 14:32:36    


Le problème du sac à dos avec des valeurs entières peut etre résolu de manière efficace (en utilisant la programmation dynamique), c'est vrai, mais ici les valeurs ne sont pas entières, le poids peut prendre n'importe quelle valeur réelle, on est bien face à la version Non Polynomiale du problème.
 
Voilà un algo récursif qui permet de le résoudre.
 
La procédure récursive Calcul(i,u) a pour paramètres d'appel, i l'objet pour lequel on doit prendre une décision, et u la capacité disponible restante. Elle considère deux possibilités pour l'objet i l'une pour laquelle il est mis dans le sac (si on ne dépasse pas la capacité restante u), l'autre pour laquelle il n'y est pas mis. La procédure appelle Calcul(i+1, u) et Calcul(i+1, u - p[i]). Ainsi le premier appel de calcul(i, u) est fait avec i = 0 et u égal à la capacité M du sac, les appels successifs feront ensuite augmenter i (et diminuer u) jusqu'à atteindre la valeur n. Le résultat est mémorisé s'il améliore la valeur courante de meilleur.
 
procedure Calcul (i: integer; u: real);
    begin
    if i > n then
        if u < meilleur then
            begin
            for j:= 1 to n do msac[i] := sac[i];
            meilleur := u;
            end;
    else
        begin
        if  p[i] <= u then
            begin
            sac[i] := 1;
            Calcul(i + 1, u - p[i]);
            end;
        sac[i] := 0;
        Calcul(i + 1, u);
        end;
    end;
 
On vérifie sur des exemples que cette procédure donne des résultats assez rapidement pour n < 20. Pour des valeurs plus grandes le temps mis est bien plus long car il croît comme 2 puissance n.  
 
extrait de :http://www.enseignement.polytechnique.fr/profs/informatique/Jean-Jacques.Levy/poly/main8/node8.html
 
Je rappelle que le problème du sac à dos consiste à essayer de remplir au maximum un sac de taille u, avec des objets de taille p[i]. Le probleme du facteur consiste donc à faire le problème du sac à dos plusieurs fois jusqu'à ce qu'on est plus d'objets.

Reply

Marsh Posté le 31-12-2005 à 14:32:36   

Reply

Marsh Posté le 31-12-2005 à 15:31:31    

http://www.edm2.com/0601/backpack.html
Algo rapide pour le backpack problem.

Reply

Marsh Posté le 31-12-2005 à 16:21:34    


Ouais...
Je suis pas sur qu'un programme en C de 500 lignes bourré d'optimisations soit la bonne solution pour un petit exo à faire en java...

Reply

Marsh Posté le 31-12-2005 à 16:57:24    

amnesiks a écrit :

Ouais...
Je suis pas sur qu'un programme en C de 500 lignes bourré d'optimisations soit la bonne solution pour un petit exo à faire en java...


Ce ne sont "que" des exemples servant à illustrer la progression de l'idée et de l'algo hein :sweat:  
 
Rien n'empêche de suivre la pensée pour réimplémenter la chose en java, ou en Ruby, ou en Lisp [:spamafote]

Reply

Marsh Posté le 03-01-2006 à 11:55:03    

drapeau


---------------
TReVoR - http://dev.arqendra.net - http://info.arqendra.net
Reply

Marsh Posté le 14-01-2006 à 03:02:16    

amnesiks a écrit :

procedure Calcul (i: integer; u: real);
    begin
    if i > n then
        if u < meilleur then
            begin
            for j:= 1 to n do msac[i] := sac[i];
            meilleur := u;
            end;
    else
        begin
        if  p[i] <= u then
            begin
            sac[i] := 1;
            Calcul(i + 1, u - p[i]);
            end;
        sac[i] := 0;
        Calcul(i + 1, u);
        end;
    end;
 
extrait de http://www.enseignement.polytechni [...] node8.html


 
j'ai implémenté cet algo en java, ca marche sans pb. en revanche il y a une petite erreur (elle est aussi sur la page donnée en lien). le vrai algo est le suivant:

Code :
  1. procedure Calcul (i: integer; u: real);
  2.     begin
  3.     if i > n then
  4.         if u < meilleur then
  5.             begin
  6.             for j:= 1 to n do msac[j] := sac[j];   // <-- erreur: ici 'j' et pas 'i'
  7.             meilleur := u;
  8.             end;
  9.     else
  10.         begin
  11.         if  p[i] <= u then
  12.             begin
  13.             sac[i] := 1;
  14.             Calcul(i + 1, u - p[i]);
  15.             end;
  16.         sac[i] := 0;
  17.         Calcul(i + 1, u);
  18.         end;
  19.     end;


 
en revanche, aussi bien sur ce site que sur d'autres que j'ai parcouru par rapport à cet algo "backpack" il est dit que

Citation :

Le problème du sac à dos, lorsque la capacité du sac n'est pas un entier, est un exemple typique classique de problème (NP-complet) pour lequel aucun algorithme efficace n'est connu et où il faut explorer toutes les possibilités pour obtenir la meilleure solution


 
dans mon cas, la capacité du sac (u dans l'algo précédent) est un entier, et pas réel. je comprends donc, d'après l'assertion précédente, que le backpack est alors solutionnable sans avoir à tester toutes les possibilités
 
j'ai cherché un peu mais sans trop de résultats. est-ce que qqun aurait des infos à ce sujet ?
 
merci d'avance

Message cité 1 fois
Message édité par trevor le 14-01-2006 à 03:04:30

---------------
TReVoR - http://dev.arqendra.net - http://info.arqendra.net
Reply

Marsh Posté le 21-01-2006 à 12:28:32    

on pourrait pas utiliser l'algo du simplexe ici ?
(remarque peut etre très conne, j'suis une burne en math mais je me rappelle avoir fait ce genre d'exo en cours d'optimisation quand j'étais encore étudiant)

Reply

Marsh Posté le 27-01-2006 à 14:59:01    

trevor a écrit :


dans mon cas, la capacité du sac (u dans l'algo précédent) est un entier, et pas réel. je comprends donc, d'après l'assertion précédente, que le backpack est alors solutionnable sans avoir à tester toutes les possibilités


 
Il me semble que pour pouvoir résoudre le problème sans tester toutes les possibiltés, il faut que la capacité du sac ET le poids des objets soient des entiers.

Reply

Marsh Posté le 27-01-2006 à 20:00:05    

amnesiks a écrit :

Il me semble que pour pouvoir résoudre le problème sans tester toutes les possibiltés, il faut que la capacité du sac ET le poids des objets soient des entiers.


 
c'est le cas :D
bon, ca ne me donne pas plus d'infos sur cet aspect-là... à moins que du coup, l'algo porte un autre nom que "backpack". pas trop eu le temps de chercher ces 2 dernieres semaines. mais faut que je m'y remette :)


---------------
TReVoR - http://dev.arqendra.net - http://info.arqendra.net
Reply

Marsh Posté le 28-01-2006 à 15:19:19    

Alors dans ce cas oui, tu peux utiliser un solution avec programmation dynamique qui est bien plus rapide que l'algo qui explore toutes les possibilités.


Message édité par amnesiks le 28-01-2006 à 15:20:22
Reply

Marsh Posté le 28-01-2006 à 15:37:28    

oki. merci pour le conseil :) il me semblait bien que je pouvais utiliser cette méthode. me reste à trouver suffisamment de documentation et à l'implémenter.
aurais-tu qqes liens par hasard stp ?


---------------
TReVoR - http://dev.arqendra.net - http://info.arqendra.net
Reply

Marsh Posté le 28-01-2006 à 17:41:02    


J'ai pas d'algo tout fait sous la main.
Tape "programmation dynamique sac dos" dans google, y'a le cours de mon prof d'info Mr Robson et d'autres liens qui en parlent et qui peuvent t'aider.

Reply

Marsh Posté le 30-01-2006 à 07:07:47    

ok. merci pour le "tip" ! :)


---------------
TReVoR - http://dev.arqendra.net - http://info.arqendra.net
Reply

Marsh Posté le    

Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed