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

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

Internetā cilvēki terminu "Vilsons" lieto ļoti dažādiem mērķiem, un tas ir diezgan mulsinoši: pastāv Vilsona algoritms labirintu ģenerēšanai, Vilsona modelis (jeb EOQ) inventāram un Vilsona teorēma skaitļu teorijā. Šajā rakstā mēs visu noskaidrojam, sākot ar sākotnējo lietojumu labirintos un rūpīgi nošķirot citas nozīmes, jo Tie nav vienādi 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. Jūs 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 jūs varētu jūs varat identificēt katru jēdzienu un to pareizi 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 lielākā 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 ceļi tiek pievienoti jau konstruētajai kopai, bet, kad nejauša pastaiga krustojas ar sevi, cikls tiek "dzēsts" un maršruts turpinās no vietas, kur tas apstājās. Šī detaļa neļauj procesam radīt garus, liekus ceļus vai ciklus, saglabājot struktūru kā koku, kas savieno visas šūnas. Rezultāts ir "taisnīgs" labirints: nevienam koridoram vai pagriezienam nav statistiskas priekšrocības salīdzinājumā ar citu.

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

Labirinta veidošana un risināšana ir uzdevumi, kas, lai gan var šķist kā spēles, ir cieši saistīti ar meklēšanas un optimizācijas problēmām. To izstrādei nepieciešams līdzsvars starp skaidrību un interesi, izvairoties no triviāliem risinājumiem vai strupceļiem; izpētīt ierobežotu telpu ar milzīgām kombinācijām. Tāpēc gan uz papīra, gan digitālajās simulācijās tie darbojas kā Lieliski vingrinājumi loģikā, varbūtībā un pacietībā.

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

Zemāk ir sniegts algoritma vispārīgs apraksts bez koda, bet ar būtiskāko 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 punktu pāriem ir 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, Oldusa-Brodera, Prim vai Kruskals, kas pielāgots labirintiem), Vilsons izceļas ar ģenerējošā koka izlases vienmērīgumu. Tā skaitļošanas izmaksas ir saprātīgas tipiskos režģos un, pats galvenais, nodrošina, ka katrs risinājums ir vienlīdz ticams, kas ir ļoti novērtēts akadēmiskajā un simulācijas kontekstā.

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

Loģistikā “Vilsona modelim” (sauktam arī par EOQ — ekonomisko pasūtījuma daudzumu; vai CEP — ekonomisko pasūtījuma daudzumu) nav nekāda sakara ar labirintiem. Tā ir klasiska metode optimālā pasūtījuma daudzuma noteikšanai ar mērķi samazināt kopējās krājumu izmaksas. To 1934. gadā popularizēja R.H. Vilsons, lai gan Pirmo priekšlikumu izvirzīja Fords Vitmens Hariss 1913. gadā..

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

Visizplatītākā formula ir Q = √(2 D K/G). Tā norāda partijas lielumu; no tā iegūst gada pasūtījumu skaitu D/Q, un no tā var atvasināt laika ritmu. Ir svarīgi arī iestatīt 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 neietver nenoteiktību nepārprotami.

Tipiski pielietojumi: izmanto ar izejvielām vai jebkura veida precēm, kurām var ticami noteikt iegādes un uzglabāšanas izmaksas. Praksē, ja D, K un G ir zināmi ar pietiekamu ticamību, Uzņēmums var noteikt partiju izmērus un plānot to piegādi. ar lielāku kontroli.

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

Pieņēmumi ir kritiski svarīgi rezultātu 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 piegādes laiki ir nemainīgi un turklāt, neparedz 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 atbilstoši jūsu apstākļiem. Tā priekšrocības ietver samazinātu pārmērīgu krājumu veidošanos, samazinātu krājumu trūkuma risku (ja to papildina atkārtotas pasūtīšanas punkts un drošības krājumi), kā arī skaidrību iepirkumu plānošanā. Daudzas organizācijas to novērtē, jo piedāvā vienkāršu skaitlisku pamatu, lai izlemtu, cik daudz pasūtīt.

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 Group EOQ formulu ir aizstājušas stabilākas sistēmas, piemēram, Kanban vai Just in Time, kas Viņi labāk tiek galā ar reālu mainīgumu un nepārtrauktā plūsma.

EOQ (Vilsona) praktiskie piemēri

1. piemērs (tipisks): Uzņēmums ar gada produkciju 10 000 vienību iepērk 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), kur D = 1.000, K = 200, G = 2.000, iegūst Q ≈ 14,14. Tas liecina par 14 kg partijām un aptuveni 71 pasūtījumiem gadā. Šis ir ilustratīvs vingrinājums, kurā ar nelieliem skaitļiem mēs varam redzēt, ka 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 uzglabāšanas izmaksas par vienību gadā ir 5 eiro (G). Piemērojot vienādojumu, Q ≈ 848,52, tad gadā būtu aptuveni 7,07 pasūtījumi. Ar šādu partijas lielumu uzņēmums tiecas uz efektīvāku krājumu līmeni, samazinot uzglabāšanas izmaksas, nepalielinot pasūtījumu sagatavošanas izmaksas.

Papildus formulai ir ieteicams aprēķināt atkārtotas pasūtīšanas punktu, ņemot vērā izpildes laiku un drošības krājumu uzturēšanu, jo tīrais modelis neņem vērā nenoteiktību. Tas arī nevērtē apjoma atlaižu ietekmi, kas dažreiz 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ā aritmētika 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)” bieži 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 patiesībā, Formulējuma pirmsākumi meklējami Alhacena 11. gadsimtā..

Konkrēts piemērs: ja p = 11, grupējot katru elementu ar tā multiplikatīvo apgriezto vērtību kopā {1, 2, …, p − 1}, kopējais reizinājums kļūst ≡ −1 (mod p). Visi faktori vienmērīgi atceļas, ja g g^{-1} ≡ 1, izņemot 1 un p − 1, un tātad 10! ≡ −1 (mod 11)Šī pieeja izmanto, ka ar p pirmskaitli (Z/pZ)^× ir multiplikatīva grupa, un katram elementam (izņemot 1 un p − 1) ir atšķirīgs inverss elements.

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). Modulim p, f(x) būtu ne vairāk kā p − 2 saknes, ja tas nebūtu nulles polinoms, bet visi 1, 2, …, p − 1 izzustu no f(x) saskaņā ar Fermā mazo teorēmu. Tādējādi f(x) ir identiski 0 mod p, un neatkarīgais loceklis noved pie (p − 1)! ≡ −1 (mod p).

To neizmanto kā praktisku pirmskaitļu testu, 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 konkrētiem diapazoniem). Tomēr ir lietderīgi secināt noderīgas īpašības: piemēram, ja p = 2n + 1 ir pirmskaitlis, tad mums ir ∏_{j=1}^{n} j^2 ≡ (−1)^{n+1} (mod p). Un, kā daļējs secinājums, −1 ir kvadrātiskais atlikums ar 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āts Z/pZ.

Pastāv arī praktisks “apgrieztais variants”: jebkuram saliktam skaitlim n > 5 ir taisnība, ka 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 norādīto izņēmumu, kas noved pie rezultāta, izņemot gadījumus, kad n = 4.

Gauss vispārināja teorēmu: visu vienību reizinājums ar moduli n, ∏_{1≤a Tas ir 2. kārtas elements.

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

Nākamajā tabulā var redzēt konkrētas n vērtības no 2 līdz 30. Ja n ir pirmskaitlis, atlikums (n − 1)!, dalīts ar n, ir vienāds ar n − 1 (kas ir ≡ −1 mod n). Saliktos materiālos atlikums bieži ir 0. Salīdzinājumam ir iekļauts arī −1 mod n. Šie dati ļoti labi ilustrē, kā Vilsona teorēma darbojas mazos gadījumos, un palīdz labot 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ā bāze nejaušās pastaigās ar ciklu dzēšanu nodrošina vienmērīgus kokus. Krājumiem 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, JIT 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ātiskajiem atlikumiem), bet Tas nav praktiski kā primitivitātes tests. lieliem skaitļiem.

Nav vienas universālas formulas pasūtīšanas un uzglabāšanas izmaksu aprēķināšanai: katram uzņēmumam ir jāsadala stundas, procesi, transports, 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, lai gūtu peļņu. Šī pielāgošana ir būtiska, lai aprēķinātais Q būtu noderīgs, un kopā ar labu atkārtotas pasūtīšanas punktu un drošības krājumiem, izvairīties no krājumu trūkuma vai pārmērīgas inventāra.

Ir vērts atcerēties, ka termins "Vilsona algoritms" meklēšanā parasti attiecas uz labirinta ģeneratoru, savukārt "Vilsona modelis" jeb "EOQ" attiecas uz inventāru, un "Vilsona teorēma" attiecas uz skaitļu teoriju. To atšķiršana jau no paša sākuma ļauj izvairīties no neskaidrībām un ļauj labāk izmantot katru pieeju: Objektīvi labirinti, optimālas partijas ar reālistiskiem pieņēmumiem un elegants pirmskaitļu raksturojums kas, lai gan nav praktisks pirmskaitļu tests, tomēr ir vērtīga matemātiskās mīklas sastāvdaļa.