Meilleure combinaison, methode de recherche mathematique...

[invitedbef360d]

Bonsoir,

J'ai un probleme, je cherche la meilleure solution parmis 4^30 possibilites...
Je vais tenter d'etre un peu plus clair.
Voici une image pour commencer :


En fait j'ai un tableau avec 3 colonnes et 10 lignes.
Je somme chaque ligne et ensuite je somme les lignes pour lesquelles la somme est negative (cellules en rose).

Mon resultat final est la cellule jaune (somme des cellules roses).

La ou ca se complique c'est que sous chaque valeur je peux incerer zero, un, deux ou trois 0 (en rouge).
Ces 0 decalent les valeurs d'autant.

Cela change la valeur de la somme sur chaque ligne et le resultat final.

Je cherche une methode pour trouver (ou du moins approcher) la meilleure combinaison.
Si je teste toute les possibilites, j'en ai 4^30!!

Aurriez-vous une idee ou une piste pour resoudre mon probleme??

Merci

Thibaut
-----

[Scorp]

Petite question juste pour éclaircir les choses : le tableau de 30 entrées est-il fixe, ou faut il en plus une formule générale quelque soit le tableau d'entré ?

[invitedbef360d]

Bonjour,

Le tableau d'entrée n'est pas fixe, là, c'est juste un cas.
Tu penses à quelque chose?

Thibaut

[leg]

il faut savoir pourquoi tu incère un 0 rouge est ce répétif, 1,2,3 puis 1 est tu décales d'une ligne, c'est cette raison qu'il faut expliquer .
et tu cherches la meilleur combinaison de quoi ?

[A voir en vidéo sur Futura]

[invitedbef360d]

Bonjour,

Ce n'est pas répétitif, le dessin montre juste les 4 premières combinaisons.
Dans la dernière combinaison (la 4^30 eme) il y'a Trois 0 incérés sous chaque valeur.

Je recherche la meilleure combinaison (le nombre de 0 sous chacune des 30 valeurs) pour laquelle la somme des valeurs négatives de chaque ligne est la plus proche de 0.
C'est la valeur jaune qui doit être la plus proche de 0.

Est-ce que j'ai été plus précis?

Thibaut

[leg]

donc tu veux obtenir 1 , sachant que tu as -81 et + 80 et il te faut placer les 0
de sorte , que la somme des lignes te donne cette colonne = 1 jaune "aux alentour de 1"
mais je suppose que tu as des restrictions, tu ne peux pas placer autant de 0 que tu veux...Non?

[invitedbef360d]

En réalité, je peux mettre des 0 toutes les 3 cellules, ce qui fait que ca ne déborde pas du tableau, donc ce n'est pas 4^30 mais 4^10 possibiltés. Mais le problème reste entier, cela fait toujours trop de cas différents à calculer.

[Toufou]

Bonjour,

Avant toute chose, ton problème, c’est un exo dans le cadre d’étude ou c’est pour résoudre quelque chose de concret, si oui quoi ? Comment comptes-tu tes 4^30 possibilités ? Tu cherches une formalisation mathématique ou un programme informatique ?
Si j'ai bien compris le problème, j’ai l’impression que tu te fais peur pour rien…

[invitedbef360d]

Ce n'est pas un exercice d'école (les études sont terminées pour moi malheureusement).
Si on considère qu'on peut ajouter zero, un, deux ou trois 0 sous 10 des 30 valeurs du tableau (toutes les 3 valeurs), on a 4^10 combinaisons differentes.
Où dans mon raisonement, penses-tu que je me fasse peur?

[invite986312212]

salut,

je n'ai pas beaucoup réfléchi à ton problème, donc je ne sais pas s'il y a une méthode analytique, mais je trouve que 4^10 ça n'est pas énorme, tu peux eplorer toutes les possibilités et choisir la meilleure. Bien sûr si ce n'est là qu'un petit exemple mais que le problème réel est beaucoup plus grand ça ne suffira pas.

[Toufou]

Les 0 ne peuvent être que dans la première colonne??
D'après ton premier poste, j'avais compris que tes solo, duo ou trio de zéros pouvaient prendre chacun 30 positions (en supposant qu’il puisse y avoir 1,2, ou 3 zéros dans la première case) avec une seule occurrence à chaque fois. Il n’y aurait donc que 90 tableaux avec 11 additions à évaluer. Le seule « difficulté » c’est le déplacement des valeurs. Il me semble que cela se solutionne avec 3 tableaux et un modulo, mais c'est de l'algo pas des math. Maintenant, j'ai peut être mal compris.
Si c'est pas pour un exo, concrètement c'est pourquoi ?

[invitedbef360d]

Et oui, tu as bien compris, ici, c'est un petit exemple.
Dans ce que je recherche, j'ai 2000 valeurs en tout et 30 points sous lesquels je peux ajouter zero, un deux ou trois 0.
Meme avec l'ordinateur, de la nasa, ca mettrait du temps à explorer toutes les solutions (avec un Thinkpad récent, je peux explorer à peu près 5 000 000 de valeurs par heure).
Je cherche donc une méthode géneral (et un peu plus intéligente que la méthode bourine qui consite à tout tester) pour réduire le nombre de calculs.
Aurriez-vous des pistes à explorer?

[leg]

je trouve :-8


-9....0...10...9....-5
-5....0....0....-2...7
-1....3...-3....0
-9....9....0....0
-6....9....4....-7
.6...-9....0....0
-6...-2....4....0
.0.....7....0....-7
.2....-6...-4....9
.1.....0....0....0

mais sans respecter le 2 cellules d'écart....

[invite986312212]

ressalut,

si tu expliquais un peu l'origine du problème? ça me motiverait un peu...

[leg]

Et oui, tu as bien compris, ici, c'est un petit exemple.
Dans ce que je recherche, j'ai 2000 valeurs en tout et 30 points sous lesquels je peux ajouter zero, un deux ou trois 0.

Je cherche donc une méthode géneral (et un peu plus intéligente que la méthode bourine qui consite à tout tester) pour réduire le nombre de calculs.
Aurriez-vous des pistes à explorer?

Aucune de plus, si il n'y à pas une période cyclique de différences ou autre...
et je suppose que c'est aléatoire....
il ne te reste plus qu'à creuser...

[invitedbef360d]

Ben voilà,
J'ai un train électrique, avec plusieurs montées et descentes. J'ai 2 locomotives. Dans la montée, la loco consomme beaucoup d'électricité tandis que dans la descente, le moteur de la loco devient générateur.
Si les 2 locos sont en meme temps sur la descente, les 2 deviennent génératrices et cette energie est perdue si il n'ya pas une 3 eme loco qui la capte.
Mes mesures sont les energies consommée par une loco en fonction du temps. Quand c'est consommé par la loco c'est positif et quand la loco genere le courrant, c'est négatif.

En gros j'essaye de répartir mes 2 ou 3 locos de façon optimum pour eviter que les 3 consomment à fond en meme temps et qu'elle ne soit generatrices en meme temps.
Avec 2 loco c'est assé simple mais avec plus c'est dur.

Voila le cadre.

Sinon, comment as-tu fait pour trouver cette solution? Est-ce la meilleure?

[leg]

Ben voilà,
J'ai un train électrique, avec plusieurs montées et descentes. J'ai 2 locomotives. Dans la montée, la loco consomme beaucoup d'électricité tandis que dans la descente, le moteur de la loco devient générateur.
Si les 2 locos sont en meme temps sur la descente, les 2 deviennent génératrices et cette energie est perdue si il n'ya pas une 3 eme loco qui la capte.
Mes mesures sont les energies consommée par une loco en fonction du temps. Quand c'est consommé par la loco c'est positif et quand la loco genere le courrant, c'est négatif.

En gros j'essaye de répartir mes 2 ou 3 locos de façon optimum pour eviter que les 3 consomment à fond en meme temps et qu'elle ne soit generatrices en meme temps.
Avec 2 loco c'est assé simple mais avec plus c'est dur.

Voila le cadre.

Sinon, comment as-tu fait pour trouver cette solution? Est-ce la meilleure?

je t'ai mis les 0 en gras, mais cela ne correspond pas forcément au fonctionnement de tes locomotives .

il doit y avoir une meilleur solution que le tableau que tu as proposé .
en définitive il faudrait recalculer les périodes de temps en fonction des trajets ce qui est sur; c'est qu'il y a 1 point d'écart , ce qui veut dire que c'est presque pareil consommation et génératrice...tout dépend du trajet que vont faire tes locomotive en décalant les trajets et départ.....il faut t'arranger pour qu'il y en est deux en descente et une qui monte ...
et le départ doit se faire à un en droit précis du circuit ...pour les différentes loco...
elles ne fonctionnent pas sur secteur ? est ce qu'en période de génératrice tu ré-alimente quoi?

mais le circuit est fixe, donc je suppose qu'il y a une répétition de passage il doit être possible de faire un décalage.

à moins que tes 0 servent justement à faire changer de voie afin justement de ne pas consommer en même temps.. donc ce qu'il te faut c'est ou placer tes 0....
par contre je ne vois pas pourquoi tu veut minimiser le courant négatif, c'est à dire le circuit où elle génère le moins de courant;
donc le circuit ou elle consomme le plus.....

[Toufou]

Ben voilà,
J'ai un train électrique, avec plusieurs montées et descentes. J'ai 2 locomotives. Dans la montée, la loco consomme beaucoup d'électricité tandis que dans la descente, le moteur de la loco devient générateur.
Si les 2 locos sont en meme temps sur la descente, les 2 deviennent génératrices et cette energie est perdue si il n'ya pas une 3 eme loco qui la capte.
Mes mesures sont les energies consommée par une loco en fonction du temps. Quand c'est consommé par la loco c'est positif et quand la loco genere le courrant, c'est négatif.

En gros j'essaye de répartir mes 2 ou 3 locos de façon optimum pour eviter que les 3 consomment à fond en meme temps et qu'elle ne soit generatrices en meme temps.
Avec 2 loco c'est assé simple mais avec plus c'est dur.

Voila le cadre.

Sinon, comment as-tu fait pour trouver cette solution? Est-ce la meilleure?

Merci d'avoir donné le cadre (ça me ferait mal de réfléchir gratos pour un banquier )
Je ne suis toujours pas certain d'avoir compris. Je croyais qu'il n'y avait qu'une occurrence de 1, 2 ou 3 zéros par tableau à évaluer. Dans l'exemple de Leg il y a une tapée de zéros et là c'est certain la combinatoire explose...

[invite986312212]

c'est amusant comme problème. Je suppose que dans l'exemple que tu donnes tu as 3 locos? et tu peux insérer des segments horizontaux. Par contre tu ne peux pas permuter les éléments du tableau, c'est dommage, parce que là on pourrait trouver un algorithme assez efficace.

[invitedbef360d]

Merci pour votre aide.

J'ai fait un petit schema:


En fait pour avoir les donnees de depart, j'ai pris une loco, j'ai mesure le courant tout au long du circuit, seconde par seconde.

Je considere ca comme la reference (a un point x du circuit, j'ai une consommation elec y).
Les loco (si on considere que la vitesse est constante tout au long du circuit et qu'il n'ya pas de retard aux points rouges) sont situees a equidistance. Je ne peux pas avoir 3 locos a la queue leuleu et une 4eme ailleur.

voila pour les precisions : )

[invitedbef360d]

c'est amusant comme problème. Je suppose que dans l'exemple que tu donnes tu as 3 locos? et tu peux insérer des segments horizontaux. Par contre tu ne peux pas permuter les éléments du tableau, c'est dommage, parce que là on pourrait trouver un algorithme assez efficace.

Oui, dans l'exemple, c'est comme si je prennais 3 locos.

Voici un schema:


Avec 1 loco, ca represente les valeurs du courant mesurees.

Quand tu parles de permuter? tu penses a des valeurs sur la meme ligne?

[leg]

bonjour

je suppose que les 0 sont les retenues 1,2 ou3" mais dans qu'elle but , puisqu'alors elles vont se rapprocher les une des autres...ou alors cela serra identique pour les 4 loco..
en fonction de leur emplacement sur le circuit.

qu'elle est le problème exact de la consommation de courant et de la production de courant ...?
car en fonction de cela il te faudrait en placer une en haut d'une montée donc début descente,= génératrice, et la 2ème en bas de la montée = consommation pour la même durée de parcourt ..
les deux autres à équidistance; début de consommation et début de génératrice.mais par rapport aux deux premières .
car je suppose que la distance de montée est = à la distance de descente, afin d'équilibrer la consommation électrique, puisque tu as une consommation de courant < à 1 unité (80+, et , 80-) donc c'est en fonction de ces points du parcourt qu'il faut déjà les placer.

et les points d'arrêt doivent permettre justement de respecter cet équilibre de sorte que tes locomotives arrivent en même temps, une au début de descente, et l'autre au début de montée. pendant que les deux autres sont à l'autre bout du circuit et qu'elles en feront de même .il faut calculer les différents temps pour arriver justement à ces points précis, étant donnée que la vitesse est constante pour les 4 loco..
je pense, qu'il faudrait que 2 points d'arrêt * 2 ; mais justement les choisir en fonction de la distance qu'il reste à parcourir pour être en début de montée et de descente
1)début de descente
2) début de montée
3 ) équidistance du début de montée
4) à équidistance de 3
ce qui te donne:
lorsque la troisième à fini sa descente, la 4ème est en début de descente.

et donc consommation et génération de courant équilibrée:
pour la partie montée - la partie descente.

la partie la plus longue de montée doit correspondre à la partie la plus longue de descente placer les deux dernière locomotive de sorte qu'elles arrivent à ces deux points en même temps que les deux premières ont fini.

[invite986312212]

Quand tu parles de permuter? tu penses a des valeurs sur la meme ligne?

je pensais à la possibilité de changer la disposition des tronçons montants et descendants.

[invitedbef360d]

Le circuit n'est pas à moi (c'est avec un club), je ne peux pas modifier les pentes ni leurs dispositions.
Les montées n'ont pas forcement les memes inclinaisons que les descentes.
A chaque point rouge je peux retenir la loco quelques secondes. C'est le cas pour toutes les locos. Toutes ont le meme temps de parcours et toutes sont retenues la meme durée à chaque point rouge.

thibaut

[leg]

Les montées n'ont pas forcement les memes inclinaisons que les descentes.

thibaut

ok donc c'est une question de durée de trajet pour les montée par rapport aux descentes qui devrait fixé les emplacements des 4 locomotives, afin de partagée en deux * deux , les consommation et les génératrices.
mais je suppose que cela à du être étudié car le parcourt est fixe; et vous connaissez les endroit et la durée du parcourt où les locomotives génèrent et consomment du courant.

[invitedbef360d]

Bonjour,

En fait j'ai pris une loco, défini un parcours type. Je l'ai callé pour qu'une loco fasse le tour en 5 min (300 sec).
Pour chaque seconde j'ai mesuré le courant.

Donc à la seconde x (sans aucune rétention des locos aux points rouges), la loco est toujours à la même position sur le circuit et la consommation ou génération de courant est la même.

Merci pour l'intérêt que tu portes à mon problème.


thibaut

[leg]

Bonjour,

En fait j'ai pris une loco, défini un parcours type. Je l'ai callé pour qu'une loco fasse le tour en 5 min (300 sec).
Pour chaque seconde j'ai mesuré le courant.

Donc à la seconde x (sans aucune rétention des locos aux points rouges), la loco est toujours à la même position sur le circuit et la consommation ou génération de courant est la même.

Merci pour l'intérêt que tu portes à mon problème.


thibaut

Bonjour

tu prends le parcourt pour 1 locomotive qui est le parcourt total de ton circuit. ok

en fonction de ton schéma 1 loco donc tu mets la première sur le point -9 début ("5cellules")

-9 . -5. -1 .-9 .-6; courant -

tu mets la deuxième deux cellules plus loin, ce qui donne ("5cellules"):

2 . 1 . 3 . 9 . 9 ;courant +

tu sautes 5 cellules et tu mets la troisième sur le point -3, juste après 10. donc pour 5 cellules :

-3 . 4 . 4 . -4 . 0 , courant = 0 ("+1, car -7 et +8)

tu met la 4 ème sur le point 0 soit 2 cellules plus loin, donc pour 5 cellules :

-7 .0 . -7 . 9 . -5 . courant -

et la 3ème colonne te donne + 5 alors que les trois autres sont en production de courants pour le départ ..et pour 5 cellules parcourues.

ensuite tu regardes ou tu tombes pour la 6ème cellule de chaque loco
et là sur la 6ème elles consomme + et - pour les deux premières
et
il faut faire un décalage..pour la 3ème loco, arrêt une seconde sur la 5éme cellules = 0, la 4ème passe la 6ème cellule 7 et arrive sur -9,

tu libères la troisième; la troisième est sur 9, et la 4ème sur -9, puis tu arrête une seconde la 1èr ,2èm et 4ème pour absorber le décalage d'une seconde de la 3ème . elles auront toutes parcourues 7 cellules .

tu peux prendre 4 rubans qui correspond à ton schéma
pour 1 loco et tu les faits glisser les uns sous les autres, pour voir le meilleur résultat...
amuse toi bien.

[invitedbef360d]

Merci pour ton aide, je vais essayer ca et voir si je ne peux pas en tirer un algorithme général qui pourrait fonctionner sur plusieurs configurations.

Thibaut