Wilsons algoritme: Komplet guide, forskelle med EOQ og sætningen

Informatic Digital » Engineering » Wilsons algoritme: Komplet guide, forskelle med EOQ og sætningen

På internettet bruger folk udtrykket "Wilson" til meget forskellige formål, og det er ret forvirrende: der er Wilson-algoritmen til generering af labyrinter, Wilson-modellen (eller EOQ) til opgørelser og Wilsons sætning i talteori. I denne artikel præciserer vi alt, startende med den oprindelige brug i labyrinter og omhyggeligt skelner mellem de andre betydninger, fordi De er ikke de samme, og de gælder heller ikke for det samme område.

Hvis du har set en demo eller applet, hvor en labyrint "vokser" af sig selv, har du sandsynligvis allerede stødt på Wilsons algoritme. Du har også hørt om Wilson-modellen til beregning af den økonomiske ordensmængde eller endda sætningen, der karakteriserer primtal ved hjælp af faktorialer. Her finder du en komplet forklaring med eksempler, så du kan du kan identificere hvert koncept og bruge det korrekt.

Hvad er Wilsons algoritme for labyrinter?

Wilsons algoritme er en labyrintgenereringsmetode baseret på loop-ereased random walks. Dens store fordel er, at den producerer et ensartet tilfældigt udspændende træ over gitteret: enkelt sagt, Hver mulig labyrint optræder med samme sandsynligheduden bias mod bestemte retninger eller mønstre.

Hovedideen er, at stier tilføjes til det allerede konstruerede sæt, men når en tilfældig vandring krydser sig selv, "slettes" løkken, og ruten fortsætter derfra, hvor den slap. Denne detalje forhindrer processen i at skabe lange, redundante stier eller løkker, og bevarer strukturen som et træ, der forbinder alle cellerne. Resultatet er en "fair" labyrint: ingen korridor eller drejning har en statistisk fordel frem for en anden.

Der findes projekter og applets skabt af fællesskabet, der viser algoritmen i aktion på en visuel og meget underholdende måde. Blandt dem skiller nogle applets fra Cruz Godar sig ud, hvor du kan vælge gitterstørrelsen og sætte den til at arbejde for at se, hvordan labyrinten dukker op trin for trin. At se den køre hjælper dig med at forstå hvorfor. Loop-sletning udligner oddsene i hver udvidelse af grafen.

Opbygning og løsning af labyrinter er opgaver, der, selvom de kan virke som spil, er tæt forbundet med søge- og optimeringsproblemer. Design af dem kræver en balance mellem klarhed og interesse, hvor trivielle løsninger eller blindgyder undgås; udforsk et begrænset rum med enorme kombinationer. Derfor fungerer de både på papir og i digitale simuleringer som Gode ​​øvelser i logik, sandsynlighed og tålmodighed.

Hvordan det fungerer (i praksis)

Nedenfor er en overordnet beskrivelse af algoritmen, uden kode, men med de essentielle mekanikker til at forstå dens adfærd. Husk at målet er at bygge et træ (uden cyklusser), der forbinder alle cellerne, således at der er kun én simpel sti mellem et hvilket som helst punktpar.

• Det starter med et tomt gitter: en celle vælges tilfældigt og markeres som en del af træet.
• En anden celle vælges tilfældigt, en trinvis tilfældig vandring startes, og hvis stien krydser sig selv, fjernes løkkerne øjeblikkeligt (løkkesletning).
• Når stien når det allerede genererede træ, "limes" hele den raffinerede sti (uden løkker) til træet.
• Det gentager sig: vi vælger en ny, uforbundet celle, går med løkkesletning og slutter os til træet.
• Til sidst er alle celler forbundet, og labyrinten er et ensartet, tilfældigt udspændende træ, så der er ingen retningsbestemte eller topologiske bias.

Sammenlignet med andre metoder (såsom Aldous-Broder, første eller Kruskal tilpasset labyrinter), skiller Wilson sig ud ved ensartetheden af ​​samplingen af ​​det genererende træ. Dens beregningsomkostninger er rimelige på typiske gitre og frem for alt, sikrer, at hver løsning er lige sandsynlig, noget der værdsættes højt i akademiske og simuleringsmæssige sammenhænge.

Andre betydninger: Wilson-model eller EOQ (opgørelser)

Inden for logistik har "Wilson-modellen" (også kaldet EOQ, Economic Order Quantity; eller CEP, Economic Order Quantity) intet at gøre med labyrinter. Det er en klassisk metode til at bestemme den optimale ordremængde med det mål at minimere de samlede lageromkostninger. Den blev populariseret i 1934 af R.H. Wilson, selvom Det første forslag var af Ford Whitman Harris i 1913..

Dens formål er at finde den partistørrelse Q, der afbalancerer bestillingsomkostningerne og lageromkostningerne. Ud fra den årlige efterspørgsel (D), omkostningerne pr. ordre (K) og lageromkostningerne pr. enhed og periode (G) opnås en mængde, der inden for rammerne af dens antagelser, reducerer de samlede lageromkostninger.

Den mest almindelige formel er Q = √(2 D K/G). Dette giver batchstørrelsen; derfra vil antallet af årlige ordrer være D/Q, og herfra kan du udlede tidskadencen. Det er også vigtigt at indstille genbestillingspunktet (under hensyntagen til leveringstiden) og sikkerhedslageret for at undgå lagermangel, selvom Grundformlen inkorporerer ikke usikkerhed eksplicit.

Typiske anvendelser: anvendes med råmaterialer eller enhver type vare, for hvilken indkøbs- og lageromkostninger kan bestemmes pålideligt. I praksis, hvis D, K og G er kendt med tilstrækkelig pålidelighed, Virksomheden kan dimensionere sine partier og planlægge deres levering med større kontrol.

Antagelser, fordele og begrænsninger ved Wilson-modellen

Antagelser er afgørende for resultaternes validitet. EOQ-modellen antager, at efterspørgslen er konstant og kendt, at enhedsprisen forbliver stabil, at lageromkostningerne er kendte og afhænger af lagerniveauet, at leveringstiderne er konstante, og desuden... overvejer ikke mængderabatter.

• Stabil, uafhængig efterspørgsel uden sæsonudsving eller pludselige toppe.
• Købsprisen er fast eller praktisk talt uændret i den analyserede periode.
• Kendte lageromkostninger pr. enhed og periode.
• Ingen mængderabatter og øjeblikkelig eller konstant genopfyldning.

Vigtigste fordele: Det er nemt at implementere, bruges i vid udstrækning og hjælper med at minimere bestillings- og lageromkostninger under dine forhold. Fordelene omfatter reduceret overlagerbeholdning, reduceret risiko for udsolgte varer (hvis det ledsages af et genbestillingspunkt og sikkerhedslager) og klarhed i indkøbsplanlægningen. Mange organisationer værdsætter det fordi tilbyder et simpelt numerisk grundlag for at bestemme, hvor meget der skal bestilles.

Ulemper: Det fungerer ikke godt med sæsonbestemt eller uregelmæssig efterspørgsel, ignorerer mængderabatter og antager øjeblikkelig (eller fast) genopfyldning, hvilket er urealistisk i mange forsyningskæder. Derfor er EOQ-formlen i miljøer som Toyota Group blevet erstattet af mere robuste systemer som Kanban eller Just in Time, som De håndterer reel variation bedre og den kontinuerlige strømning.

Praktiske eksempler på EOQ (Wilson)

Eksempel 1 (typisk): En virksomhed med en årlig produktion på 10.000 enheder køber 1.000 kg råmateriale. Hvis hver ordre koster €200, og de samlede årlige lageromkostninger er €2.000, giver anvendelse af formlen Q = √(2 D K/G) med D = 1.000, K = 200, G = 2.000 Q ≈ 14,14. Dette antyder partier på 14 kg og cirka 71 ordrer om året. Dette er en illustrativ øvelse, hvor vi med beskedne tal kan se Hvordan lotstørrelsen afbalancerer ordrer og lagerbeholdning.

Eksempel 2: Sillas Grandes World SL distribuerer 6.000 stole (D), hver ordre koster €300 (K), og lagerplads pr. enhed pr. år er €5 (G). Ved at anvende ligningen Q ≈ 848,52 ville firmaet foretage cirka 7,07 ordrer pr. år. Med denne partistørrelse vil firmaet tenderer mod et mere effektivt lagerniveau, hvilket reducerer lageromkostninger uden at øge omkostningerne til ordreforberedelse.

Ud over formlen er det en god idé at beregne genbestillingspunktet under hensyntagen til leveringstiden og opretholdelsen af ​​sikkerhedslageret, fordi den rene model ikke tager højde for usikkerhed. Den estimerer heller ikke effekten af ​​mængderabatter, som nogle gange kunne udligne lageromkostninger hvis større partier anvendes.

Ikke at forveksle med Wilsons sætning (talteori)

Wilsons sætning tilhører modulær aritmetik og siger i bund og grund, at et heltal n > 1 er primt hvis og kun hvis (n − 1)! ≡ −1 (mod n). Implikationen "hvis n er primt, så kaldes (n − 1)! ≡ −1 (mod n)" ofte strengt taget "Wilsons sætning", og den omvendte implikation er også sand. Historisk set tilskrev Edward Waring resultatet til John Wilson (1770), selvom det første kendte bevis blev givet af Lagrange (1771), og faktisk, Formuleringen stammer fra Alhacen i det 11. århundrede.

Konkret eksempel: for p = 11, når hvert element grupperes med dets multiplikative inverse i mængden {1, 2, …, p − 1}, bliver det samlede produkt ≡ −1 (mod p). Alle faktorer ophæver hinanden ligeligt, da g g^{-1} ≡ 1, undtagen 1 og p − 1, og derfor 10! ≡ −1 (mod 11)Denne tilgang bruger, at med p-primtal er (Z/pZ)^× en multiplikativ gruppe, og hvert element (undtagen 1 og p − 1) har en distinkt invers.

Der er flere beviser. Én polynomteknik betragter g(x) = (x − 1)(x − 2)···(x − (p − 1)) og f(x) = g(x) − (x^{p−1} − 1). Modul p, f(x) ville højst have p − 2 rødder, hvis det ikke var nulpolynomiet, men alle 1, 2, …, p − 1 forsvinder fra f(x) ved Fermats lille sætning. Derfor er f(x) identisk 0 mod p, og det uafhængige led fører til (p − 1)! ≡ −1 (mod p).

Den bruges ikke som en praktisk primalitetstest, fordi det er dyrt at beregne (n − 1)! mod n for store n, og der findes hurtigere tests (såsom Miller-Rabin eller deterministiske tests for specifikke intervaller). Alligevel er det nyttigt at udlede nyttige egenskaber: for eksempel, hvis p = 2n + 1 er et primtal, så har vi ∏_{j=1}^{n} j^2 ≡ (−1)^{n+1} (mod p). Og som en delvis korollar er −1 en kvadratisk rest modulo p, hvis p ≡ 1 (mod 4), da den kan skrives som kvadratet af produktet 1 2 2k, når p = 4k + 1, hvilket viser, når −1 er kvadratisk i Z/pZ.

Der er også en praktisk "invers": for ethvert sammensat n > 5 gælder det, at n dividerer (n − 1)!. Tilfældet n = 4 er den klassiske undtagelse (3! er ikke et multiplum af 4). En måde at se dette på er at tælle potenserne af et primtal q, der dividerer n: i (n − 1)! er der nok multipla af q til at dække den potens, der optræder i n, bortset fra den angivne undtagelse, som fører til resultatet, bortset fra at n = 4.

Gauss generaliserede sætningen: produktet af alle enheder modulo n, ∏_{1≤a Det er det element af orden 2.

Illustrativ tabel af (n − 1)! mod n for n = 2…30

I den følgende tabel kan du se specifikke værdier for n mellem 2 og 30. For n, der er primtal, er resten af ​​(n − 1)!, når den divideres med n, lig med n − 1 (som er ≡ −1 mod n). I kompositter er resten ofte 0. −1 mod n er også inkluderet til sammenligning. Disse data illustrerer meget godt, hvordan Wilsons sætning opfører sig i små tilfælde og hjælper med at fiks intuition.

n > 1	(n − 1)!	(n − 1)! mod n	−1 mod n
2	1	1	1
3	2	2	2
4	6	2	3
5	24	4	4
6	120	0	5
7	720	6	6
8	5040	0	7
9	40320	0	8
10	362880	0	9
11	3628800	10	10
12	39916800	0	11
13	479001600	12	12
14	6227020800	0	13
15	87178291200	0	14
16	1307674368000	0	15
17	20922789888000	16	16
18	355687428096000	0	17
19	6402373705728000	18	18
20	121645100408832000	0	19
21	2432902008176640000	0	20
22	51090942171709440000	0	21
23	1124000727777607680000	22	22
24	25852016738884976640000	0	23
25	620448401733239439360000	0	24
26	15511210043330985984000000	0	25
27	403291461126605635584000000	0	26
28	10888869450418352160768000000	0	27
29	304888344611713860501504000000	28	28
30	8841761993739701954543616000000	0	29

Anvendelser, begrænsninger og anbefalinger

Hvis du ønsker at generere objektive labyrinter, skal du bruge Wilsons algoritme: dens grundlag i tilfældige vandringer med loop-sletning sikrer ensartede træer. Til varebeholdninger er Wilson-modellen nyttig, når efterspørgsel, priser og omkostninger er stabile og præcist kendte; i ustabile miljøer kan metoder som Kanban, JIT eller avanceret planlægningssoftware være mere passende. Og i matematik er Wilsons sætning en teoretisk perle med interessante afledninger (såsom kvadratiske residuer), men Det er ikke praktisk som en primalitetstest for store tal.

Der findes ingen universel formel til beregning af bestillings- og lageromkostninger: Hver virksomhed skal opdele timer, processer, transport, modtagelse, personale, husleje, energi, forsikring og finansielle omkostninger. Mange fagfolk estimerer timer pr. operation og anvender en timepris for at tjene penge. Denne tilpasning er nøglen til at gøre den beregnede Q nyttig, og sammen med et godt genbestillingspunkt og sikkerhedslager, undgå udsolgte eller overskydende lagerbeholdning.

Det er værd at huske, at udtrykket "Wilsons algoritme" i søgninger normalt refererer til labyrintgeneratoren, mens "Wilsons model" eller "EOQ" refererer til opgørelser, og "Wilsons sætning" refererer til talteori. Ved at skelne mellem dem fra starten undgår du forvirring og giver dig mulighed for bedre at udnytte hver tilgang: Upartiske labyrinter, optimale batcher under realistiske antagelser og en elegant karakterisering af primtal som, selvom det ikke er en praktisk primalitetstest, stadig er en værdifuld brik i det matematiske puslespil.