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

Informatec Digital » Strojírenství » Wilsonův algoritmus: Kompletní průvodce, rozdíly oproti EOQ a teorém

Na internetu se termín „Wilson“ používá pro mnoho různých věcí, což je dost matoucí: existuje Wilsonův algoritmus pro generování bludišť, Wilsonův inventářový model (nebo EOQ) a Wilsonova věta v teorii čísel. V tomto článku si vše objasníme, počínaje jeho původním použitím v bludištích a pečlivě rozlišujeme ostatní významy, protože se nejedná o totéž a nevztahují se 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. Možná jste také slyšeli 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 každý koncept identifikovat a správně jej používat.

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

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

Klíčovou myšlenkou je, že cesty se přidávají do existující sítě, ale když se náhodná cesta protíná sama se sebou, smyčka se „vymaže“ a trasa pokračuje od bodu, kde se uvolnila. Tento detail zabraňuje procesu upřednostňovat redundantní dlouhé cesty nebo vytvářet cykly, čímž se struktura zachovává jako strom, který spojuje všechny buňky. Výsledkem je „spravedlivé“ bludiště: žádná cesta ani odbočka nemá statistickou výhodu oproti jiné.

Existují komunitní projekty a applety, které vizuálně a zábavně demonstrují algoritmus v akci. Mezi nimi vynikají některé z appletů Cruze Godara, kde si můžete zvolit velikost mřížky a spustit ji, abyste viděli, jak se bludiště krok za krokem vyvíjí. Sledování běhu vám pomůže pochopit, proč mazání smyčky vyrovnává pravděpodobnosti v každém prodloužení grafu.

Stavba a řešení bludišť, ačkoli se zdají být hry, je úzce spjato s problémy vyhledávání a optimalizace. Jejich navrhování vyžaduje rovnováhu mezi jasností a intrikou, vyhýbání se triviálním řešením nebo nemožným slepým uličkám a prozkoumávání konečného prostoru s obrovským množstvím kombinací. Proto, jak na papíře, tak v digitálních simulacích, slouží jako vynikající cvičení logiky, pravděpodobnosti a trpělivosti.

Jak to funguje (v praxi)

Níže je uveden stručný 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 libovolnými dvěma body existovala 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 jsou Aldous-Broder, Prim nebo Kruskal přizpůsobené pro bludiště) vyniká Wilson uniformitou vzorkování pomocí kostry. Jeho výpočetní náklady jsou na typických sítích rozumné a především zaručuje, že každé řešení je ekvipravděpodobné , což je vysoce ceněno v akademickém a simulačním kontextu.

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

V logistice nemá Wilsonův model (nazývaný také EOQ, 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 původní koncept navrhl Ford Whitman Harris v roce 1913.

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

Nejběžnější vzorec je vyjádřen jako Q = √(2·D·K/G). Tento údaj udává velikost každé dávky; odtud bude počet ročních objednávek D/Q a z toho lze odvodit cyklus objednávek. Je také důležité stanovit 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 explicitně nezahrnuje nejistotu.

Typické aplikace: Používá se u surovin nebo jakéhokoli druhu zboží, u kterého lze spolehlivě určit náklady na nákup a skladování. V praxi může společnost díky dostatečné znalosti D, K a G dimenzovat své šarže a plánovat nákup s větší kontrolou.

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

Tyto předpoklady jsou klíčové pro platnost výsledku. Model EOQ předpokládá, že poptávka je konstantní a známá, že jednotková cena zůstává stabilní, že skladovací náklady jsou známé a závisí na stavu zásob, že dodací lhůty jsou konstantní a dále nezohledňuje 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.

Klíčové výhody: Je snadno implementovatelný, široce používaný a pomáhá minimalizovat náklady na objednávání a správu zásob v rámci svých podmínek. Mezi výhody patří snížení předzásobení, snížení rizika nedostatku zásob (v kombinaci s bodem pro opětovné objednání a bezpečnostní zásobou) a větší přehlednost plánování nákupu. Mnoho organizací si ho cení, protože poskytuje přímočarý numerický základ pro určení množství objednávek.

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 skupina Toyota, 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ů získá 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 použití vzorce Q = √(2·D·K/G) s D=1 000, K=200 a G=2 000 dává Q ≈ 14,14. To naznačuje šarže o hmotnosti 14 kg a přibližně 71 objednávek ročně. Jedná se o ilustrativní cvičení, kde s malým počtem kusů můžeme vidět, jak velikost šarže vyvažuje objednávky a zásoby.

Příklad 2: Společnost Sillas Grandes World SL distribuuje 6 000 židlí (D), každá objednávka stojí 300 EUR (K) a roční náklady na skladování na jednotku jsou 5 EUR (G). Použitím rovnice Q ≈ 848,52 znamená, že společnost by ročně zadala přibližně 7,07 objednávek. S touto velikostí šarže se firma přiklání k efektivnější úrovni zásob , čímž snižuje náklady na skladování, aniž by výrazně zvyšovala náklady na přípravu objednávek.

Kromě samotného vzorce je vhodné vypočítat bod opětovné objednávky s ohledem na dodací lhůtu a udržovat bezpečnostní zásoby, protože čistý model nezohledňuje nejistotu. Také neodhaduje dopad množstevních slev, které by někdy mohly 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ří do modulární aritmetiky 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 obvykle 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 formulace ve skutečnosti pochází z doby Alhazena v 11. století.

Konkrétní příklad: pro p = 11, seskupením každého prvku s jeho multiplikativní inverzí v množině {1, 2, …, p − 1} je celkový součin ≡ −1 (mod p). Všechny činitelé se po párech vyruší, protože g·g^{-1} ≡ 1, s výjimkou 1 a p − 1, a proto 10! ≡ −1 (mod 11) . Tento přístup využívá skutečnosti, že pro p prvočíslo 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). Modulo p by f(x) měla nejvýše p − 2 kořenů, kdyby nebyla nulovým polynomem, ale všechny 1, 2, …, p − 1 dělají f(x) nulou podle Fermatovy malé věty. Proto je f(x) identicky 0 mod p; konstantní č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-Rabin nebo deterministické testy pro specifické hodnosti). Přesto jej lze použít k odvození užitečných vlastností: například pokud je p = 2n + 1 prvočíslo, dostaneme ∏_{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ž se projeví, když je −1 umocněno 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 zmíněné 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<n, (a,n)=1} a, je ≡ −1 (mod n), pokud n ∈ {4, p^k, 2p^k} s p lichým prvočíslem, a ≡ 1 (mod n) ve všech ostatních případech. Z pohledu konečných abelovských grup je součin všech jejich prvků jednotkou, pokud neexistuje právě jeden prvek řádu 2, v takovém případě je součinem tento prvek řádu 2.

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

Následující tabulka ukazuje konkrétní hodnoty pro n mezi 2 a 30. U prvočísel je zbytek (n − 1)! po dělení n roven n − 1 (což je ≡ −1 mod n). U složených čísel je zbytek často 0. Pro srovnání je zde také uvedeno −1 mod n. Tato data jasně ilustrují, jak se Wilsonova věta chová v malých případech, a pomáhají upevnit 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 nezaujaté 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 řízení zásob 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, Just-in-Time 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í praktická jako test prvočísla pro velká čísla.

Neexistuje jediný 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íčová pro zajištění toho, aby vypočítané množství objednávky (Q) bylo užitečné, a spolu s dobrým bodem pro opětovné objednání a bezpečnostními zásobami pomáhá předcházet nedostatku zásob nebo nadměrným zásobám.

Je třeba si uvědomit, že termín „Wilsonův algoritmus“ ve vyhledávání obvykle odkazuje na 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: nezaujatá bludiště, optimální dávky za realistických předpokladů a elegantní charakterizaci prvočísel, která sice není praktickým důkazem prvočísel, ale zůstává cenným dílem matematické skládačky.