Algorithme de Wilson : guide complet, différences avec EOQ et le théorème

Informatec Digital » ingénierie » Algorithme de Wilson : guide complet, différences avec EOQ et le théorème

Sur Internet, le terme « Wilson » est utilisé à des fins très diverses, ce qui prête à confusion : il existe l'algorithme de Wilson pour générer des labyrinthes, le modèle de Wilson (ou EOQ) pour les inventaires et le théorème de Wilson en théorie des nombres. Dans cet article, nous clarifions tout, en commençant par l'utilisation originale dans les labyrinthes et en distinguant soigneusement les autres significations, car Ils ne sont pas identiques et ne s’appliquent pas au même domaine..

Si vous avez vu une démonstration ou une applet où un labyrinthe « grandit » tout seul, vous avez probablement déjà rencontré l'algorithme de Wilson. Vous avez également entendu parler du modèle de Wilson pour le calcul de la quantité d'ordre économique, ou encore du théorème caractérisant les nombres premiers à l'aide des factorielles. Vous trouverez ici une explication complète avec des exemples, pour que vous puissiez vous pouvez identifier chaque concept et l'utiliser correctement.

Quel est l'algorithme de Wilson pour les labyrinthes ?

L'algorithme de Wilson est une méthode de génération de labyrinthes basée sur des marches aléatoires à boucles effacées. Son principal avantage est de produire un arbre couvrant aléatoire uniforme sur la grille : en termes simples, Chaque labyrinthe possible apparaît avec la même probabilité, sans préjugés envers des directions ou des modèles spécifiques.

L'idée clé est que les chemins sont ajoutés à l'ensemble déjà construit, mais lorsqu'une marche aléatoire se croise, la boucle est supprimée et l'itinéraire reprend là où il s'était arrêté. Ce détail empêche le processus de créer des chemins ou des boucles longs et redondants, préservant ainsi la structure arborescente reliant toutes les cellules. Le résultat est un labyrinthe « correct » : aucun couloir ou virage n'a d'avantage statistique sur un autre.

Il existe des projets et des applets créés par la communauté qui montrent l'algorithme en action de manière visuelle et très divertissante. Parmi eux, certaines applets de Cruz Godar se distinguent : vous pouvez choisir la taille de la grille et la configurer pour voir le labyrinthe émerger étape par étape. L'observer vous permettra de comprendre pourquoi. L'effacement de la boucle égalise les chances dans chaque extension du graphe.

Construire et résoudre des labyrinthes est une tâche qui, bien qu'apparente à un jeu, est étroitement liée aux problèmes de recherche et d'optimisation. Leur conception exige un équilibre entre clarté et intérêt, en évitant les solutions triviales ou les impasses. explorer un espace fini avec d'énormes combinaisons. Par conséquent, tant sur papier que dans les simulations numériques, ils fonctionnent comme Excellents exercices de logique, de probabilité et de patience.

Comment cela fonctionne (en termes pratiques)

Vous trouverez ci-dessous une description détaillée de l'algorithme, sans code, mais avec les mécanismes essentiels pour comprendre son fonctionnement. Rappelons que l'objectif est de construire un arbre (sans cycles) reliant toutes les cellules, de telle sorte que il n'y a qu'un seul chemin simple entre n'importe quelle paire de points.

• Tout commence avec une grille vide : une cellule est choisie au hasard et marquée comme faisant partie de l'arbre.
• Une autre cellule est choisie au hasard, une marche aléatoire étape par étape est lancée et si le chemin se croise, les boucles sont immédiatement supprimées (effacement de boucle).
• Lorsque le parcours atteint l’arbre déjà généré, l’ensemble du chemin raffiné (sans boucles) est « collé » à l’arbre.
• Cela se répète : nous choisissons une nouvelle cellule non connectée, marchons avec la suppression de boucle et rejoignons l'arbre.
• Au final, toutes les cellules sont connectées et le labyrinthe est un arbre couvrant aléatoire uniforme, donc il n'y a pas de biais directionnels ou topologiques.

Par rapport à d’autres méthodes (telles que Aldous–Broder, prime (ou Kruskal adapté aux labyrinthes), Wilson se distingue par l'uniformité de l'échantillonnage de l'arbre générateur. Son coût de calcul est raisonnable sur des grilles classiques et, surtout, garantit que chaque solution est également probable, quelque chose de très apprécié dans les contextes académiques et de simulation.

Autres significations : Modèle Wilson ou EOQ (inventaires)

En logistique, le « modèle Wilson » (également appelé QEO, Quantité Économique de Commande, ou QEC, Quantité Économique de Commande) n'a rien à voir avec les labyrinthes. Il s'agit d'une méthode classique permettant de déterminer la quantité optimale à commander afin de minimiser les coûts totaux de stock. Il a été popularisé en 1934 par R.H. Wilson, bien que La première proposition fut celle de Ford Whitman Harris en 1913.

Son objectif est de déterminer la taille du lot Q qui équilibre le coût de commande et le coût de stockage. À partir de la demande annuelle (D), du coût par commande (K) et du coût de stockage par unité et par période (G), on obtient une quantité qui, dans le cadre de ses hypothèses, réduit le coût total des stocks.

La formule la plus courante est Q = √(2 D K/G). Elle donne la taille du lot ; à partir de là, le nombre de commandes annuelles sera D/Q, et on peut en déduire la cadence. Il est également important de définir le point de commande (en tenant compte du délai) et le stock de sécurité pour éviter les ruptures de stock, bien que la formule de base n'intègre pas l'incertitude explicitement.

Applications courantes : utilisées avec des matières premières ou tout type de marchandise pour laquelle les coûts d'achat et de stockage peuvent être déterminés de manière fiable. En pratique, si D, K et G sont connus avec une fiabilité suffisante, L'entreprise peut dimensionner ses lots et programmer leur approvisionnement avec un meilleur contrôle.

Hypothèses, avantages et limites du modèle Wilson

Les hypothèses sont essentielles à la validité des résultats. Le modèle EOQ suppose que la demande est constante et connue, que le prix unitaire reste stable, que les coûts de stockage sont connus et dépendent du niveau des stocks, que les délais d'approvisionnement sont constants et, de plus, ne prévoit pas de remises sur volume.

• Demande stable et indépendante, sans saisonnalité ni pics soudains.
• Prix ​​d’achat fixe ou pratiquement inchangé durant la période analysée.
• Coûts de stockage connus par unité et par période.
• Aucune remise quantitative et réapprovisionnement immédiat ou constant.

Principaux avantages : sa mise en œuvre est simple, son utilisation est répandue et il permet de minimiser les coûts de commande et de gestion des stocks selon vos conditions. Parmi ses avantages, on compte la réduction des surstocks, la diminution des risques de ruptures de stock (si elle est assortie d'un point de commande et d'un stock de sécurité) et la clarté de la planification des achats. De nombreuses organisations l'apprécient car offre une base numérique simple pour décider de la quantité à commander.

Inconvénients : Cette méthode est peu adaptée aux demandes saisonnières ou irrégulières, ignore les remises sur volume et suppose un réapprovisionnement immédiat (ou fixe), ce qui est irréaliste dans de nombreuses chaînes d'approvisionnement. Par conséquent, dans des environnements comme celui du groupe Toyota, la formule de la quantité de commande finale a été remplacée par des systèmes plus robustes comme Kanban ou le juste-à-temps, qui Ils gèrent mieux la variabilité réelle et le flux continu.

Exemples pratiques de l'EOQ (Wilson)

Exemple 1 (typique) : Une entreprise produisant 10 000 unités par an achète 1 000 kg de matières premières. Si chaque commande coûte 200 € et que le coût total annuel de stockage est de 2 000 €, l'application de la formule Q = √(2 D K/G) avec D = 1 000, K = 200, G = 2 000 donne Q ≈ 14,14. Cela suppose des lots de 14 kg et environ 71 commandes par an. Cet exercice d'illustration montre, avec des effectifs modestes, que nous pouvons observer. Comment la taille du lot équilibre les commandes et les stocks.

Exemple 2 : Sillas Grandes World SL distribue 6 000 chaises (D), chaque commande coûte 300 € (K) et le stockage unitaire annuel est de 5 € (G). En appliquant l’équation Q ≈ 848,52, l’entreprise passerait environ 7,07 commandes par an. Avec cette taille de lot, l’entreprise tend vers un niveau de stock plus efficace, réduisant les coûts de stockage sans augmenter les coûts de préparation des commandes.

Au-delà de la formule, il est judicieux de calculer le point de commande en tenant compte du délai de livraison et du maintien du stock de sécurité, car le modèle pur ne prend pas en compte l'incertitude. Il n'estime pas non plus l'impact des remises sur volume, qui peuvent parfois pourrait compenser les coûts des stocks si des lots plus grands sont utilisés.

À ne pas confondre avec le théorème de Wilson (théorie des nombres)

Le théorème de Wilson appartient au arithmétique modulaire et affirme essentiellement qu'un entier n > 1 est premier si et seulement si (n − 1)! ≡ −1 (mod n). L'implication « si n est premier alors (n − 1)! ≡ −1 (mod n) » est souvent appelée, au sens strict, « théorème de Wilson », et la réciproque est également vraie. Historiquement, Edward Waring a attribué ce résultat à John Wilson (1770), bien que la première preuve connue ait été donnée par Lagrange (1771), et en fait, La formulation remonte à Alhacen au XIe siècle.

Exemple concret : pour p = 11, en regroupant chaque élément avec son inverse multiplicatif dans l'ensemble {1, 2, …, p − 1}, le produit total devient ≡ −1 (mod p). Tous les facteurs s'annulent uniformément lorsque g g^{-1} ≡ 1, sauf 1 et p − 1, et ainsi de suite. 10! ≡ −1 (mod 11)Cette approche part du principe que, avec p premier, (Z/pZ)^× est un groupe multiplicatif et que chaque élément (sauf 1 et p − 1) possède un inverse distinct.

Il existe plusieurs preuves. Une technique polynomiale considère que g(x) = (x − 1)(x − 2)···(x − (p − 1)) et f(x) = g(x) − (x^{p−1} − 1). Module p, f(x) aurait au plus p − 2 racines s'il n'était pas le polynôme nul, mais tous les 1, 2, …, p − 1 annulent f(x) par le petit théorème de Fermat. Ainsi, f(x) est identique à 0 modulo p et le terme indépendant conduit à (p − 1)! ≡ −1 (mod p).

Il n'est pas utilisé comme test de primalité pratique, car calculer (n − 1)! mod n pour un grand n est coûteux et il existe des tests plus rapides (tels que Miller-Rabin ou des tests déterministes pour des plages spécifiques). Néanmoins, il est utile de déduire des propriétés utiles : par exemple, si p = 2n + 1 est premier, alors on a ∏_{j=1}^{n} j^2 ≡ (−1)^{n+1} (mod p). Et, en corollaire partiel, −1 est un résidu quadratique modulo p si p ≡ 1 (mod 4), car il peut s'écrire comme le carré du produit 1 2 2k lorsque p = 4k + 1, ce qui montre quand −1 est carré en Z/pZ.

Il existe aussi une « inverse » pratique : pour tout composé n > 5, il est vrai que n divise (n − 1)!. Le cas n = 4 est l'exception classique (3! n'est pas un multiple de 4). Une façon de le voir est de compter les puissances d'un nombre premier q qui divisent n : dans (n ​​− 1)!, il y a suffisamment de multiples de q pour couvrir la puissance qui apparaît dans n, sauf dans l'exception indiquée, qui conduit au résultat sauf pour n = 4.

Gauss a généralisé le théorème : le produit de toutes les unités modulo n, ∏_{1≤a C'est cet élément d'ordre 2.

Tableau illustratif de (n − 1)! mod n pour n = 2…30

Le tableau suivant présente des valeurs spécifiques pour n entre 2 et 30. Pour un nombre premier, le reste de (n − 1)! divisé par n est égal à n − 1 (soit ≡ −1 mod n). Dans les nombres composés, le reste est souvent nul. −1 mod n est également inclus à titre de comparaison. Ces données illustrent très bien le comportement du théorème de Wilson dans les cas restreints et aident à… corriger l'intuition.

Applications, limites et recommandations

Si vous cherchez à générer des labyrinthes non biaisés, utilisez l'algorithme de Wilson : son principe de marches aléatoires avec suppression de boucles garantit des arbres uniformes. Pour les stocks, le modèle de Wilson est utile lorsque la demande, les prix et les coûts sont stables et connus avec précision ; dans des environnements volatils, des méthodologies telles que Kanban, JIT ou des logiciels de planification avancés peuvent être plus appropriées. En mathématiques, le théorème de Wilson est un joyau théorique offrant des dérivations intéressantes (comme les résidus quadratiques), mais Ce n’est pas pratique comme test de primalité pour les grands nombres.

Il n'existe pas de formule universelle pour calculer les coûts de commande et de stockage : chaque entreprise doit ventiler les heures, les processus, le transport, la réception, le personnel, le loyer, l'énergie, les assurances et les coûts financiers. De nombreux professionnels estiment les heures par opération et appliquent un taux horaire pour les monétiser. Cette personnalisation est essentielle pour rendre le Q calculé utile et, avec un bon point de commande et un stock de sécurité, éviter les ruptures de stock ou les excès de stock.

Il est important de rappeler que, dans les recherches, le terme « algorithme de Wilson » désigne généralement le générateur de labyrinthe, tandis que le « modèle de Wilson » ou « EOQ » désigne les inventaires, et le « théorème de Wilson » la théorie des nombres. Les distinguer dès le départ permet d'éviter toute confusion et de mieux exploiter chaque approche : Labyrinthes impartiaux, lots optimaux sous des hypothèses réalistes et une caractérisation élégante des nombres premiers ce qui, bien qu'il ne s'agisse pas d'un test de primalité pratique, reste une pièce précieuse du puzzle mathématique.

Article connexe:

L'algorithme de Kruskal et son application aux graphes