Trier des actions pondérées

Je possède un certain nombre d'actions, qui sont pondérées par leur temps d'éxécution. Ce que je veux faire : éxécuter ces actions le plus rapidement possible.

Exemple :
Je veux écrire :ExeMplE
Sachant que :
écrire une lettre = 1s
passer de majuscule en minuscule = 2s
passer de minuscule en majuscule = 3s
changer la couleur = 5s
Donc il y a tout d'abord la méthode :
Mettre en rouge / Passer en majuscule / Ecrire une lettre / Passer en minuscule / Mettre en bleu / Ecrire une lettre / Passer en rouge / Ecrire une lettre / Passer en majuscule / Passer en vert / Ecrire une lettre / Passer en rouge / Passer en minuscule / Ecrire une lettre / Passer en jaune / Ecrire une lettre / Passer en noir / Passer en majuscule / Ecrire une lettre
5+3+1+3+5+1+5+1+3+5+1+5+2+1+5+1+5+3+1 = 56s si je ne me suis pas trompé.
Il y a moyen de faire plus rapide dans ce cas la en évitant des changements de couleur en écrivant par exemple toutes les lettres rouges, puis toutes les lettres vertes.... etc.

Ce que je cherche donc c'est un algorithme qui trouve l'enchainement d'action le moins consomateur de temps...

-> J'avais essayé de calculer toutes les combinaisons différentes, puis de calculer le temps de chacune des combinansons, de les trier et de prendre la plus rapide...
Mais le temps de faire tous les calculs, j'ai le temps de faire la combinaison la plus longue ^^ donc ça servait à rien...

-> J'avais essayé de de limiter le plus possible les apels aux actions les plus couteuses...
A = 3s
B = 2s
C = 1s
Mais souvent j'ai moins de A que de B; j'optimise en évitant de faire 1 A, mais pour cela il faut que je fasse 4 B en plus,(par exemple) ce qui est plus long qu'un A. Donc ça n'a pas optimisé en fait...

Voila, je m'en remet à vous... :twisted:

Essayons d'exprimer le problème d'une autre manière:

On a différentes actions à réaliser:
A1) écrire E (en majuscule et en rouge)
A2) écrire x
A3) écrire e
A4) écrire M
A5) écrire p
A6) écrire l
A7) écrire E

On est en mesure de calculer les temps qu'il faut pour passer d'une action à une autre.

Ex A1=>A2 (E -> x)
- passer de majuscule en minuscule: 2s
- changer la couleur: 5s
- écrire x: 1s
Total: 8s

De là on peut représenter le problème sous forme d'un graphe, avec:
- comme noeuds du graphe: les actions à effectuer
- comme arcs du graphe: les passages d'une action à une autre, avec comme valeur le temps d'exécution

Comme il s'agit d'un graphe, on évolue en terrain connu.

Le graphe ainsi obtenu est extrêmement dense puisque pour tous points x et y du graphe tels que x!=y, il existe un arc entre x et y. Ainsi, si on a n actions (points du graphe), on aura n^2 transitions possibles (arcs du graphe)

Maintenant, le problème consiste à trouver le chemin de poids minimal permettant de relier tous les points du graphe sans passer 2 fois par le même point. Il s'agit donc ni plus ni moins que du problème dit du "voyageur de commerce" qui malheureusement est NP-complet.

Cependant, tout n'est pas perdu: on peut en effet s'appuyer sur l'ensemble des algorithmes sur les graphes pour obtenir une approximation de la solution optimale.

Bien sûr on n'aura qu'une approximation de la solution optimale, mais cette solution sera bien suffisante car, comme tu l'as signalé, essayer de trouver la solution optimale prendrait alors plus de temps que d'effectuer la combinaison la plus longue.

Hum je suis allé voir sur le liens que tu m'as donné, (j'ai cherché sur google : "voyageur de commerce") je vois comment faire si toutes mes actions prennent le même temps...
Faire une espèce de tableau de Karnaught (pas sur de l'orthographe)....
Mais pour des actions qui ne prennent pas le même temps je ne vois pas comment faire un algo générique....

En plus cet algo sera apellé souvent même très souvent...
Peut-être 100, 200 fois par secondes...

J'ai pensé au moindre carré, mais c'est beaucoup trop long comme méthode...