Wilsonov algoritam: Potpuni vodič, razlike s EOQ-om i teorem

Informatec Digital » Inženjering » Wilsonov algoritam: Potpuni vodič, razlike s EOQ-om i teorem

Na internetu ljudi koriste izraz "Wilson" u vrlo različite svrhe, što je prilično zbunjujuće: postoji Wilsonov algoritam za generiranje labirinata, Wilsonov model (ili EOQ) za inventare i Wilsonov teorem u teoriji brojeva. U ovom članku razjašnjavamo sve, počevši od izvorne upotrebe u labirintima i pažljivo razlikujući ostala značenja, jer Nisu isti niti se odnose na isto područje.

Ako ste vidjeli demo ili applet gdje labirint "raste" sam od sebe, vjerojatno ste već naišli na Wilsonov algoritam. Također ste čuli za Wilsonov model za izračunavanje ekonomske količine narudžbe ili čak za teorem koji karakterizira proste brojeve pomoću faktorijela. Ovdje ćete pronaći potpuno objašnjenje s primjerima, tako da možete možete prepoznati svaki koncept i pravilno ga koristiti.

Što je Wilsonov algoritam za labirinte?

Wilsonov algoritam je metoda generiranja labirinta temeljena na slučajnim šetnjama s brisanjem petlji. Njegova velika prednost je što stvara uniformno slučajno razapinjuće stablo preko mreže: jednostavno rečeno, Svaki mogući labirint pojavljuje se s istom vjerojatnošću, bez pristranosti prema određenim smjerovima ili obrascima.

Ključna ideja je da se putevi dodaju već konstruiranom skupu, ali kada slučajna šetnja presiječe samu sebe, petlja se "briše" i ruta se nastavlja od mjesta gdje je stala. Ovaj detalj sprječava proces stvaranja dugih, redundantnih puteva ili petlji, održavajući strukturu kao stablo koje povezuje sve ćelije. Rezultat je "pravedan" labirint: Nijedan koridor ili zavoj nema statističku prednost nad drugim.

Postoje projekti i apleti koje je kreirala zajednica, a koji prikazuju algoritam u akciji na vizualan i vrlo zabavan način. Među njima se ističu neki apleti Cruza Godara, gdje možete odabrati veličinu mreže i postaviti je da radi kako biste vidjeli kako labirint nastaje korak po korak. Promatranje kako se izvodi pomaže vam da shvatite zašto. Brisanje petlje izjednačava izglede u svakom proširenju grafa.

Izgradnja i rješavanje labirinata su zadaci koji, iako se mogu činiti kao igre, usko su povezani s problemima pretraživanja i optimizacije. Njihovo dizajniranje zahtijeva ravnotežu između jasnoće i zanimljivosti, izbjegavajući trivijalna rješenja ili slijepe ulice; istražiti ograničeni prostor s ogromnim kombinacijama. Stoga, i na papiru i u digitalnim simulacijama, oni funkcioniraju kao Izvrsne vježbe iz logike, vjerojatnosti i strpljenja.

Kako to funkcionira (u praksi)

U nastavku slijedi opći opis algoritma, bez koda, ali s osnovnim mehanizmima za razumijevanje njegovog ponašanja. Imajte na umu da je cilj izgraditi stablo (bez ciklusa) koje povezuje sve ćelije, tako da postoji samo jedan jednostavan put između bilo kojeg para točaka.

• Počinje s praznom mrežom: ćelija se nasumično bira i označava kao dio stabla.
• Nasumično se bira druga ćelija, pokreće se postupno nasumično hodanje i ako se put križa sa samim sobom, petlje se odmah uklanjaju (brisanje petlji).
• Kada šetnja dođe do već generiranog stabla, cijela profinjena putanja (bez petlji) se „zalijepi“ za stablo.
• Ponavlja se: biramo novu nepovezanu ćeliju, hodamo s brisanjem petlje i pridružujemo se stablu.
• Na kraju su sve ćelije povezane i labirint je uniformno slučajno razapinjuće stablo, dakle nema smjernih ili topoloških pristranosti.

U usporedbi s drugim metodama (kao što je Aldous-Broder, ukočen ili Kruskal prilagođen labirintima), Wilson se ističe ujednačenošću uzorkovanja generirajućeg stabla. Njegovi računalni troškovi su razumni na tipičnim mrežama i, prije svega, osigurava da je svako rješenje jednako vjerojatno, što je vrlo cijenjeno u akademskim i simulacijskim kontekstima.

Druga značenja: Wilsonov model ili EOQ (zalihe)

U logistici, „Wilsonov model“ (također nazvan EOQ, Economic Order Quantity; ili CEP, Economic Order Quantity) nema nikakve veze s labirintima. To je klasična metoda za određivanje optimalne količine narudžbe s ciljem minimiziranja ukupnih troškova zaliha. Popularizirao ga je 1934. R.H. Wilson, iako Prvi prijedlog dao je Ford Whitman Harris 1913. godine..

Njegova je svrha pronaći veličinu serije Q koja uravnotežuje trošak naručivanja i trošak držanja zaliha. Iz godišnje potražnje (D), troška po narudžbi (K) i troška skladištenja po jedinici i razdoblju (G) dobiva se količina koja, unutar okvira svojih pretpostavki, smanjuje ukupne troškove zaliha.

Najčešća formula je Q = √(2 D K/G). To daje veličinu serije; odatle će broj godišnjih narudžbi biti D/Q, a iz toga se može izvesti vremenska kadenca. Također je važno postaviti točku ponovne narudžbe (uzimajući u obzir vrijeme isporuke) i sigurnosne zalihe kako bi se izbjegle nestašice, iako osnovna formula ne uključuje nesigurnost eksplicitno.

Tipične primjene: koristi se sa sirovinama ili bilo kojom vrstom robe za koju se troškovi nabave i skladištenja mogu pouzdano utvrditi. U praksi, ako su D, K i G poznati s dovoljnom pouzdanošću, Tvrtka može odrediti veličinu svojih serija i zakazati njihovu isporuku s većom kontrolom.

Pretpostavke, prednosti i ograničenja Wilsonovog modela

Pretpostavke su ključne za valjanost rezultata. EOQ model pretpostavlja da je potražnja konstantna i poznata, da je jedinična cijena stabilna, da su troškovi skladištenja poznati i ovise o razini zaliha, da su vremena opskrbe konstantna i, nadalje, ne predviđa količinske popuste.

• Stabilna, neovisna potražnja, bez sezonalnosti ili naglih vrhunaca.
• Nabavna cijena fiksna ili praktički nepromijenjena tijekom analiziranog razdoblja.
• Poznati troškovi skladištenja po jedinici i razdoblju.
• Nema količinskih popusta i trenutnog ili stalnog nadopunjavanja zaliha.

Glavne prednosti: Jednostavan je za implementaciju, široko se koristi i pomaže u smanjenju troškova naručivanja i zaliha u vašim uvjetima. Njegove prednosti uključuju smanjeno prezalihivanje, smanjeni rizik od nedostatka zaliha (ako postoji točka ponovne narudžbe i sigurnosne zalihe) i jasnoću u planiranju nabave. Mnoge organizacije ga cijene jer nudi jednostavnu numeričku osnovu za odlučivanje koliko naručiti.

Nedostaci: Ne funkcionira dobro sa sezonskom ili neredovitom potražnjom, zanemaruje količinske popuste i pretpostavlja trenutno (ili fiksno) popunjavanje zaliha, što je nerealno u mnogim lancima opskrbe. Stoga je u okruženjima poput Toyota Grupe formula EOQ zamijenjena robusnijim sustavima poput Kanbana ili Just in Time, koji Bolje se nose sa stvarnom varijabilnosti i kontinuirani tok.

Praktični primjeri EOQ-a (Wilson)

Primjer 1 (tipičan): Tvrtka s godišnjom proizvodnjom od 10.000 jedinica kupuje 1.000 kg sirovine. Ako svaka narudžba košta 200 €, a ukupni godišnji trošak skladištenja iznosi 2.000 €, primjenom formule Q = √(2 D K/G) s D = 1.000, K = 200, G = 2.000 dobivamo Q ≈ 14,14. To sugerira serije od 14 kg i približno 71 narudžbu godišnje. Ovo je ilustrativna vježba gdje, uz skromne brojke, možemo vidjeti Kako veličina lota uravnotežuje narudžbe i zalihe.

Primjer 2: Sillas Grandes World SL distribuira 6.000 stolica (D), svaka narudžba košta 300 € (K), a skladištenje po jedinici godišnje iznosi 5 € (G). Primjenom jednadžbe, Q ≈ 848,52, to bi značilo približno 7,07 narudžbi godišnje. S ovom veličinom serije, tvrtka teži prema učinkovitijoj razini zaliha, smanjujući troškove skladištenja bez povećanja troškova pripreme narudžbe.

Osim formule, dobra je ideja izračunati točku ponovne narudžbe uzimajući u obzir vrijeme isporuke i održavanje sigurnosnih zaliha, jer čisti model ne uzima u obzir nesigurnost. Također ne procjenjuje utjecaj količinskih popusta, koji ponekad... mogao bi nadoknaditi troškove zaliha ako se koriste veće serije.

Ne treba miješati s Wilsonovim teoremom (teorija brojeva)

Wilsonov teorem pripada modularna aritmetika i u biti kaže da je cijeli broj n > 1 prost ako i samo ako (n − 1)! ≡ −1 (mod n). Implikacija „ako je n prost onda (n − 1)! ≡ −1 (mod n)“ često se strogo naziva „Wilsonov teorem“, a obrnuta implikacija također vrijedi. Povijesno gledano, Edward Waring pripisao je rezultat Johnu Wilsonu (1770.), iako je prvi poznati dokaz dao Lagrange (1771.), i zapravo, Formulacija datira još iz Alhacena u 11. stoljeću..

Konkretan primjer: za p = 11, kada se svaki element grupira s njegovim multiplikativnim inverzom u skupu {1, 2, …, p − 1}, ukupni produkt postaje ≡ −1 (mod p). Svi faktori se ravnomjerno poništavaju jer je g g^{-1} ≡ 1, osim 1 i p − 1, i tako dalje 10! ≡ −1 (mod 11)Ovaj pristup koristi činjenicu da je, s p prost, (Z/pZ)^× multiplikativna grupa i svaki element (osim 1 i p − 1) ima različit inverz.

Postoji nekoliko dokaza. Jedna polinomska tehnika razmatra g(x) = (x − 1)(x − 2)···(x − (p − 1)) i f(x) = g(x) − (x^{p−1} − 1). Modul p, f(x) bi imao najviše p − 2 korijena da nije nulti polinom, ali svi 1, 2, …, p − 1 nestaju f(x) prema Fermatovom malom teoremu. Stoga je f(x) identično 0 mod p i nezavisni član vodi do (p − 1)! ≡ −1 (mod p).

Ne koristi se kao praktični test primarnosti, jer je računanje (n − 1)! mod n za velike n skupo i postoje brži testovi (kao što su Miller-Rabin ili deterministički testovi za specifične raspone). Unatoč tome, korisno je izvesti korisna svojstva: na primjer, ako je p = 2n + 1 prost broj, tada imamo ∏_{j=1}^{n} j^2 ≡ (−1)^{n+1} (mod p). I, kao djelomična posljedica, −1 je kvadratni ostatak modulo p ako je p ≡ 1 (mod 4), budući da se može zapisati kao kvadrat produkta 1 2 2k kada je p = 4k + 1, što pokazuje kada je −1 kvadrat u Z/pZ.

Postoji i praktični „inverz“: za bilo koji složeni broj n > 5, istina je da n dijeli (n − 1)!. Slučaj n = 4 je klasičan izuzetak (3! nije višekratnik broja 4). Jedan od načina da se to vidi jest prebrojavanje potencija prostog broja q koje dijele n: u (n − 1)! postoji dovoljno višekratnika broja q da pokriju potenciju koja se pojavljuje u n, osim naznačenog izuzetka, koji vodi do rezultata osim za n = 4.

Gauss je generalizirao teorem: produkt svih jedinica modulo n, ∏_{1≤a To je element drugog reda.

Ilustrativna tablica (n − 1)! mod n za n = 2…30

U sljedećoj tablici možete vidjeti specifične vrijednosti za n između 2 i 30. Za n koji je prost, ostatak od (n − 1)! pri dijeljenju s n jednak je n − 1 (što je ≡ −1 mod n). U kompozitnim brojevima, ostatak je često 0. −1 mod n je također uključen za usporedbu. Ovi podaci vrlo dobro ilustriraju kako se Wilsonov teorem ponaša u malim slučajevima i pomažu u popraviti intuiciju.

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

Primjene, ograničenja i preporuke

Ako želite generirati nepristrane labirinte, koristite Wilsonov algoritam: njegova osnova u slučajnim šetnjama s brisanjem petlji osigurava uniformna stabla. Za zalihe, Wilsonov model je koristan kada su potražnja, cijene i troškovi stabilni i precizno poznati; u nestabilnim okruženjima, metodologije poput Kanbana, JIT-a ili naprednog softvera za planiranje mogu biti prikladnije. A u matematici, Wilsonov teorem je teorijski dragulj sa zanimljivim izvedbama (kao što su kvadratni ostaci), ali Nije praktično kao test primarnosti za velike brojeve.

Ne postoji univerzalna formula za izračun troškova naručivanja i skladištenja: svaka tvrtka mora raščlaniti sate, procese, prijevoz, prijem, osoblje, najamninu, energiju, osiguranje i financijske troškove. Mnogi profesionalci procjenjuju sate po operaciji i primjenjuju satnicu za monetizaciju. Ova prilagodba ključna je za to da izračunati Q bude koristan i, uz dobru točku ponovne narudžbe i sigurnosne zalihe, izbjegavajte nestašice ili višak zaliha.

Vrijedi zapamtiti da se pojam "Wilsonov algoritam" u pretragama obično odnosi na generator labirinta, dok se "Wilsonov model" ili "EOQ" odnosi na inventare, a "Wilsonov teorem" na teoriju brojeva. Razlikovanjem od samog početka izbjegava se zbrka i omogućuje se bolje korištenje svakog pristupa: Nepristrani labirinti, optimalne serije pod realnim pretpostavkama i elegantna karakterizacija prostih brojeva koji, iako nije praktičan test jednostavnosti, ipak je vrijedan dio matematičke slagalice.