[Algorythme] Tester toutes les combinaisons possibles

Bonjour,

Je travail sur une BDD sous access 2003, et je suis face a un probleme,

j'ai une table, qui contiend une liste de segments de transports, je doits associer ces segments les un avec les autres de maniere a ce que la solution finale soit le moin couteuse possible. malheureusement ces segments n'ont pas de cout fixes, et le prix d'une combinaison de segment depend de sa propre composition (KM temps de route, nb de segment...)

Je pense donc procèder de la maniere suivante:

évaluer toutes les combinaisons possible de segments (enchainement en fonction des heures de debut et de fin)

évaluer le prix de chaque combinaison

retenir que les combinaisons les plus intéressantes, en excluant les combinaisons qui se recoupent (celles qui contiennent le meme segment)

mon probleme est que je n'arrive pas a formuler le code qui génère toutes les combinaisons possible.

Quelqu'un a une idée ?

cordialement

Franck

pour avoir toutes les combinaisons possibles, il suffit de faire le produit cartésien de ta table avec elle-même.

Code:

---

Select table1.segment, table2.segment from tatable as table1, tatable as table2

---

Par contre, cela limite la combinaison à une combinaison de 2 segments. Pour avoir plus, il faut à nouveau réaliser un produit cartésien du résultat de la première requête avec tatable.

bonjour,

merci de la reponse,

Le probleme, c'est que cela calcul environ 192 millards de possibilité rien que pour les combinaisons de 5 segments.

je vais donc affiner ma recherche car le temps de traitement de la requete risque d'etre tres long....

je m'explique donc.

chaque segments a un N° qui est chronologique.

donc si on prend un exemple simpleavec les segment 1 2 3 4 et pour une combinaison de 3 segments je souhaite obtenir le resultat suivant:
- 1
- 2
- 3
- 4
- 1 2
- 1 3
- 1 4
- 2 3
- 2 4
- 3 4
- 1 2 3
- 1 2 4
- 1 3 4
- 2 3 4

il y a t'il un moyen de générer une table ou un recorset contenant ces combinaisons ??

merci

Franck

A première vue je dis qu’il te faut deux boucles for combine l’une dans l’autre

Code:

---

1 2 3 4 5 6 7 8

i segment, j segment, l segment For i segment l = i For j segment l = combine j et l retourne l Next j Next i

---

plus claire

salut,

la j'ai rien compris du tout....

peut tu essayer de faire plus clair ?

merci

Franck

bonjour,
A la lecture de ce probleme, la solution est une fonction recursive.
Ce type de programmation permet d'explorer toutes les possibilités.
Charge à toi de définir la faisabilité des possibilités.

En esperant t'avoir aidé.
Ray.

Fais une recherche sur des méthode d'optimisation logistique mathématique
Je crois que çà répondrais à ta recherche

Je me souviens avoir fais des trucs dans le genre en cours de math à la fac. Ca résolvait justement ce genre de problématique

Ensuite, il sera sans doute pas trop dur de mettre en oeuvre la solution
Bon Courage

Bonjour,
Ton problème, pour être résolu proprement, relève de la théorie des graphes en recherche opérationnelle : par exemple avec l'algorithme de Dijkstra ou bien celui de de Ford-Bellman

http://fr.wikipedia.org/wiki/Algorithme_de_Dijkstra

je dois reconnaitre que c'est pas simple à mettre directement en pratique.

:)