Wilson's algoritme: complete gids, verschillen met EOQ en de stelling

Informatec Digital » Engineering » Wilsons algoritme: complete handleiding, verschillen met EOQ en de stelling

Op internet wordt de term "Wilson" voor veel verschillende dingen gebruikt, wat nogal verwarrend is: er is Wilsons algoritme voor het genereren van doolhoven, het Wilson-voorraadmodel (of EOQ) en Wilsons stelling in de getaltheorie. In dit artikel verduidelijken we alles, te beginnen met het oorspronkelijke gebruik in doolhoven en door de andere betekenissen zorgvuldig te onderscheiden, omdat ze niet hetzelfde zijn en niet op hetzelfde gebied van toepassing zijn.

Als je een demo of applet hebt gezien waarin een doolhof vanzelf "groeit", ben je waarschijnlijk al bekend met het algoritme van Wilson. Je hebt misschien ook wel eens gehoord van het Wilson-model voor het berekenen van de economische bestelhoeveelheid of zelfs van de stelling die priemgetallen karakteriseert met behulp van faculteiten. Hier vind je een complete uitleg met voorbeelden, zodat je elk concept kunt herkennen en correct kunt toepassen.

Wat is Wilsons algoritme voor doolhoven?

Het algoritme van Wilson is een methode voor het genereren van doolhoven gebaseerd op lusverwijderende willekeurige wandelingen. Het belangrijkste voordeel is dat het een uniforme willekeurige opspannende boom over het hele raster produceert: simpel gezegd, elk mogelijk doolhof verschijnt met dezelfde waarschijnlijkheid , zonder voorkeur voor specifieke richtingen of patronen.

Het kernidee is dat paden aan het bestaande netwerk worden toegevoegd, maar wanneer een willekeurig pad zichzelf kruist, wordt de lus "verwijderd" en loopt de route verder vanaf het punt waar deze vrijkwam. Dit detail voorkomt dat het proces overbodige lange paden bevoordeelt of cycli creëert, waardoor de structuur als een boom behouden blijft die alle cellen met elkaar verbindt. Het resultaat is een "eerlijk" doolhof: geen enkel pad of bocht heeft een statistisch voordeel ten opzichte van een ander.

Er zijn door de community gemaakte projecten en applets die het algoritme op een visuele en vermakelijke manier in actie laten zien. Een aantal applets van Cruz Godar springen eruit, waarbij je de rastergrootte kunt kiezen en het programma kunt uitvoeren om te zien hoe het doolhof stap voor stap ontstaat. Door het programma te bekijken, begrijp je beter waarom het wissen van lussen de waarschijnlijkheden bij elke uitbreiding van de grafiek gelijk trekt.

Het bouwen en oplossen van doolhoven, hoewel het op het eerste gezicht op spelletjes lijkt, is nauw verbonden met zoek- en optimalisatieproblemen. Het ontwerpen ervan vereist een balans tussen duidelijkheid en intrige, waarbij triviale oplossingen of onmogelijke doodlopende wegen worden vermeden; het verkennen van een eindige ruimte met talloze combinaties. Daarom dienen ze, zowel op papier als in digitale simulaties, als uitstekende oefeningen in logica, waarschijnlijkheid en geduld.

Hoe het werkt (in de praktijk)

Hieronder volgt een algemene beschrijving van het algoritme, zonder code maar met de essentiële mechanismen om het gedrag ervan te begrijpen. Onthoud dat het doel is om een ​​boom (zonder cycli) te bouwen die alle cellen verbindt, zodat er slechts één eenvoudig pad is tussen twee willekeurige punten.

• Het begint met een leeg raster: er wordt willekeurig een cel gekozen en gemarkeerd als onderdeel van de boom.
• Er wordt willekeurig een andere cel gekozen, er wordt een stapsgewijze willekeurige wandeling gestart en als het pad zichzelf kruist, worden de lussen onmiddellijk verwijderd (lus-verwijdering).
• Wanneer de wandeling de reeds gegenereerde boom bereikt, wordt het gehele verfijnde pad (zonder lussen) aan de boom “gelijmd”.
• Het herhaalt zich: we kiezen een nieuwe, niet-verbonden cel, lopen door de lus heen met verwijdering en voegen ons bij de boom.
• Uiteindelijk zijn alle cellen met elkaar verbonden en is het doolhof een uniforme, willekeurige overspannende boom, dus er zijn geen richting- of topologische vertekeningen.

Vergeleken met andere methoden (zoals Aldous-Broder, Prim of Kruskal aangepast aan doolhoven) onderscheidt Wilson zich door de uniformiteit van de steekproefname van de opspannende boom. De rekenkosten zijn redelijk op typische roosters en, belangrijker nog, de methode garandeert dat elke oplossing even waarschijnlijk is , iets wat zeer gewaardeerd wordt in academische en simulatiecontexten.

Andere betekenissen: Wilson Model of EOQ (inventarissen)

In de logistiek heeft het Wilson-model (ook wel EOQ, Economic Order Quantity genoemd) niets met doolhoven te maken. Het is een klassieke methode om de optimale bestelhoeveelheid te bepalen om de totale voorraadkosten te minimaliseren. Het model werd in 1934 populair gemaakt door R.H. Wilson, hoewel het oorspronkelijke concept al in 1913 door Ford Whitman Harris werd voorgesteld.

Het doel is om de optimale ordergrootte Q te vinden die de kosten van het plaatsen van bestellingen en de kosten van het aanhouden van voorraad in evenwicht brengt. Op basis van de jaarlijkse vraag (D), de kosten per bestelling (K) en de opslagkosten per eenheid per periode (G) wordt een hoeveelheid berekend die, binnen de gegeven aannames, de totale voorraadkosten verlaagt.

De meest gebruikte formule luidt Q = √(2·D·K/G). Dit getal geeft de grootte van elke batch; daaruit volgt het aantal jaarlijkse bestellingen, namelijk D/Q, waarmee de bestelcyclus kan worden afgeleid. Het is ook belangrijk om het herbestelpunt (rekening houdend met de levertijd) en de veiligheidsvoorraad vast te stellen om voorraadtekorten te voorkomen, hoewel de basisformule onzekerheid niet expliciet meeneemt.

Typische toepassingen: Het wordt gebruikt met grondstoffen of elk type handelswaar waarvan de inkoop- en opslagkosten betrouwbaar kunnen worden vastgesteld. In de praktijk kan een bedrijf, door D, K en G met voldoende betrouwbaarheid te kennen, de batchgroottes bepalen en de inkoop beter plannen.

Veronderstellingen, voordelen en beperkingen van het Wilson-model

De aannames zijn cruciaal voor de geldigheid van het resultaat. Het EOQ-model gaat ervan uit dat de vraag constant en bekend is, dat de eenheidsprijs stabiel blijft, dat de opslagkosten bekend zijn en afhangen van het voorraadniveau, dat de levertijden constant zijn en houdt bovendien geen rekening met volumekortingen.

• Stabiele, onafhankelijke vraag, zonder seizoensgebondenheid of plotselinge pieken.
• Aankoopprijs vast of nagenoeg ongewijzigd gedurende de geanalyseerde periode.
• Bekende opslagkosten per eenheid en periode.
• Geen kwantumkortingen en directe of constante aanvulling.

Belangrijkste voordelen: Het is eenvoudig te implementeren, wordt veel gebruikt en helpt de bestel- en voorraadkosten te minimaliseren. Voordelen zijn onder andere minder overbevoorrading, een lager risico op voorraadtekorten (in combinatie met een nabestelpunt en veiligheidsvoorraad) en meer duidelijkheid bij de inkoopplanning. Veel organisaties waarderen het omdat het een eenvoudige numerieke basis biedt voor het bepalen van bestelhoeveelheden.

Nadelen: Het werkt niet goed bij seizoensgebonden of onregelmatige vraag, negeert volumekortingen en gaat uit van onmiddellijke (of vaste) aanvulling, wat in veel toeleveringsketens onrealistisch is. Daarom is de EOQ-formule in omgevingen zoals de Toyota-groep vervangen door robuustere systemen zoals Kanban of Just-in-Time, die beter omgaan met daadwerkelijke variabiliteit en continue doorstroming.

Praktische voorbeelden van de EOQ (Wilson)

Voorbeeld 1 (typisch): Een bedrijf met een jaarlijkse productie van 10.000 eenheden koopt 1.000 kg grondstof in. Als elke bestelling € 200 kost en de totale jaarlijkse opslagkosten € 2.000 bedragen, levert de formule Q = √(2·D·K/G) met D=1.000, K=200 en G=2.000 een Q ≈ 14,14 op. Dit suggereert batches van 14 kg en ongeveer 71 bestellingen per jaar. Het is een illustratieve oefening waarbij we met bescheiden aantallen kunnen zien hoe de batchgrootte de balans tussen bestellingen en voorraad beïnvloedt.

Voorbeeld 2: Sillas Grandes World SL distribueert 6.000 stoelen (D), elke bestelling kost €300 (K), en de jaarlijkse opslagkosten per eenheid bedragen €5 (G). Door de vergelijking toe te passen, krijgen we Q ≈ 848,52, wat betekent dat het bedrijf jaarlijks ongeveer 7,07 bestellingen zou plaatsen. Met deze ordergrootte streeft het bedrijf naar een efficiënter voorraadniveau , waardoor de opslagkosten worden verlaagd zonder dat de kosten voor ordervoorbereiding significant toenemen.

Naast de formule zelf is het raadzaam om het bestelpunt te berekenen rekening houdend met de levertijd en een veiligheidsvoorraad aan te houden, omdat het pure model geen rekening houdt met onzekerheid. Het schat ook niet de impact van volumekortingen in, die soms de voorraadkosten kunnen compenseren bij grotere afnamehoeveelheden.

Niet te verwarren met de stelling van Wilson (getallentheorie)

De stelling van Wilson behoort tot de modulaire rekenkunde en stelt in essentie dat een geheel getal n > 1 priem is als en slechts als (n − 1)! ≡ −1 (mod n). De implicatie "als n priem is, dan is (n − 1)! ≡ −1 (mod n)" wordt meestal strikt "de stelling van Wilson" genoemd, en de omgekeerde implicatie is ook waar. Historisch gezien schreef Edward Waring het resultaat toe aan John Wilson (1770), hoewel het eerste bekende bewijs werd geleverd door Lagrange (1771), en de formulering feitelijk teruggaat tot Alhazen in de 11e eeuw.

Een concreet voorbeeld: voor p = 11, door elk element te groeperen met zijn multiplicatieve inverse in de verzameling {1, 2, …, p − 1}, is het totale product ≡ −1 (mod p). Alle factoren heffen elkaar paarsgewijs op omdat g·g^{-1} ≡ 1, behalve 1 en p − 1, en daarom is 10! ≡ −1 (mod 11) . Deze aanpak maakt gebruik van het feit dat, met p priem, (Z/pZ)^× een multiplicatieve groep is en elk element (behalve 1 en p − 1) een verschillende inverse heeft.

Er zijn verschillende bewijzen. Eén polynoomtechniek beschouwt g(x) = (x − 1)(x − 2)···(x − (p − 1)) en f(x) = g(x) − (x^{p−1} − 1). Modulo p zou f(x) maximaal p − 2 wortels hebben als het niet de nulpolynoom was, maar alle 1, 2, …, p − 1 maken f(x) nul volgens de Kleine Stelling van Fermat. Daarom is f(x) identiek 0 modulo p; de constante term leidt tot (p − 1)! ≡ −1 (mod p).

Het wordt niet gebruikt als een praktische test voor primaliteit, omdat het berekenen van (n − 1)! mod n voor grote n kostbaar is, en er snellere tests bestaan ​​(zoals Miller-Rabin of deterministische tests voor specifieke rangen). Desondanks kan het worden gebruikt om nuttige eigenschappen af ​​te leiden: bijvoorbeeld, als p = 2n + 1 een priemgetal is, verkrijgen we ∏_{j=1}^{n} j^2 ≡ (−1)^{n+1} (mod p). En, als gedeeltelijk gevolgtrekking, is −1 een kwadratisch residu modulo p als p ≡ 1 (mod 4), aangezien het kan worden geschreven als het kwadraat van het product 1·2···2k wanneer p = 4k + 1, wat blijkt wanneer −1 wordt gekwadrateerd in Z/pZ.

Er bestaat ook een praktische "omgekeerde": voor elk samengesteld getal n > 5 geldt dat n (n − 1)! deelt. Het geval n = 4 is de klassieke uitzondering (3! is geen veelvoud van 4). Een manier om dit te zien is door de machten van een priemgetal q te tellen die n delen: in (n − 1)! zijn er genoeg veelvouden van q om de macht die in n voorkomt te dekken, behalve in de genoemde uitzondering, wat leidt tot het resultaat behalve voor n = 4.

Gauss generaliseerde de stelling: het product van alle eenheden modulo n, ∏_{1≤a<n, (a,n)=1} a, is ≡ −1 (mod n) als n ∈ {4, p^k, 2p^k} met p een oneven priemgetal, en ≡ 1 (mod n) in alle andere gevallen. Vanuit het perspectief van eindige abelse groepen is het product van al hun elementen de identiteit, tenzij er precies één element van orde 2 bestaat, in welk geval het product dat element van orde 2 is.

Illustratieve tabel van (n − 1)! mod n voor n = 2…30

De volgende tabel toont specifieke waarden voor n tussen 2 en 30. Voor priemgetallen is de rest van (n − 1)! bij deling door n gelijk aan n − 1 (wat ≡ −1 mod n is). Voor samengestelde getallen is de rest vaak 0. −1 mod n is ook ter vergelijking opgenomen. Deze gegevens illustreren duidelijk hoe de stelling van Wilson zich gedraagt ​​in kleine gevallen en helpen de intuïtie te versterken.

Toepassingen, limieten en aanbevelingen

Als je onbevooroordeelde doolhoven wilt genereren, gebruik dan het algoritme van Wilson: de basis ervan in willekeurige wandelingen met lusverwijdering zorgt voor uniforme bomen. Voor voorraadbeheer is het Wilson-model nuttig wanneer de vraag, prijzen en kosten stabiel en precies bekend zijn; in volatiele omgevingen zijn methoden zoals Kanban, Just-in-Time of geavanceerde planningssoftware wellicht geschikter. En in de wiskunde is de stelling van Wilson een theoretisch juweeltje met interessante afleidingen (zoals kwadratische residuen), maar het is niet praktisch als primaliteitstest voor grote getallen.

Er bestaat geen eenduidige formule voor het berekenen van bestel- en opslagkosten: elk bedrijf moet de uren, processen, transport, ontvangst, personeel, huur, energie, verzekeringen en financiële kosten afzonderlijk bekijken. Veel professionals schatten de uren per bewerking en hanteren een uurtarief voor de berekening. Deze aanpassing is essentieel om ervoor te zorgen dat de berekende bestelhoeveelheid (Q) bruikbaar is en, samen met een goed nabestelpunt en een veiligheidsvoorraad, voorraadtekorten of overtollige voorraad helpt voorkomen.

Het is belangrijk te onthouden dat de term "Wilsons algoritme" bij zoekopdrachten meestal verwijst naar de doolhofgenerator, terwijl "Wilson-model" of "EOQ" betrekking heeft op inventarissen en "Wilsons stelling" op getaltheorie. Door ze vanaf het begin te onderscheiden, wordt verwarring voorkomen en kunt u elke aanpak beter benutten: onbevooroordeelde doolhoven, optimale batches onder realistische aannames en een elegante karakterisering van priemgetallen die, hoewel geen praktisch primaliteitsbewijs, een waardevol onderdeel van de wiskundige puzzel vormt.

Gerelateerd artikel:

Het algoritme van Kruskal en de toepassing ervan in grafieken