Vilsona algoritms: pilnīgs ceļvedis, atšķirības ar EOQ un teorēmu

Informatec Digital » Inženierija » Vilsona algoritms: pilnīgs ceļvedis, atšķirības ar EOQ un teorēmu

Internetā termins "Vilsons" tiek lietots daudzām dažādām lietām, kas ir diezgan mulsinoši: pastāv Vilsona algoritms labirintu ģenerēšanai, Vilsona inventarizācijas modelis (jeb EOQ) un Vilsona teorēma skaitļu teorijā. Šajā rakstā mēs visu noskaidrojam, sākot ar tā sākotnējo lietojumu labirintos un rūpīgi nošķirot citas nozīmes, jo tās nav viens un tas pats un neattiecas uz vienu un to pašu jomu.

Ja esat redzējis demonstrāciju vai sīklietotni, kurā labirints "aug" pats no sevis, iespējams, jau esat saskāries ar Vilsona algoritmu. Iespējams, esat dzirdējuši arī par Vilsona modeli ekonomiskās kārtas daudzuma aprēķināšanai vai pat teorēmu, kas raksturo pirmskaitļus, izmantojot faktoriālus. Šeit atradīsiet pilnīgu skaidrojumu ar piemēriem, lai varētu identificēt katru jēdzienu un pareizi to lietot.

Kāds ir Vilsona algoritms labirintiem?

Vilsona algoritms ir labirinta ģenerēšanas metode, kuras pamatā ir cilpu dzēstas nejaušas pastaigas. Tās galvenā priekšrocība ir tā, ka tā ģenerē vienmērīgu nejaušu aptverošu koku visā režģī: vienkārši sakot, katrs iespējamais labirints parādās ar vienādu varbūtību , bez aizspriedumiem pret konkrētiem virzieniem vai modeļiem.

Galvenā ideja ir tāda, ka esošajam tīklam tiek pievienoti ceļi, bet, kad nejaušs ceļš krustojas ar sevi, cikls tiek "izdzēsts", un maršruts turpinās no punkta, kur tas kļuva brīvs. Šī detaļa neļauj procesam dot priekšroku liekiem gariem ceļiem vai veidot ciklus, saglabājot struktūru kā koku, kas savieno visas šūnas. Rezultāts ir "taisnīgs" labirints: nevienam ceļam vai pagriezienam nav statistiskas priekšrocības salīdzinājumā ar citu.

Ir kopienas veidoti projekti un sīklietotnes, kas vizuāli un izklaidējoši demonstrē algoritmu darbībā. Starp tām izceļas dažas no Krusa Godara sīklietotnēm, kurās var izvēlēties režģa izmēru un palaist to, lai redzētu, kā soli pa solim veidojas labirints. Vērojot tā darbību, var saprast, kāpēc ciklu dzēšana izlīdzina varbūtības katrā grafika paplašinājumā.

Labirinta veidošana un risināšana, lai gan šķietami atgādina spēles, ir cieši saistīta ar meklēšanas un optimizācijas problēmām. To izstrādei ir nepieciešams līdzsvars starp skaidrību un intrigu, izvairoties no triviāliem risinājumiem vai neiespējamiem strupceļiem; izpētot galīgu telpu ar plašām kombinācijām. Tāpēc gan uz papīra, gan digitālās simulācijās tie kalpo kā lieliski loģikas, varbūtības un pacietības vingrinājumi.

Kā tas darbojas (praktiskā nozīmē)

Zemāk ir sniegts algoritma vispārīgs apraksts bez koda, bet ar būtisko mehāniku, lai izprastu tā darbību. Atcerieties, ka mērķis ir izveidot koku (bez cikliem), kas savieno visas šūnas tā, lai starp jebkuriem diviem punktiem būtu tikai viens vienkāršs ceļš.

• Tas sākas ar tukšu režģi: šūna tiek izvēlēta nejauši un atzīmēta kā koka daļa.
• Nejauši tiek izvēlēta vēl viena šūna, tiek uzsākta pakāpeniska nejauša pastaiga, un, ja ceļš krustojas pats ar sevi, cilpas tiek nekavējoties noņemtas (cilpu dzēšana).
• Kad pastaiga sasniedz jau ģenerētu koku, viss precizētais ceļš (bez cilpām) tiek “pielīmēts” kokam.
• Tas atkārtojas: mēs izvēlamies jaunu nesavienotu šūnu, ejam ar cikla dzēšanu un pievienojamies kokam.
• Galu galā visas šūnas ir savienotas, un labirints ir vienmērīgs nejaušs stiepjošs koks, tāpēc nav virziena vai topoloģisku noviržu.

Salīdzinot ar citām metodēm (piemēram, Aldous-Broder, Prim vai Kruskal, kas pielāgotas labirintiem), Wilson metode izceļas ar aptverošā koka izlases vienmērīgumu. Tās skaitļošanas izmaksas ir saprātīgas tipiskos režģos un, pats galvenais, tā garantē, ka katrs risinājums ir vienlīdz ticams , kas ir ļoti vērtīgi akadēmiskā un simulācijas kontekstā.

Citas nozīmes: Vilsona modelis vai EOQ (krājumi)

Loģistikā Vilsona modelim (sauktam arī par EOQ jeb ekonomisko pasūtījuma daudzumu) nav nekāda sakara ar labirintiem. Tā ir klasiska metode optimālā pasūtījuma daudzuma noteikšanai, lai samazinātu kopējās krājumu izmaksas. To 1934. gadā popularizēja R. H. Vilsons, lai gan sākotnējo koncepciju 1913. gadā ierosināja Fords Vitmens Hariss.

Tās mērķis ir atrast partijas lielumu Q, kas līdzsvaro pasūtījumu veikšanas izmaksas un krājumu uzturēšanas izmaksas. Pamatojoties uz gada pieprasījumu (D), izmaksām uz vienu pasūtījumu (K) un uzglabāšanas izmaksām uz vienu vienību periodā (G), tiek iegūts daudzums, kas, ievērojot tā pieņēmumus, samazina kopējās krājumu izmaksas.

Visizplatītākā formula ir izteikta kā Q = √(2·D·K/G). Šis skaitlis norāda katras partijas lielumu; no tā iegūst gada pasūtījumu skaitu D/Q, un no tā var atvasināt pasūtījumu ciklu. Ir svarīgi arī noteikt atkārtotas pasūtīšanas punktu (ņemot vērā izpildes laiku) un drošības krājumus, lai izvairītos no krājumu trūkuma, lai gan pamatformula tieši neietver nenoteiktību.

Tipiski pielietojumi: To izmanto ar izejvielām vai jebkura veida precēm, kurām var ticami noteikt iegādes un uzglabāšanas izmaksas. Praksē, pietiekami ticami zinot D, K un G, uzņēmums var noteikt partiju lielumu un plānot iepirkumus ar lielāku kontroli.

Vilsona modeļa pieņēmumi, priekšrocības un ierobežojumi

Pieņēmumi ir kritiski svarīgi rezultāta derīgumam. EOQ modelis pieņem, ka pieprasījums ir nemainīgs un zināms, ka vienības cena paliek stabila, ka uzglabāšanas izmaksas ir zināmas un ir atkarīgas no krājumu līmeņa, ka izpildes laiki ir nemainīgi, un turklāt neņem vērā apjoma atlaides.

• Stabils, neatkarīgs pieprasījums bez sezonalitātes vai pēkšņiem pieaugumiem.
• Pirkuma cena analizētajā periodā ir fiksēta vai praktiski nemainīga.
• Zināmas uzglabāšanas izmaksas par vienību un periodu.
• Nav daudzuma atlaižu un tiek nodrošināta tūlītēja vai pastāvīga papildināšana.

Galvenās priekšrocības: to ir vienkārši ieviest, plaši izmantot un tas palīdz samazināt pasūtīšanas un krājumu izmaksas saskaņā ar tā noteikumiem. Ieguvumi ietver samazinātu pārprodukciju, samazinātu krājumu trūkuma risku (apvienojumā ar atkārtotas pasūtīšanas punktu un drošības krājumiem) un uzlabotu skaidrību iepirkumu plānošanā. Daudzas organizācijas to novērtē, jo tas nodrošina vienkāršu skaitlisku pamatu pasūtījumu daudzumu noteikšanai.

Trūkumi: Tā slikti darbojas ar sezonālu vai neregulāru pieprasījumu, ignorē apjoma atlaides un pieņem tūlītēju (vai fiksētu) papildināšanu, kas daudzās piegādes ķēdēs nav reāli. Tāpēc tādās vidēs kā Toyota grupa EOQ formulu ir aizstājušas stabilākas sistēmas, piemēram, Kanban vai Just-in-Time, kas labāk apstrādā faktisko mainīgumu un nepārtrauktu plūsmu.

EOQ (Vilsona) praktiskie piemēri

1. piemērs (tipisks): Uzņēmums ar gada produkciju 10 000 vienību iegādājas 1.000 kg izejvielu. Ja katrs pasūtījums maksā 200 eiro un kopējās gada uzglabāšanas izmaksas ir 2.000 eiro, tad, piemērojot formulu Q = √(2·D·K/G) ar D = 1.000, K = 200 un G = 2.000, iegūst Q ≈ 14,14. Tas liecina par 14 kg partijām un aptuveni 71 pasūtījumam gadā. Tas ir ilustratīvs vingrinājums, kurā ar nelieliem skaitļiem mēs varam redzēt, kā partijas lielums līdzsvaro pasūtījumus un krājumus.

2. piemērs: Sillas Grandes World SL izplata 6.000 krēslu (D), katra pasūtījuma izmaksas ir 300 eiro (K), un gada uzglabāšanas izmaksas par vienību ir 5 eiro (G). Piemērojot vienādojumu, Q ≈ 848,52, kas nozīmē, ka uzņēmums gadā veiktu aptuveni 7,07 pasūtījumus. Ar šādu partijas lielumu uzņēmums tiecas uz efektīvāku krājumu līmeni , samazinot uzglabāšanas izmaksas, būtiski nepalielinot pasūtījumu sagatavošanas izmaksas.

Papildus pašai formulai ieteicams aprēķināt atkārtotas pasūtīšanas punktu, ņemot vērā izpildes laiku un saglabājot drošības krājumus, jo tīrais modelis neņem vērā nenoteiktību. Tas arī nevērtē apjoma atlaižu ietekmi, kas dažkārt varētu kompensēt krājumu izmaksas, ja tiek izmantotas lielākas partijas.

Nejaukt ar Vilsona teorēmu (skaitļu teorija)

Vilsona teorēma pieder pie modulārās aritmētikas un būtībā apgalvo, ka vesels skaitlis n > 1 ir pirmskaitlis tad un tikai tad, ja (n − 1)! ≡ −1 (mod n). Implikācija "ja n ir pirmskaitlis, tad (n − 1)! ≡ −1 (mod n)" parasti tiek stingri saukta par "Vilsona teorēmu", un arī apgrieztā implikācija ir patiesa. Vēsturiski Edvards Vorings rezultātu piedēvēja Džonam Vilsonam (1770), lai gan pirmo zināmo pierādījumu sniedza Lagranžs (1771), un formulējums faktiski datējams ar Alhazenu 11. gadsimtā.

Konkrēts piemērs: ja p = 11, grupējot katru elementu ar tā multiplikatīvo inverso elementu kopā {1, 2, …, p − 1}, kopējais reizinājums ir ≡ −1 (mod p). Visi faktori atceļ viens otru pāros, jo g·g^{-1} ≡ 1, izņemot 1 un p − 1, un tāpēc 10! ≡ −1 (mod 11) . Šī pieeja izmanto faktu, ka, ja p ir pirmskaitlis, (Z/pZ)^× ir multiplikatīva grupa un katram elementam (izņemot 1 un p − 1) ir atšķirīga inversā elementa vērtība.

Ir vairāki pierādījumi. Viena polinoma metode ņem vērā g(x) = (x − 1)(x − 2)···(x − (p − 1)) un f(x) = g(x) − (x^{p−1} − 1). Moduļa p gadījumā f(x) būtu ne vairāk kā p − 2 saknes, ja tas nebūtu nulles polinoms, bet visi 1, 2, …, p − 1 saskaņā ar Fermā Mazo teorēmu padara f(x) par nulli. Tāpēc f(x) ir identiski 0 mod p; konstantais loceklis noved pie (p − 1)! ≡ −1 (mod p).

To neizmanto kā praktisku pirmskaitļu pārbaudi, jo (n − 1)! mod n aprēķināšana lieliem n ir dārga, un pastāv ātrāki testi (piemēram, Millera–Rabina vai deterministiski testi noteiktām rindām). Tomēr to var izmantot, lai secinātu noderīgas īpašības: piemēram, ja p = 2n + 1 ir pirmskaitlis, iegūstam ∏_{j=1}^{n} j^2 ≡ (−1)^{n+1} (mod p). Un, kā daļēju secinājumu, −1 ir kvadrātiskais atlikums pēc modulo p, ja p ≡ 1 (mod 4), jo to var uzrakstīt kā reizinājuma 1·2···2k kvadrātu, ja p = 4k + 1, kas parāda, kad −1 ir kvadrātā starp Z/pZ.

Pastāv arī praktisks "apgrieztais variants": jebkuram saliktam skaitlim n > 5, n dalās ar (n − 1)! Gadījums n = 4 ir klasisks izņēmums (3! nav 4 reizinājums). Viens veids, kā to redzēt, ir saskaitīt pirmskaitļa q pakāpes, kas dala n: (n − 1)! ir pietiekami daudz q reizinājumu, lai nosegtu pakāpi, kas parādās n, izņemot minēto izņēmumu, kas noved pie rezultāta, izņemot gadījumu, kad n = 4.

Gauss vispārināja teorēmu: visu vienību reizinājums pēc moduļa n, ∏_{1≤a<n, (a,n)=1} a, ir ≡ −1 (mod n), ja n ∈ {4, p^k, 2p^k} ar p nepāra pirmskaitli un ≡ 1 (mod n) visos pārējos gadījumos. No galīgu Ābela grupu viedokļa visu to elementu reizinājums ir vienība, ja vien nepastāv tieši viens otrās kārtas elements, tādā gadījumā reizinājums ir šis otrās kārtas elements.

Ilustratīva tabula (n − 1)! mod n, ja n = 2…30

Nākamajā tabulā ir parādītas konkrētas n vērtības no 2 līdz 30. Pirmskaitļiem atlikums (n − 1)!, dalīts ar n, ir vienāds ar n − 1 (kas ir ≡ −1 mod n). Saliktiem skaitļiem atlikums bieži ir 0. Salīdzinājumam ir iekļauts arī −1 mod n. Šie dati skaidri ilustrē, kā Vilsona teorēma uzvedas mazos gadījumos, un palīdz nostiprināt intuīciju.

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

Pielietojums, ierobežojumi un ieteikumi

Ja vēlaties ģenerēt objektīvus labirintus, izmantojiet Vilsona algoritmu: tā pamatā ir nejaušas pastaigas ar ciklu dzēšanu, kas nodrošina vienmērīgus kokus. Krājumu pārvaldībai Vilsona modelis ir noderīgs, ja pieprasījums, cenas un izmaksas ir stabilas un precīzi zināmas; mainīgās vidēs piemērotākas var būt tādas metodoloģijas kā Kanban, Just-in-Time vai uzlabota plānošanas programmatūra. Savukārt matemātikā Vilsona teorēma ir teorētisks dārgakmens ar interesantiem atvasinājumiem (piemēram, kvadrātvienādojumiem), taču tā nav praktiska kā pirmskaitļu pārbaude lieliem skaitļiem.

Nav vienas formulas pasūtīšanas un uzglabāšanas izmaksu aprēķināšanai: katram uzņēmumam ir jāsadala stundas, procesi, transportēšana, saņemšana, personāls, īre, enerģija, apdrošināšana un finanšu izmaksas. Daudzi speciālisti aprēķina stundas katrā operācijā un piemēro stundas likmi monetizācijai. Šī pielāgošana ir būtiska, lai nodrošinātu, ka aprēķinātais pasūtījuma daudzums (Q) ir noderīgs un kopā ar labu atkārtotas pasūtīšanas punktu un drošības krājumiem palīdz izvairīties no krājumu trūkuma vai pārmērīgas uzkrāšanās.

Ir vērts atcerēties, ka termins "Vilsona algoritms" meklēšanā parasti norāda uz labirinta ģeneratoru, savukārt "Vilsona modelis" jeb "EOQ" attiecas uz inventāriem, bet "Vilsona teorēma" - uz skaitļu teoriju. To atšķiršana jau no paša sākuma ļauj izvairīties no neskaidrībām un labāk izmantot katru pieeju: objektīvus labirintus, optimālas partijas ar reālistiskiem pieņēmumiem un elegantu pirmskaitļu raksturojumu, kas, lai gan nav praktisks pirmskaitļu pierādījums, joprojām ir vērtīga matemātiskās mīklas sastāvdaļa.