Forum |  HardWare.fr | News | Articles | PC | S'identifier | S'inscrire | Shop Recherche
2024 connectés 

  FORUM HardWare.fr
  Programmation
  Java

  Algo du facteur en JAVA

 



 Mot :   Pseudo :  
 
Bas de page
Auteur Sujet :

Algo du facteur en JAVA

n°1274998
krovomi
Posté le 30-12-2005 à 16:09:49  profilanswer
 

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 !

mood
Publicité
Posté le 30-12-2005 à 16:09:49  profilanswer
 

n°1275004
theshockwa​ve
I work at a firm named Koslow
Posté le 30-12-2005 à 16:28:02  profilanswer
 

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

n°1275021
krovomi
Posté le 30-12-2005 à 17:14:18  profilanswer
 

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 ;)

n°1275038
sircam
I Like Trains
Posté le 30-12-2005 à 17:42:48  profilanswer
 

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}
n°1275092
krovomi
Posté le 30-12-2005 à 18:36:26  profilanswer
 

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

n°1275219
amnesiks
Posté le 31-12-2005 à 02:19:54  profilanswer
 


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.

n°1275221
krovomi
Posté le 31-12-2005 à 02:27:21  profilanswer
 

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

n°1275222
0x90
Posté le 31-12-2005 à 02:30:02  profilanswer
 

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


---------------
Me: Django Localization, Yogo Puzzle, Chrome Grapher, C++ Signals, Brainf*ck.
n°1275227
theshockwa​ve
I work at a firm named Koslow
Posté le 31-12-2005 à 03:19:10  profilanswer
 

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

n°1275308
amnesiks
Posté le 31-12-2005 à 14:32:36  profilanswer
 


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.

mood
Publicité
Posté le 31-12-2005 à 14:32:36  profilanswer
 

n°1275341
masklinn
í dag viðrar vel til loftárása
Posté le 31-12-2005 à 15:31:31  profilanswer
 

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

n°1275370
amnesiks
Posté le 31-12-2005 à 16:21:34  profilanswer
 


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...

n°1275383
masklinn
í dag viðrar vel til loftárása
Posté le 31-12-2005 à 16:57:24  profilanswer
 

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]

n°1276267
trevor
laissez la vie vous étonner...
Posté le 03-01-2006 à 11:55:03  profilanswer
 

drapeau


---------------
TReVoR - http://dev.arqendra.net - http://info.arqendra.net
n°1283466
trevor
laissez la vie vous étonner...
Posté le 14-01-2006 à 03:02:16  profilanswer
 

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
n°1288854
sebi
Posté le 21-01-2006 à 12:28:32  profilanswer
 

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)

n°1293448
amnesiks
Posté le 27-01-2006 à 14:59:01  profilanswer
 

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.

n°1293759
trevor
laissez la vie vous étonner...
Posté le 27-01-2006 à 20:00:05  profilanswer
 

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
n°1294005
amnesiks
Posté le 28-01-2006 à 15:19:19  profilanswer
 

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
n°1294010
trevor
laissez la vie vous étonner...
Posté le 28-01-2006 à 15:37:28  profilanswer
 

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
n°1294038
amnesiks
Posté le 28-01-2006 à 17:41:02  profilanswer
 


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.

n°1294410
trevor
laissez la vie vous étonner...
Posté le 30-01-2006 à 07:07:47  profilanswer
 

ok. merci pour le "tip" ! :)


---------------
TReVoR - http://dev.arqendra.net - http://info.arqendra.net
mood
Publicité
Posté le   profilanswer
 


Aller à :
Ajouter une réponse
  FORUM HardWare.fr
  Programmation
  Java

  Algo du facteur en JAVA

 

Sujets relatifs
Problème Java Utilisation[JAVA] Migration d'une applet vers un logiciel
[Java][VBA] Java ou VBA pour cet usage ?pb applet java + firefox
[Java] bdd HSQL : impossible de créer une connexion (RESOLU)[Java] héritage abstract
[java] exécuter une appli java en tache de fond ou service.eregi ou preg contre un script java "resize pop up"
[Java] avis sur ce procédé de remplacement de suspend() / resume()koi installé j2se ? pb de java sous firefox suite à l'install de j2se
Plus de sujets relatifs à : Algo du facteur en JAVA


Copyright © 1997-2018 Hardware.fr SARL (Signaler un contenu illicite / Données personnelles) / Groupe LDLC / Shop HFR