Wilsons algoritm: Komplett guide, skillnader med EOQ och teoremet

Informatec Digital » Teknik » Wilsons algoritm: Komplett guide, skillnader med EOQ och teoremet

På internet använder man termen "Wilson" för väldigt olika syften, och detta är ganska förvirrande: det finns Wilson-algoritmen för att generera labyrinter, Wilson-modellen (eller EOQ) för inventeringar och Wilsons sats i talteori. I den här artikeln förtydligar vi allt, med början i den ursprungliga användningen i labyrinter och noggrant åtskiljer de andra betydelserna, eftersom De är inte samma sak och gäller inte heller för samma område.

Om du har sett en demo eller applet där en labyrint "växer" av sig själv har du förmodligen redan stött på Wilsons algoritm. Du har också hört talas om Wilson-modellen för att beräkna den ekonomiska ordningskvantiteten eller till och med satsen som kännetecknar primtal med hjälp av faktorialer. Här hittar du en fullständig förklaring med exempel, så att du kan du kan identifiera varje koncept och använda det korrekt.

Vad är Wilsons algoritm för labyrinter?

Wilsons algoritm är en labyrintgenereringsmetod baserad på loop-raderade slumpmässiga promenader. Dess stora fördel är att den producerar ett enhetligt slumpmässigt uppspännande träd över rutnätet: enkelt uttryckt, Varje möjlig labyrint uppträder med samma sannolikhet, utan partiskhet mot specifika riktningar eller mönster.

Huvudidén är att banor läggs till den redan konstruerade mängden, men när en slumpmässig gång korsar sig själv, "raderas" loopen och rutten fortsätter där den slutade. Denna detalj förhindrar att processen skapar långa, redundanta banor eller loopar, och bibehåller strukturen som ett träd som förbinder alla celler. Resultatet är en "rättvis" labyrint: ingen korridor eller vändning har en statistisk fördel gentemot en annan.

Det finns projekt och applets skapade av communitys som visar algoritmen i aktion på ett visuellt och mycket underhållande sätt. Bland dem sticker några applets av Cruz Godar ut, där du kan välja rutnätsstorlek och ställa in den för att se hur labyrinten dyker upp steg för steg. Att se den springa hjälper dig att förstå varför. Loopradering jämnar ut oddsen i varje utvidgning av grafen.

Att bygga och lösa labyrinter är uppgifter som, även om de kan verka som spel, är nära kopplade till sök- och optimeringsproblem. Att utforma dem kräver en balans mellan tydlighet och intresse, och man undviker triviala lösningar eller återvändsgränder; utforska ett begränsat utrymme med enorma kombinationer. Därför fungerar de, både på papper och i digitala simuleringar, som Bra övningar i logik, sannolikhet och tålamod.

Hur det fungerar (i praktiken)

Nedan följer en översiktlig beskrivning av algoritmen, utan kod men med den nödvändiga mekaniken för att förstå dess beteende. Kom ihåg att målet är att bygga ett träd (utan cykler) som kopplar samman alla celler, så att det finns bara en enkel väg mellan varje punktpar.

• Det börjar med ett tomt rutnät: en cell väljs slumpmässigt och markeras som en del av trädet.
• En annan cell väljs slumpmässigt, en steg-för-steg-slumpmässig vandring påbörjas, och om vägen korsar sig själv tas looparna omedelbart bort (loop-erasing).
• När promenaden når det redan genererade trädet "limmas" hela den förfinade vägen (utan loopar) fast vid trädet.
• Det upprepas: vi väljer en ny okopplad cell, går med loopborttagning och ansluter till trädet.
• Till slut är alla celler sammankopplade och labyrinten är ett enhetligt slumpmässigt omspännande träd, så det finns inga riktnings- eller topologiska bias.

Jämfört med andra metoder (som Aldous-Broder, Prim eller Kruskal anpassad till labyrinter), utmärker sig Wilson för enhetligheten i samplingen av genereringsträdet. Dess beräkningskostnad är rimlig på typiska rutnät och framför allt, säkerställer att varje lösning är lika sannolik, något som är mycket uppskattat i akademiska och simuleringssammanhang.

Andra betydelser: Wilson-modellen eller EOQ (inventarier)

Inom logistik har "Wilson-modellen" (även kallad EOQ, Economic Order Quantity; eller CEP, Economic Order Quantity) ingenting att göra med labyrinter. Det är en klassisk metod för att bestämma den optimala orderkvantiteten med målet att minimera de totala lagerkostnaderna. Den populariserades 1934 av R.H. Wilson, även om Det första förslaget kom från Ford Whitman Harris år 1913..

Dess syfte är att hitta den partistorlek Q som balanserar beställningskostnaden och lagerhållningskostnaden. Från den årliga efterfrågan (D), kostnaden per beställning (K) och lagerkostnaden per enhet och period (G) erhålls en kvantitet som, inom ramen för dess antaganden, minskar den totala lagerkostnaden.

Den vanligaste formeln är Q = √(2 D K/G). Detta ger batchstorleken; därifrån blir antalet årliga beställningar D/Q, och från detta kan man härleda tidskadensen. Det är också viktigt att ställa in beställningspunkten (med hänsyn till ledtiden) och säkerhetslagret för att undvika lagerbrist, även om grundformeln innehåller inte osäkerhet uttryckligen.

Typiska tillämpningar: används med råvaror eller alla typer av varor för vilka inköps- och lagringskostnader kan bestämmas tillförlitligt. I praktiken, om D, K och G är kända med tillräcklig tillförlitlighet, Företaget kan dimensionera sina partier och schemalägga deras leveranser med större kontroll.

Antaganden, fördelar och begränsningar med Wilson-modellen

Antaganden är avgörande för resultatens giltighet. EOQ-modellen antar att efterfrågan är konstant och känd, att enhetspriset förblir stabilt, att lagerkostnaderna är kända och beror på lagernivån, att leveranstiderna är konstanta och dessutom... överväger inte volymrabatter.

• Stabil, oberoende efterfrågan, utan säsongsvariationer eller plötsliga toppar.
• Inköpspriset var fast eller praktiskt taget oförändrat under den analyserade perioden.
• Kända lagringskostnader per enhet och period.
• Inga mängdrabatter och omedelbar eller kontinuerlig påfyllning.

Huvudfördelar: Det är enkelt att implementera, används flitigt och hjälper till att minimera beställnings- och lagerkostnader under dina förhållanden. Fördelarna inkluderar minskad överlagerhållning, minskad risk för slut på lager (om det åtföljs av en beställningspunkt och säkerhetslager) och tydlighet i inköpsplaneringen. Många organisationer värdesätter det eftersom erbjuder en enkel numerisk grund för att bestämma hur mycket man ska beställa.

Nackdelar: Det fungerar inte bra med säsongsbetonad eller oregelbunden efterfrågan, ignorerar volymrabatter och förutsätter omedelbar (eller fast) påfyllning, vilket är orealistiskt i många leveranskedjor. Därför har EOQ-formeln i miljöer som Toyota-koncernen ersatts av mer robusta system som Kanban eller Just in Time, vilka De hanterar verklig variation bättre och det kontinuerliga flödet.

Praktiska exempel på EOQ (Wilson)

Exempel 1 (typiskt): Ett företag med en årlig produktion på 10 000 enheter köper 1 000 kg råmaterial. Om varje beställning kostar 200 euro och den totala årliga lagringskostnaden är 2 000 euro, ger tillämpning av formeln Q = √(2 D K/G) med D = 1 000, K = 200, G = 2 000 Q ≈ 14,14. Detta antyder partier på 14 kg och cirka 71 beställningar per år. Detta är en illustrativ övning där vi, med blygsamma siffror, kan se Hur partistorlek balanserar order och lager.

Exempel 2: Sillas Grandes World SL distribuerar 6 000 stolar (D), varje beställning kostar 300 € (K) och förvaring per enhet och år är 5 € (G). Om man tillämpar ekvationen Q ≈ 848,52, skulle det göra cirka 7,07 beställningar per år. Med denna partistorlek skulle företaget tenderar mot en mer effektiv lagernivå, vilket minskar lagerkostnaderna utan att öka kostnaderna för orderförberedelse.

Utöver formeln är det en bra idé att beräkna beställningspunkten med hänsyn till ledtiden och att bibehålla säkerhetslager, eftersom den rena modellen inte tar hänsyn till osäkerhet. Den uppskattar inte heller effekten av volymrabatter, som ibland skulle kunna kompensera för lagerkostnaderna om större partier används.

Inte att förväxla med Wilsons sats (talteori)

Wilsons sats tillhör modulär aritmetik och säger i huvudsak att ett heltal n > 1 är primtal om och endast om (n − 1)! ≡ −1 (mod n). Implikationen "om n är primtal så kallas (n − 1)! ≡ −1 (mod n)" ofta strikt nog för "Wilsons sats", och den motsatta implikationen är också sann. Historiskt sett tillskrev Edward Waring resultatet till John Wilson (1770), även om det första kända beviset gavs av Lagrange (1771), och faktiskt, Formuleringen går tillbaka till Alhacen på 1100-talet.

Konkret exempel: för p = 11, när man grupperar varje element med dess multiplikativa invers i mängden {1, 2, …, p − 1}, blir den totala produkten ≡ −1 (mod p). Alla faktorer tar ut varandra jämnt eftersom g g^{-1} ≡ 1, förutom 1 och p − 1, och så 10! ≡ −1 (mod 11)Denna metod använder att, med p primtal, är (Z/pZ)^× en multiplikativ grupp och varje element (förutom 1 och p − 1) har en distinkt invers.

Det finns flera bevis. En polynomteknik betraktar g(x) = (x − 1)(x − 2)···(x − (p − 1)) och f(x) = g(x) − (x^{p−1} − 1). Modulen p, f(x) skulle ha högst p − 2 rötter om det inte vore nollpolynomet, men alla 1, 2, …, p − 1 försvinner från f(x) enligt Fermats lilla sats. Därför är f(x) identiskt 0 mod p och den oberoende termen leder till (p − 1)! ≡ −1 (mod p).

Det används inte som ett praktiskt primalitetstest, eftersom det är dyrt att beräkna (n − 1)! mod n för stora n och snabbare tester finns (som Miller-Rabin eller deterministiska tester för specifika intervall). Ändå är det användbart för att härleda användbara egenskaper: till exempel, om p = 2n + 1 är primtal, då har vi ∏_{j=1}^{n} j^2 ≡ (−1)^{n+1} (mod p). Och, som en partiell korollar, är −1 en kvadratisk residu modulo p om p ≡ 1 (mod 4), eftersom den kan skrivas som kvadraten av produkten 1 2 2k när p = 4k + 1, vilket visar när −1 är kvadratisk i Z/pZ.

Det finns också en praktisk "invers": för alla sammansatta n > 5 gäller att n delar (n − 1)!. Fallet n = 4 är det klassiska undantaget (3! är inte en multipel av 4). Ett sätt att se detta är att räkna potenserna av ett primtal q som delar n: i (n − 1)! finns det tillräckligt med multiplar av q för att täcka potensen som förekommer i n, förutom det angivna undantaget, vilket leder till resultatet förutom för n = 4.

Gauss generaliserade satsen: produkten av alla enheter modulo n, ∏_{1≤a Det är det elementet av ordning 2.

Illustrativ tabell för (n − 1)! mod n för n = 2…30

I följande tabell kan du se specifika värden för n mellan 2 och 30. För n som är primtal är resten av (n − 1)!, när den divideras med n, lika med n − 1 (vilket är ≡ −1 mod n). I kompositer är resten ofta 0. −1 mod n ingår också för jämförelse. Dessa data illustrerar mycket väl hur Wilsons sats beter sig i små fall och hjälper till att fixa intuitionen.

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

Tillämpningar, begränsningar och rekommendationer

Om du vill generera opartiska labyrinter, använd Wilsons algoritm: dess grund i slumpmässiga promenader med loopdeletion säkerställer enhetliga träd. För lager är Wilson-modellen användbar när efterfrågan, priser och kostnader är stabila och exakt kända; i volatila miljöer kan metoder som Kanban, JIT eller avancerad planeringsprogramvara vara mer lämpliga. Och inom matematik är Wilsons sats en teoretisk pärla med intressanta härledningar (som kvadratiska residuer), men Det är inte praktiskt som ett primalittest för stora tal.

Det finns ingen universalformel för att beräkna beställnings- och lagerkostnader: varje företag måste bryta ner timmar, processer, transport, mottagning, personal, hyra, energi, försäkring och finansiella kostnader. Många yrkesverksamma uppskattar timmar per operation och tillämpar en timtaxa för att tjäna pengar. Denna anpassning är nyckeln till att göra den beräknade kvantiteten användbar och, tillsammans med en bra beställningspunkt och säkerhetslager, undvik lagerbrist eller överskottslager.

Det är värt att komma ihåg att termen "Wilsons algoritm" i sökningar vanligtvis hänvisar till labyrintgeneratorn, medan "Wilsons modell" eller "EOQ" hänvisar till inventeringar, och "Wilsons sats" hänvisar till talteori. Att skilja dem åt från början undviker förvirring och gör att du bättre kan utnyttja varje metod: Objektiva labyrinter, optimala batcher under realistiska antaganden och en elegant karakterisering av primtal vilket, även om det inte är ett praktiskt primalitetstest, fortfarande är en värdefull pusselbit.