Un problème de combinatoire

Question

Bonjour, Pour un projet de R.O. (Recherche opérationnelle) Statistique, je dois faire plusieurs choses:

Tout d'abord, lister l'ensemble A toutes les combinaisons de k éléments dans un ensemble de n éléments (k<= n )
Ensuite, pour chaque combinaisons Ai lister l'ensemble Bi toutes les permutations de j valeurs possibles.
Enfin pour chaque Bil vérifier si elles correspond aux contraintes (à définir en fonction de la recherche).

D'un point de vue mathématiques, l'ensemble A contient n! / ( k! ( n - k ) ! ) et chaque ensemble Bi contient j! éléments; soit un total de j! ( n! / ( k! ( n - k ) ! )). Exemple: Un bus de 80 places possède 15 passagers et chaque passager à une particularité spécifique parmi 10 catégories, recenser l'ensemble des possibilités de placement de ces passagers dans le bus. Le nombre de combinaisons total est donc de 10! ( 80! / ( 15! (80 - 15) ! )) = 5 472 782 816 133 670 000 000 Je voudrais votre avis sur comment procéder, dois-je commencer par calculer l'ensemble A dans son intégralité ou faire en sorte qu'au fur et à mesure que celui-ci se remplit créer les ensembles Bi auxquels j'ai "accès"; ou aborder une toute autre approche..? De plus j'aimerais un coup de main sur quelques points où je ne vois pas comment procéder:

Gérer la sauvegarde du processus, de sorte à pouvoir le reprendre ultérieurement au stade où il s'était arrêté (comme pour le moment je gère tout cela à l'aide de récursive je n'arrive pas à correctement sauver mon état)

Permettre l'affichage de la progression à l'aide d'un ProgressBar, le problème étant les grands nombres à gérer et quel format utiliser pour les stocker sachant que cela doit ralentir le moins possible le reste (donc les Decimal à éviter par exemple)

Toute piste utile à l'optimisation du tout aussi bien en terme de vitesse d'exécution, qu'en terme de mémoire (du processus en lui même d'une part et du format de stockage des résultats valides d'autre part, sachant que toute base de données est exclue (au moins pour le moment))

Merci d'avance à tous, pour l'attention portée à ce message ainsi qu'à toute aide apportée !

cs_Orohena · Answer

Bonjour

Je pense que la priorité est de bien choisir le système d'exploitation et l'outil de programmation. Ton application est à la limite de ce que peuvent faire la plupart des langages. Je ne connais pas vb2005 et vb.net, donc je ne peux pas donner d'avis. Je souhaite seulement attirer ton attention sur cet aspect important de ton projet.


Sauvegarde : Je ne pense pas qu'un langage de haut niveau, comme VB, permette d'écrire un algorithme vraiment efficace de point de reprise, surtout pour un processus récursif. Des langages de bas niveau tel que le c ou l'assembleur sont, je pense, parfaitement capables d'accéder aux piles et les manipuler. En effet, la solution la meilleure, voire la seule, pour créer des points de reprise entre deux sessions est d'accéder directement à la mémoire des données de ton processus pour la sauvegarder et la restaurer. Ce n'est pas très nouveau, des applications existent, permettant par exemple la reprise automatique d'un processus après un crash sur mini-ordinateurs.


Afin d'optimiser l'exécution d'une appli comme la tienne, il faut éviter comme la peste les entrées-sorties vers l'écran ou autres périphériques, au sein de tes boucles. Tout appel au système consommera en effet bien davantage de temps machine que tes instructions mathématiques qui, elles, utilisent relativement peu de code et ne sollicitent que la mémoire vive. Dans un processus récursif, une barre de progression est utile, mais pas essentielle, et elle peut ralentir sensiblement, voire plomber l'exécution du code. Enfin, c'est mon avis.

Aussi une bonne chose idée serait de faire tourner ton appli sur une machine dédiée, dont ton application sera le seul processus utilisateur, et de ne pas etre chiche sur la mémoire vive. Chaque fois que tu devras faire tourner ton appli de RO en même temps que d'autres applications, veille à élever la priorité de la RO au-dessus de celle des autres applications.

Cordialement

Sehnsucht · Answer

Je suis tout à fait d'accord avec vous, et dans une situation similaire décontextualisée j'aurais approuvé cent fois, malheureusement; ma situation m'impose ces contraintes logicielles et matérielles d'où le présent sujet posté ici.

Sehnsucht · Answer

Up

cs_Orohena · Answer

Sehnsucht, j'ai reçu "Up" ! Message tronqué ???

Je profite de l'occasion pour vous dire que je regrette mon message précédent. J'avais bien compris que vous aviez des contraintes fortes. Pour être sincère, dans votre config actuelle, je pense que votre application va tourner des années et des années avant que vous obteniez un résultat. Des années sans panne ni plantage ? c'est hasardeux, n'est-ce pas ?

J'ai essayé de passer le message en restant positif, en proposant des solutions, dans l'esprit de ce forum. Mais je ne m'y suis assez mal pris, c'est sûr.

Cordialement

Un problème de combinatoire

4 réponses

Votre réponse

Discussions similaires