3.3 Triangle contenu dans un carré fixé

On se propose de déterminer le maximum de l'aire d'un triangle dont les sommets appartiennent à un carré donné, par exemple le carré . Donnons plusieurs méthodes de résolution de ce problème.

Soient les sommets du triangle et leurs coordonnées. Appelons score d'un triangle le double de son aire. On a , c'est à dire :

3.3.1 Monte-Carlo, première version

Une première technique consiste à fabriquer N triangles par tirage au sort de chacune des 6 coordonnées , selon une loi uniforme sur et à conserver le meilleur des scores obtenus. Une exécution avec nous a donné des valeurs de contenues dans l'intervalle , ce qui est bien loin du résultat !

Lorsque l'on regarde l'histogramme des valeurs obtenues pour A (figure 3.1), on constate que l'ensemble des triangles réalisant un score voisin du maximum est un ensemble de mesure très petite et que, plus précisément, .

Figure 3.1: Aires de 2000 triangles contenus dans le carré.

Ce qui rend peu efficace ce premier algorithme n'est donc pas que les triangles réalisant le maximum forment un ensemble de mesure nulle, mais que le passage au voisinage du maximum soit un événement rare. Cet état de fait est évident géométriquement : si l'un des sommets (par exemple ) n'est pas sur le bord du carré, on améliore le score du triangle en éloignant ce sommet le long de la médiatrice du segment .

3.3.2 Monte-Carlo, deuxième version

Nous allons donc maintenant nous limiter à des triangles dont les sommets sont situés sur les bords du carré. Pour sélectionner de tels points selon une mesure uniforme, nous utilisons une variable uniformément répartie dans : sa partie entière désignera le numéro du côté, tandis que sa partie fractionnaire fournira la coordonnée variable sur ce côté, ce qui conduit à l'algorithme 48 :

Une exécution avec nous a donné des valeurs de contenues dans , ce qui commence à approcher correctement le résultat . Les scores obtenus se répartissent selon l'histogramme de la figure 3.2.

Figure 3.2: Aires de 2000 triangles inscrits dans le carré.

On a donc un résultat bien meilleur que par le précédent algorithme. Mais, à nouveau, une simple augmentation de n'améliorera pas significativement le résultat obtenu. On constate que . Autrement dit, des résultats seront en dessous de , valeur elle-même significativement en dessous du meilleur score atteint.

3.3.3 Exploration locale dirigée

Nous allons maintenant décrire un processus d'apprentissage, qui consiste à modifier successivement chaque coordonnée et à ne conserver que les modifications qui améliorent le score. Appelons la valeur actuelle de cette coordonnée, et la valeur à essayer (et qui deviendra donc la nouvelle valeur si l'essai est concluant). Ces coordonnées appartiennent à l'intervalle réel mais nous allons plutôt les interpréter comme des réels modulo , autrement dit considérer que nous déplaçons les sommets sur un tore plutôt qu'à l'intérieur d'un carré.

Soit alors une variable aléatoire uniformément répartie sur . Pour fixé, la quantité est à son tour uniformément répartie sur et l'information issue des essais précédents est perdue. Si nous fixons une constante , la quantité reste confinée dans un "segment" centré sur , de largeur . Si donc x était au voisinage de la valeur voulue, le nouvel essai aura lieu lui aussi au voisinage de la valeur voulue, et donc pas tout à fait en aveugle.

Dans la procédure gradient décrite ci-dessous (algorithme 49), le paramètre est le nombre total d'essais à faire, tandis que le résultat est le nombre de succès. Les autres résultats sont , qui est le meilleur score obtenu et , la liste des 6 coordonnées correspondantes. La procédure commence par initialiser , et , puis procède aux tentatives. La variable parcourt cycliquement l'intervalle et contient le numéro de la coordonnée que l'on va tenter de modifier, tandis que la procédure auxiliaire calcule la valeur absolue de à partir d'une liste.

La table ci-dessous donne les résultats de trois simulations, pour et diverses valeurs de . Le fait que ces trois simulations n'ait pas convergé vers le même résultat est normal. En effet le maximum est atteint lorsque deux sommets du triangle sont des sommets du carré et que le dernier sommet du triangle est sur le côté opposé du carré.

On comprendra aisément que, dans cette méthode, le choix de est crucial. Pour trop grand, on ne conserve pas assez d'informations d'un essai sur l'autre et le nombre de succès est faible. Pour trop petit, le nombre de succès augmente, mais on n'arrive pas à se déplacer suffisamment dans le temps imparti.

3.3.4 Tétraèdre contenu dans un cube

Les techniques précédentes s'appliquent sans grand changement au problème suivant : on se donne un cube fixé et l'on cherche à déterminer le tétraèdre contenu dans le cube et réalisant le plus grand volume possible. Définissons le score d'un tétraèdre comme étant :

La figure 3.3(a) donne l'histogramme des scores obtenus pour tétraèdres dont les sommets sont uniformément situés dans le volume du cube. La figure 3.3(b) donne les scores pour le même nombre de tétraèdres uniformément situés à la surface du cube.

Figure 3.3: Scores des tétraèdres inclus et inscrits dans un cube donné.

[contenus dans le cube.][inscrits dans le cube.]

On constate que les deux premiers algorithmes sont bien moins efficaces que pour les triangles. Ce qui s'explique par le fait qu'il y a désormais 12 coordonnées à déterminer et non plus 6 : les n-uplets donnant des scores proches du maximum sont rares. Dans la simulation dont nous rendons compte, nous avons obtenu pour les tétraèdres contenus, et pour les tétraèdres inscrits. Par contre, le troisième algorithme donne une approximation acceptable du résultat. Avec et on trouve avec

Un raisonnement géométrique élémentaire permet de vérifier que le score maximal vaut et est atteint pour chacun des deux tétraèdres réguliers inscrits dans le cube. On remarquera que les deux types d'algorithmes, Monte-Carlo (couverture uniforme) et apprentissage (gradient) sont complémentaires. Une couverture uniforme permet de détecter toutes les zones où le maximum peut être atteint, tandis que la méthode de gradient permet d'accélérer le calcul d'un maximum local.