Mémoire insuffisante

Question

Bonjour,

J'ai un programme qui lit des chaînes de caractères, qui les trie selon leur longueur. En fait, ces chaînes représentent les routes dans un réseau de transport.

J'ai représenté chaque route par une matrice à trois dimensions route(i,j,k) où i désigne la demande de marchandise à transporter, j désigne le numéro de la route dans la liste triée (j=1 désigne la première route de la lsite riée)  et k désigne quel noeud est dans la position k de cette route.

Le hic est que si j'ai 360000 routes pour 100 demandes dans un réseau de 100 noeuds et 120 arcs, alors VB m'affiche "mémoire insuffisante" lorsque je veux charger toutes les routes en mémoire (j'en ai besoin pour des reroutages ensuite ou les tis selon les longueurs).

Y a-t-il un moyen pour ésoudre ce problème?
Merci d'avance

cs_Nephilim · Answer

Sans vouloir trop m'avancer ... l'algo du voyageur de commerce semble convenir à ton problème. Tu devrais en trouver un ici même (projet java), et les tis gars de Diggers en ont pondu à la pelle des plus efficaces :)

Pour ton problème de mémoire, les piles sont tes amies ;)

Tonio

cs_EBArtSoft · Answer

en même temp si j'ai bien compris ça conne un tableau comme ceci : 360 000 * 100 * 100 soit 3 433 Mo de tableau (en considerant le type "byte") pour un petit message de "Memoire insifusante"...

Parfois je me dit que j'aimerais pas êtres un ordinateur !

@+

E.B.

cs_osta · Answer

Merci pour l'info. En fait je ne m'attendais pas à une telle dimension de données (je m'attendais à 5000 routes max).

Peux-tu m'éclairer un peu plus sur les piles? Sinon j'envisage de faire des Records et des pointeurs sur ces records pour ne pas trop surcharger la mémoire.

cs_Nephilim · Answer

Les piles sont, comme leur nom l'indique, des piles :) Si tu cherche de la doc là dessus, le terme anglois est "stack" (d'où le "stack overflow" ;)).  Sinon tout bon bouquin d'algo fera l'affaire car c'est vraiment un concept de base.

En gros c'est une liste de données à longueur variable, et dans laquelle tu vas au fil de ton code ajouter des données (push) puis les retirer (pop) lorsque tu n'en auras plus besoin.

Ca n'est pas vraiment la pile qui t'aidera à économiser de la mémoire, mais la façon dont ton algo sera conçu par dessus, bien souvent de façon récursive : tu empiles à l'aller et tu dépiles au retour. L'objectif est d'éviter de stocker l'intégralité des routes pour comparaison, en subdivisant au maximum ton problème. 

Dans le cas précis du voyageur de commerce, j'aurais du mal à plus rentrer dans les détails vu que je m'occupais plutôt du moteur 3D à l'époque :o) Et puis ton problème a l'air un peu plus complexe, vu qu'il ne s'agit pas d'organiser la tournée d'une personne mais d'un groupe ... je suppose qu'il y a des contraintes supplémentaires (points de départ, de passage obligatoire etc.), donc tu t'éloigne du cas "d'école" et il faudra sûrement adapter.

Pour la théorie pure, jette un oeuil ici :
http://graal.ens-lyon.fr/~fvivien/Enseignement/Algo-2001-2002/Cours.pdf

Le chapitre 5 sur les structures de données décrit les piles (et files).
Le chapitre 6 t'expliquera plus clairement de principe de "subdivision" algorithmique.
Et le problème final abordé est ... le voyageur de commerce :)

Pour le code, si tu es fainéant, je te laisse fouiller le net ;) Maintenant je répète que le concours Diggers imposait l'usage d'un algo optimisé (fallait calculer vite et pas faire péter la mémoire), donc en demandant aux intéressés de cette année tu devrais pouvoir obtenir un code efficace sinon propre ! Je vais demander à Kraken si il a encore le sien, mais ça commence à dater ...

Tonio

cs_Nephilim · Answer

Oups, à relire ton message tu es peu-être plus éloigné que prévu du problème initial ... et si tu parles de noeuds et d'arcs, c'est que tu as sûrement un certain nombre de notions sur les graphes et leur parcours :) Mais je persiste à penser qu'il est étrange de conserver l'intégralité des routes en mémoire, nécessité de reroutage ou pas !

Maintenant le plus immédiat est de stocker tes routes à part effectivement, et de ne traiter que des pointeurs ou équivalents sur ces routes (si ça n'est pas déjà le cas !), mais le problème reste entier car ça fait beaucoup de routes à stocker ... pourrais-tu être plus précis sur le problème global que tu cherche à résoudre ?

Tonio

cs_osta · Answer

Merci bien pour le détail! C gentil de votre part. 

En effet, je cherche à construire des jonctions de différents diamètres(des tubes en gros) entre plusieurs paires de sommets qui constituent les demandes. Chaque demande comporte plusieurs tubes de dimensions différentes à construire entre ses sommets. Mon réseau comporte des noeuds et des liens entre les noeuds qui ont des capacités finies. Donc la somme des diamètres des tubes entre deux noeuds ne doit pas dépasser la capacité du lien (Gros tubes englobant ceux à contsruire)

C'est un peu compliqué, il fait intervenir le bin packing et le multiflot. 

Pour la construction des petits tubes, j'ai fait l'algorithme suivant
1-Générer toutes les routes entre les sommets des demandes
2-ordonner les routes par leur longueur (longueur est le nombre de noeuds intermédiaires entre deux noeuds donnés)
3-pour chaque tube à construire entre deux noeuds de demande
3-1 lire la demande correspondante et le diamètre.
3-2 aller à la première route de la liste triée des routes de la demande correspondante.
3-2-1 s'il y a dépassement de capacité alors choisir la route suivante de la liste triée
3-2-2 sinon et si on arrive à la destination alors sauvegarder le routage du tube

Donc pour chaque type de diamètre (j'en ai trois), il faut sauvegarder les routes pour pouvoir les classer (tri)  et aller à la suivante en cas de saturation d'un lien de cette route.

J'ai modélisé les routes par une matrice à trois vecteurs, le n° de la route dans la liste triée, la demande correspondnate et le n° de chaque noeud de cette route. Donc pour 100 demandes, 60000 routes et 100 neouds par route ça devient énorme!!

De toutes les façons je crois qu'en définissatnt des structures appropriées sous C et avec des pinteurs je m'en serais sorti

Merci quand même

Mémoire insuffisante

6 réponses

Discussions similaires