Discussion :

[IMPRO]

Bonsoir,
j'ai fait un programme qui résout le problème de voyageur de commerce( le problème consiste, à partir d'une matrice qui contient des villes ainsi la distance entre ces villes, de trouver le meilleur chemin ( le plus court) à emprunter pour parcourir toutes les ville ), qui est un problème assez connu en recherche opérationnelle. ce programme suit un algorithme de recherche profondeur, je sais que ce c'est un peu flou ce que je viens de dire pour les gens qui connaissent pas ce problème, mais je vais exposer mon problème en exposant le fonctionnement de mon programme.
à partir de ma matrice j'extrais une ville et j'enregistre dans un objet toute les ville voisines (qu'on peut acceder à partir de cette ville) sous forme de liste (ArrayList) anis d'autre parametre comme le nom de la ville, une liste des villes parcouru jusqu'à cette ville,... Puis j'empile dans une PILE(Stack). Après je dépile un voisin et je fait la même chose pour le voisin (enregistrer ces voisins,... et je l'empile) jusqu'à ce qu'une ville n'aurait pas de voisin. et ainsi de suite.
quand j'ai par exemple moins de 15 villes dans ma matrice sa marche nickel, mais au de-las je reçois des messages d'erreurs différents mais la même exception.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

Exception in thread "AWT-EventQueue-0" java.lang.OutOfMemoryError: GC overhead limit exceeded

ou bien une exception

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

Java Heap space

est ce que quelqu'un peut m'expliquer la raison de cette erreur, et comment faire des teste mémoire (avoir l'état de la mémoire à un instant donnée), et c'est qoui GC overhead et Java heap space
merci pour votre aide.

[hwoarang]

Comme tu dois le savoir, en java, la memoire est gérée par la machine virtuelle. Ainsi, tu n'as qu'a créer des objets et lorsqu'ils ne sont plus utilisés, le garbage collector (GC) libere la mémoire qui leur etait allouée. Cela se fait dans un thread qui tourne en parallele avec l'appli.
L'exception "GC overhead limit exceeded" arrive quand le JVM passe trop de temps à libérer de la mémoire et pas assez dans le programme.
Pour eviter cette exception, tu peux ajouter -XX:-UseGCOverheadLimit dans la ligne de commande. Cela dit, ca ne changera rien au fait que tu passes beaucoup de temps à libérer de la mémoire et pas beaucoup à executer le programme.

L'exception "Java Heap space" arrive quand tu n'as plus de mémoire disponible. Il peut y avoir 2 raisons :
1 - Tu as une boucle infinie qui consomme de la mémoire (typiquement, un while infini ou tu ajoutes un objet dans une arraylist)
2 - Trop de consommation mémoire

Dans ton cas, la solution 2 semble plus probable. Il y a 2 solutions :
- Optimiser le programme pour consommer moins de mémoire
- Augmenter la mémoire disponible en ajoutant -Xmx1024M à la ligne de commande.

En ce qui concerne les outils de debug, ils dependent de ton IDE...

[JoeChip]

Si mes souvenirs sont exact, il s'agit d'un problème NP-complet, donc, par définition, le besoin de ressources est en relation exponentielle avec le nombre de noeuds. Donc forcément, le maximum de noeuds que tu pourras calculer est très bas. Là, en plus, si j'ai bien suivi, tu utilises un algo récursif, or les algos récursifs sont notoirement gourmands en mémoire...

Moralité : tu vas peut-être réussir à finalement calculer la solution pour 15 villes, peut-être même 16 ou 17, mais tu auras du mal à aller bien au-delà... Les seuls algos opérationnels pour un grand nombre de villes sont heuristiques, par exemple la méthode des fourmis.

[Mako 5013]

J'ai déjà eu à traiter ce problème en cours, et je rejoins totalement BenWillard. Un total de 15 villes est déjà un beau score (il faut tout de même tester 15! possibilités, soit la bagatelle de 1.31*10^12...).

J'ajouterais que si tu veux avoir la meilleure solution, il te faut tester toutes les possibilités. Sinon, il faut utiliser des méthodes heuristiques (les fourmis comme déjà mentionné, ou bien Astar par exemple), mais ces dernières ne peuvent pas garantir un résultat optimal. Elles essayent juste de trouver un chemin "qui à l'air pas trop mal" (plus ou moins "pas trop mal" suivant l'heuristique choisie).

Mako.

[thelvin]

Oui, enfin, on sait que les problèmes NP-complets consomment des ressources exponentielles, mais avec la méthode indiquée, ces ressources c'est censé être du temps, pas de la mémoire.
Quand on empile, on a pas d'explosion combinatoire, en tout cas tant qu'on pense à dépiler.

À mon avis, là il y a empilage de trop de données redondantes : à quoi ça sert de stocker à chaque fois la liste de toutes les villes atteignables, c'est déjà dans la matrice, pourquoi le recopier ? Il y a sans doute d'autres redondances de ce genre.

[IMPRO]

Merci pour vos réponses.

thelvin
à quoi ça sert de stocker à chaque fois la liste de toutes les villes atteignables, c'est déjà dans la matrice, pourquoi le recopier

je suis obligé de les stocker parce qu'il faut parcourir les villes juste une fois. je m'explique, par exemple si j'ai par exemple 4 villes : "A","B","C" et "D" et toutes ces villes reliées entre elles. donc si je démarre de "A" par exemple alors je dois stocker dans une liste ces fils qui seront (B->C->D), et à partir de "A'' j'atteins "B" donc mon chemin est pour le moment et " A=>B " . Après je stock les fils de "B" qui sont (C->D) et NON (A->C->D). et ainsi de suite ... c'est pour sa je dois enregistrer dans une liste.

mais j'ai une question, par exemple si je lance mon application pour 15 villes ( avec un bouton)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
private void jButton3ActionPerformed(java.awt.event.ActionEvent evt) {                                         
        // TODO add your handling code here:
        Profondeur pvc = new Profondeur();
    }

et j'ouvre le gestionnaire de taches, il consomme 400mo de RAM.
et si je lance une deuxième fois avec le même bouton (sans fermer l'application), je constate que la mémoire utilisé pour ce programme est de ~ 800mo !!! alors que normalement la mémoire de la première exécution devrait être libéré.