Pour effectuer le produit de 4 matrices réelles de taille respective 10x20, 20x50, 50x1 et 1x100, il est possible de commencer par n'importe lequel des 3 produits, étant donnée l'associativité du produit matriciel. Rappelons également que le produit d'une matrice pxq par une matrice qxr donne une matrice pxr. Si le produit d'une matrice pxq par une matrice qxr demande p.q.r opérations scalaires, il est possible de calculer le coût de chaque possibilité.

produit 1	produit 2	produit 3	coût total
(10x20, 20x50): 10000	(10x50, 50x1): 500	(10x1, 1x100): 1000	11500
	(50x1, 1x100): 5000	(10x50, 50x100): 50000	65000
(20x50, 50x1): 1000	(10x20, 20x1): 200	(10x1, 1x100): 1000	2200
	(20x1, 1x100): 2000	(10x20, 20x100): 20000	23000
(50x1, 1x100): 5000	(10x20, 20x50): 10000	(10x50, 50x100): 50000	65000
	(20x50, 50x100): 100000	(10x20, 20x100): 20000	125000

1. L'ordre optimal de multiplication permettant de minimiser le nombre total d'opérations scalaires est donc celui indiqué en gras: (20x50, 50x1), puis (10x20, 20x1), puis (10x1, 1x100), qui coûte 2200 opérations. On peut observer sur le tableau que l'heuristique gloutonne, qui consiste à choisir à chaque fois le produit le moins coûteux à faire, fonctionne très bien dans ce cas, et conduit au bon résultat sans retour arrière.
2. Si le nombre de matrices à multiplier est quelconque, il est possible d'appliquer l'heuristique gloutonne, qui donnera un bon résultat. Il est possible de vérifier a posteriori la qualité de ce résultat en comparant le coût de la solution trouvée aux coûts des différentes branches laissées en suspens. Ainsi, les solutions descendant de la première possibilité ont au moins un coût de 10000, donc sont toutes moins bonnes que la solution trouvée, sans qu'il soit besoin de développer ces solutions.

Remarque complémentaire:

Dans le cas général, si l'on a à faire le produit de matrices pxq, qxr et rxs, il faudra commencer par le premier si pqr+prs < qrs+pqs, c'est à dire si 1/p + 1/r > 1/q + 1/s. L'heuristique gloutonne n'est donc pas équivalente à celle consistant à effectuer d'abord le produit qui "élimine" la plus grande dimension de matrice. Un contre exemple simple est le produit 6x15, 15x20 et 20x10.

• 6 états {q0, q1, q2, q3, q4, q5}
• 2 caractères {a, B, 1},
• un état initial q0, les actions de déplacement étant notées G et D.
• programme:
  • (q0 B G q0) (q0 a 1 q1)
  • (q1 a G q1) (q1 B G q2) (q1 1 G q1)
  • (q2 a B q3) (q2 B G q2)
  • (q3 B D q3) (q3 a D q3) (q3 1 G q4)
  • (q4 B D q5) (q4 a 1 q1)
  • (q5 1 B q4)

On peut alors essayer cette machine sur la chaine ...BBaaaaaBaaaBBB..., la lecture commençant par la droite. Merci à Cécile Janvier, qui m'a signalé une erreur dans la première version du corrigé.

Dans l'état q4, si c'est B, c'est qu'il n'y a plus de "a" entre les "1" et les "B" separateurs. Donc c'est le moment de terminer le calcul. Sinon, il y a encore un tour a faire.

1. Pour trouver un chemin passant par chacune des villes et revenant au point de départ, il suffit de choisir une permutation de la suite des n villes. Si l'on n'a besoin que d'un chemin, on peut procéder par tirage au hasard. Si l'on a besoin d'énumérer tous les chemins, on peut utiliser un algorithme récursif.
2. Une fois un chemin donné, on peut chercher à l'améliorer au moyen de l'heuristique suivante. Soient (a,b) et (c,d) deux étapes du chemin. Si D(a,b)+D(c,d)>D(a,c)+D(b,d), alors on peut couper (a,b) et (c,d) et les remplacer par (a,c) et (b,d) pour obtenir un chemin plus court. Cette opération peut être faite pour tous les couples d'étapes du chemin, jusqu'à ce que l'on ne puisse plus l'améliorer.

Cette heuristique donne en général des solutions assez bonne à ce problème, connu sous le nom de problème du voyageur de commerce.

1. Pour n = 0, la fonction quefaisje renvoie 0. Quant à la fonction etmoidonc, elle boucle et ne renvoie donc rien. Une modification possible pour corriger le problème est d'ajouter au début le même test que celui qui figure dans la première fonction.

   fonction quefaisje(n) si n < 0 ^0 sinon si n pair ^quefaisje(n/2) sinon ^1 + quefaisje((n-1)/2)

   fonction etmoidonc(n) si n < 0 ^0 sinon selon (n modulo 4) 0: ^etmoidonc(n/4) 1: ^1 + etmoidonc((n-1)/4) 2: ^1 + etmoidonc((n-2)/4) 3: ^2 + etmoidonc((n-3)/4)

2. Pour chacune de ces fonctions, la valeur renvoyée pour n = 4p est la même que la valeur renvoyée pour n = p.
3. Si l'on regarde aussi ce qui se passe pour n = 4p+1, n=4p+2, n=4p+3, on en conclut que ces deux fonctions sont équivalentes et renvoient toujours la même valeur:

   n	f(n) = quefaisje(n)	f(n) = etmoidonc(n)
   4p	f(p)	f(p)
   4p+1	f(p)+1	f(p)+1
   4p+2	f(p)+1	f(p)+1
   4p+3	f(p)+2	f(p)+2

4. A chaque étape, la fonction quefaisje divise n par 2, il faudra donc log2(n) étapes pour calculer quefaisje(n). La fonction etmoidonc, elle, divise n par 4 et sera donc de complexité log4(n)=log2(n)/2.

Question subsidiaire facultative:

La valeur renvoyée par ces fonctions pour n = p.q+r, si q est une puissance de 2 et r<q, est égale à f(p)+f(r). On en déduit alors que ces fonctions calculent le nombre de 1 dans la représentation de n en base 2.

retour à l'énoncé.