Algorithme du British Museum

Un article de Wikipédia, l'encyclopédie libre.

L'algorithme du British Museum est une approche générale qui vise à trouver une solution à un problème en cherchant toutes les possibilités les unes après les autres, en commençant par les plus petites. Le terme se réfère à un concept, plutôt qu'à une technique pratique pour des problèmes où le nombre de possibilités est énorme.

Par exemple, on peut en théorie trouver le plus petit programme qui résout un problème particulier de la façon suivante: Générer tous les codes sources possibles de la longueur d'un octet. On les vérifie ensuite chacun afin de vérifier si le problème est résolu par le code source. Tester ces programmes peut éventuellement poser des problèmes, comme des boucles infinies, etc. Si les programmes ne marchent pas, on génère et on vérifie tous les programmes de longueur de deux octets, puis trois octets, etc. Conceptuellement, cet algorithme permet de trouver le plus petit programme mais en pratique il tend à prendre un temps d'exécution inacceptable pour certains problèmes.

Cet algorithme est devenu un clin d'œil dans le milieu informatique lorsque l'on parle d'un très mauvais algorithme pour un problème donné basé sur le calcul de toutes les solutions^{[réf. nécessaire]}. Par exemple en synthèse d'image un algorithme du British Museum pour calculer la radiosité dans une scène 3D consisterait pour chaque source lumineuse à calculer tous les rayons s'en échappant en échantillonant l'espace autour de la source. Pour chaque point touché par les rayons lumineux on calcule tous les rayons réémis et ainsi de suite jusqu'à ce que les éclairages soient calculés en tout point de la scène.

• Portail de l’informatique