Wilsonův algoritmus: Kompletní průvodce, rozdíly s EOQ a teorém

Informatec Digital » Inženýrství » Wilsonův algoritmus: Kompletní průvodce, rozdíly s EOQ a teorém

Na internetu lidé používají termín „Wilson“ k velmi různým účelům, což je dost matoucí: existuje Wilsonův algoritmus pro generování bludišť, Wilsonův model (nebo EOQ) pro inventáře a Wilsonova věta v teorii čísel. V tomto článku si vše objasníme, počínaje původním použitím v bludištích a pečlivě rozlišujeme ostatní významy, protože Nejsou to stejné ani se nevztahují na stejnou oblast.

Pokud jste viděli demo nebo applet, kde bludiště „roste“ samo od sebe, pravděpodobně jste se již setkali s Wilsonovým algoritmem. Slyšeli jste také o Wilsonově modelu pro výpočet ekonomického množství objednávky nebo dokonce o větě, která charakterizuje prvočísla pomocí faktoriálů. Zde najdete kompletní vysvětlení s příklady, abyste mohli dokážete identifikovat každý koncept a správně ho používat.

Co je Wilsonův algoritmus pro bludiště?

Wilsonův algoritmus je metoda generování bludiště založená na náhodných procházkách s vymazanými smyčkami. Jeho velkou výhodou je, že vytváří uniformní náhodný kostrový strom nad mřížkou: jednoduše řečeno, Každé možné bludiště se objeví se stejnou pravděpodobností, bez zaujatosti vůči konkrétním směrům nebo vzorcům.

Klíčovou myšlenkou je, že cesty se přidávají k již vytvořené množině, ale když náhodná procházka protne sama sebe, smyčka se „smaže“ a trasa pokračuje tam, kde skončila. Tento detail zabraňuje procesu vytvářet dlouhé, redundantní cesty nebo smyčky a zachovává strukturu jako strom spojující všechny buňky. Výsledkem je „férové“ bludiště: žádný koridor ani zatáčka nemá statistickou výhodu oproti jinému.

Existují komunitní projekty a applety, které ukazují algoritmus v akci vizuálním a velmi zábavným způsobem. Mezi nimi vynikají některé applety od Cruze Godara, kde si můžete zvolit velikost mřížky a nastavit ji tak, abyste krok za krokem sledovali, jak se bludiště vyvíjí. Sledování jeho běhu vám pomůže pochopit proč. Mazání smyčky vyrovnává šance v každém rozšíření grafu.

Stavba a řešení bludišť jsou úkoly, které sice mohou vypadat jako hry, ale úzce souvisí s problémy vyhledávání a optimalizace. Jejich navrhování vyžaduje rovnováhu mezi srozumitelností a zajímavostí, vyhýbání se triviálním řešením nebo slepým uličkám; prozkoumat konečný prostor s obrovskými kombinacemi. Proto jak na papíře, tak v digitálních simulacích fungují jako Skvělá cvičení v logice, pravděpodobnosti a trpělivosti.

Jak to funguje (v praxi)

Níže je uveden podrobný popis algoritmu bez kódu, ale se základními mechanismy pro pochopení jeho chování. Nezapomeňte, že cílem je vytvořit strom (bez cyklů), který propojí všechny buňky tak, aby mezi libovolnou dvojicí bodů existuje pouze jedna jednoduchá cesta.

• Začíná to s prázdnou mřížkou: buňka je náhodně vybrána a označena jako součást stromu.
• Náhodně se vybere další buňka, spustí se postupná náhodná procházka a pokud se cesta kříží, smyčky se okamžitě odstraní (mazání smyčky).
• Když trasa dosáhne již vygenerovaného stromu, celá zpřesněná cesta (bez smyček) se ke stromu „přilepí“.
• Opakuje se to: vybereme novou nepropojenou buňku, projdeme ji s odstraněním smyčky a připojíme se ke stromu.
• Nakonec jsou všechny buňky propojené a bludiště je uniformní náhodná kostka, takže neexistují žádné směrové ani topologické odchylky.

Ve srovnání s jinými metodami (jako je Aldous-Broder, Prim nebo Kruskal adaptovaný na labyrinty), Wilson vyniká uniformitou vzorkování generujícího stromu. Jeho výpočetní náklady jsou na typických sítích rozumné a především zajišťuje, že každé řešení je stejně pravděpodobné, což je v akademickém a simulačním kontextu vysoce ceněno.

Jiné významy: Wilsonův model nebo EOQ (zásoby)

V logistice nemá „Wilsonův model“ (také nazývaný EOQ, Economic Order Quantity; nebo CEP, Economic Order Quantity) nic společného s bludištěm. Je to klasická metoda pro určení optimálního množství objednávky s cílem minimalizovat celkové náklady na zásoby. Zpopularizoval ji v roce 1934 R.H. Wilson, ačkoli První návrh předložil Ford Whitman Harris v roce 1913..

Jeho účelem je najít velikost šarže Q, která vyvažuje náklady na objednávání a náklady na skladování zásob. Z roční poptávky (D), nákladů na objednávku (K) a skladovacích nákladů na jednotku a období (G) se získá množství, které v rámci jeho předpokladů snižuje celkové náklady na zásoby.

Nejběžnější vzorec je Q = √(2 D K/G). Ten udává velikost dávky; odtud bude počet ročních objednávek D/Q a z toho lze odvodit časovou kadenci. Je také důležité nastavit bod pro opětovné objednání (s ohledem na dodací lhůtu) a bezpečnostní zásoby, aby se zabránilo vyprodání zásob, ačkoli... základní vzorec nezahrnuje nejistotu výslovně.

Typické použití: používá se se surovinami nebo jakýmkoli typem zboží, u kterého lze spolehlivě určit náklady na nákup a skladování. V praxi, pokud jsou D, K a G známy s dostatečnou spolehlivostí, Společnost si může nastavit velikost svých šarží a naplánovat jejich dodávky s větší kontrolou.

Předpoklady, výhody a omezení Wilsonova modelu

Předpoklady jsou pro platnost výsledků zásadní. Model EOQ předpokládá, že poptávka je konstantní a známá, že jednotková cena zůstává stabilní, že náklady na skladování jsou známé a závisí na úrovni zásob, že dodací lhůty jsou konstantní a dále nepředpokládá množstevní slevy.

• Stabilní, nezávislá poptávka, bez sezónnosti nebo náhlých výkyvů.
• Nákupní cena je během analyzovaného období fixní nebo prakticky nezměněná.
• Známé náklady na skladování na jednotku a období.
• Žádné množstevní slevy a okamžité nebo neustálé doplňování zásob.

Hlavní výhody: Je snadno implementovatelný, široce používaný a pomáhá minimalizovat náklady na objednávání a správu zásob za vašich podmínek. Mezi jeho výhody patří snížení předzásobení, snížení rizika nedostatku zásob (pokud je doprovázeno bodem pro opětovné objednání a bezpečnostním skladem) a přehlednost v plánování nákupu. Mnoho organizací si ho cení, protože nabízí jednoduchý numerický základ pro rozhodování o tom, kolik objednat.

Nevýhody: Nefunguje dobře se sezónní nebo nepravidelnou poptávkou, ignoruje množstevní slevy a předpokládá okamžité (nebo fixní) doplnění zásob, což je v mnoha dodavatelských řetězcích nereálné. Proto byl v prostředích, jako je Toyota Group, vzorec EOQ nahrazen robustnějšími systémy, jako je Kanban nebo Just in Time, které Lépe zvládají skutečnou variabilitu a nepřetržitý tok.

Praktické příklady EOQ (Wilson)

Příklad 1 (typický): Společnost s roční produkcí 10 000 kusů nakupuje 1 000 kg suroviny. Pokud každá objednávka stojí 200 EUR a celkové roční náklady na skladování jsou 2 000 EUR, pak po použití vzorce Q = √(2 D K/G) s D = 1 000, K = 200, G = 2 000 dostaneme Q ≈ 14,14. To naznačuje šarže o hmotnosti 14 kg a přibližně 71 objednávek ročně. Toto je ilustrativní cvičení, kde s malými čísly můžeme vidět Jak velikost šarže vyvažuje objednávky a zásoby.

Příklad 2: Sillas Grandes World SL distribuuje 6 000 židlí (D), každá objednávka stojí 300 EUR (K) a skladování na kus za rok je 5 EUR (G). Použitím rovnice Q ≈ 848,52 by to znamenalo přibližně 7,07 objednávek ročně. S touto velikostí šarže firma směřuje k efektivnější úrovni zásob, čímž se snižují náklady na skladování bez zvýšení nákladů na přípravu objednávek.

Kromě vzorce je vhodné vypočítat bod opětovného objednání s ohledem na dodací lhůtu a udržování bezpečnostních zásob, protože čistý model nezohledňuje nejistotu. Také neodhaduje dopad objemových slev, které někdy... mohly by kompenzovat náklady na zásoby pokud se použijí větší šarže.

Nesmí být zaměňována s Wilsonovou větou (teorie čísel)

Wilsonova věta patří k modulární aritmetika a v podstatě říká, že celé číslo n > 1 je prvočíslo právě tehdy, když (n − 1)! ≡ −1 (mod n). Implikace „pokud je n prvočíslo, pak (n − 1)! ≡ −1 (mod n)“ se často striktně nazývá „Wilsonova věta“ a platí i obrácená implikace. Historicky Edward Waring připisoval tento výsledek Johnu Wilsonovi (1770), ačkoli první známý důkaz poskytl Lagrange (1771) a ve skutečnosti Receptura pochází z Alhacenu v 11. století..

Konkrétní příklad: pro p = 11, když seskupíme každý prvek s jeho multiplikativní inverzí v množině {1, 2, …, p − 1}, celkový součin se stane ≡ −1 (mod p). Všechny činitelé se rovnoměrně vyruší, protože g g^{-1} ≡ 1, kromě 1 a p − 1, a proto 10! ≡ −1 (mod 11)Tento přístup využívá fakt, že s p prvočíslem je (Z/pZ)^× multiplikativní grupa a každý prvek (kromě 1 a p − 1) má odlišnou inverzi.

Existuje několik důkazů. Jedna polynomiální technika uvažuje g(x) = (x − 1)(x − 2)···(x − (p − 1)) a f(x) = g(x) − (x^{p−1} − 1). Modul p, f(x) by měl maximálně p − 2 kořeny, kdyby nebyl nulovým polynomem, ale všechny 1, 2, …, p − 1 jsou nulové f(x) podle Fermatovy malé věty. Proto f(x) je identicky 0 mod p a nezávislý člen vede k (p − 1)! ≡ −1 (mod p).

Nepoužívá se jako praktický test prvočísla, protože výpočet (n − 1)! mod n pro velké n je nákladný a existují rychlejší testy (jako Miller-Rabinovy ​​nebo deterministické testy pro specifické rozsahy). Přesto je užitečné odvodit užitečné vlastnosti: například pokud je p = 2n + 1 prvočíslo, pak máme ∏_{j=1}^{n} j^2 ≡ (−1)^{n+1} (mod p). A jako částečný důsledek, −1 je kvadratický zbytek modulo p, pokud p ≡ 1 (mod 4), protože jej lze zapsat jako druhou mocninu součinu 1 2 2k, když p = 4k + 1, což ukazuje, kdy je −1 druhá mocnina v Z/pZ.

Existuje také praktický „inverzní případ“: pro jakékoli složené číslo n > 5 platí, že n dělí (n − 1)!. Případ n = 4 je klasickou výjimkou (3! není násobkem 4). Jedním ze způsobů, jak to vidět, je spočítat mocniny prvočísla q, které dělí n: v (n − 1)! existuje dostatek násobků q, aby pokryly mocninu, která se objevuje v n, s výjimkou uvedené výjimky, která vede k výsledku s výjimkou n = 4.

Gauss zobecnil větu: součin všech jednotek modulo n, ∏_{1≤a Je to prvek řádu 2.

Ilustrativní tabulka (n − 1)! mod n pro n = 2…30

V následující tabulce vidíte konkrétní hodnoty pro n mezi 2 a 30. Pro n, které je prvočíslo, je zbytek (n − 1)! po dělení n roven n − 1 (což je ≡ −1 mod n). V kompozitních rovnicích je zbytek často roven 0. Pro srovnání je zde také zahrnuto −1 mod n. Tato data velmi dobře ilustrují, jak se Wilsonova věta chová v malých případech, a pomáhají opravit intuici.

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

Aplikace, limity a doporučení

Pokud chcete generovat nezkreslené bludiště, použijte Wilsonův algoritmus: jeho základ v náhodných procházkách s mazáním smyček zajišťuje uniformní stromy. Pro zásoby je Wilsonův model užitečný, když jsou poptávka, ceny a náklady stabilní a přesně známé; v nestabilním prostředí mohou být vhodnější metodiky jako Kanban, JIT nebo pokročilý plánovací software. A v matematice je Wilsonova věta teoretickým klenotem se zajímavými odvozeními (jako jsou kvadratické rezidua), ale Není to praktické jako test prvopočtů. pro velká čísla.

Neexistuje univerzální vzorec pro výpočet nákladů na objednávání a skladování: každá společnost musí rozebrat náklady na hodiny, procesy, dopravu, příjem, personál, nájemné, energie, pojištění a finanční náklady. Mnoho profesionálů odhaduje počet hodin na operaci a pro monetizaci používá hodinovou sazbu. Tato úprava je klíčem k tomu, aby bylo vypočítané Q užitečné, a spolu s dobrým bodem pro opětovné objednání a bezpečnostními zásobami... vyhněte se nedostatku zásob nebo nadměrnému zásobování.

Je třeba si uvědomit, že termín „Wilsonův algoritmus“ ve vyhledávání obvykle označuje generátor bludišť, zatímco „Wilsonův model“ nebo „EOQ“ označuje inventáře a „Wilsonova věta“ teorii čísel. Jejich rozlišení od samého začátku zabraňuje nejasnostem a umožňuje lépe využít každý přístup: Nestranné bludiště, optimální dávky za realistických předpokladů a elegantní charakterizace prvočísel který, ačkoliv se nejedná o praktický test prvočísla, je stále cenným dílkem matematické skládačky.