Wilson's Algorithm: Kumpletong Gabay, Mga Pagkakaiba sa EOQ at sa Theorem

Informatec Digital » Pag-iinhinyero » Wilson's Algorithm: Kumpletong Gabay, Mga Pagkakaiba sa EOQ at sa Theorem

Sa Internet, ginagamit ng mga tao ang terminong "Wilson" para sa iba't ibang layunin, at ito ay medyo nakakalito: nariyan ang Wilson algorithm para sa pagbuo ng mga maze, ang Wilson Model (o EOQ) para sa mga imbentaryo, at ang Wilson's theorem sa number theory. Sa artikulong ito, nilinaw namin ang lahat, simula sa orihinal na paggamit sa mga maze at maingat na nakikilala ang iba pang mga kahulugan, dahil Hindi sila pareho at hindi rin sila nag-aaplay sa parehong lugar.

Kung nakakita ka ng demo o applet kung saan "lumalaki" ang isang maze nang mag-isa, malamang na nakatagpo ka na ng algorithm ni Wilson. Narinig mo na rin ang Wilson Model para sa pagkalkula ng economic order quantity o maging ang theorem na nagpapakilala sa mga prime number gamit ang mga factorial. Dito makikita mo ang isang kumpletong paliwanag na may mga halimbawa, para magawa mo matutukoy mo ang bawat konsepto at magagamit mo ito ng maayos.

Ano ang algorithm ni Wilson para sa mga maze?

Ang algorithm ni Wilson ay isang paraan ng pagbuo ng maze batay sa mga loop-erased random na paglalakad. Ang malaking kalamangan nito ay ang paggawa nito ng isang pare-parehong random na sumasaklaw na puno sa ibabaw ng grid: ilagay lang, Ang bawat posibleng maze ay lilitaw na may parehong posibilidad, nang walang pagkiling sa mga partikular na direksyon o pattern.

Ang pangunahing ideya ay ang mga path ay idinagdag sa nakagawa na set, ngunit kapag ang isang random na paglalakad ay nagsalubong sa sarili nito, ang loop ay "tinatanggal" at ang ruta ay nagpapatuloy mula sa kung saan ito tumigil. Pinipigilan ng detalyeng ito ang proseso mula sa paglikha ng mahaba, paulit-ulit na mga landas o mga loop, na pinapanatili ang istraktura bilang isang puno na nagkokonekta sa lahat ng mga cell. Ang resulta ay isang "patas" na maze: walang koridor o liko ang may istatistikal na kalamangan sa iba.

Mayroong mga proyekto at applet na nilikha ng komunidad na nagpapakita ng pagkilos ng algorithm sa isang visual at lubos na nakakaaliw na paraan. Kabilang sa mga ito, namumukod-tangi ang ilang applet ni Cruz Godar, kung saan maaari mong piliin ang laki ng grid at itakda ito upang gumana upang makita kung paano umusbong ang maze nang hakbang-hakbang. Ang panonood nito ay nakakatulong na maunawaan mo kung bakit. Ang pagbubura ng loop ay nagpapapantay sa mga posibilidad sa bawat extension ng graph.

Ang pagbuo at paglutas ng mga maze ay mga gawain na, bagama't tila mga laro ang mga ito, ay malapit na nauugnay sa mga problema sa paghahanap at pag-optimize. Ang pagdidisenyo ng mga ito ay nangangailangan ng balanse sa pagitan ng kalinawan at interes, pag-iwas sa mga walang kuwentang solusyon o dead ends; galugarin ang isang may hangganang espasyo na may napakalaking kumbinasyon. Samakatuwid, pareho sa papel at sa digital simulation, gumagana ang mga ito bilang Mahusay na pagsasanay sa lohika, posibilidad at pasensya.

Paano ito gumagana (sa mga praktikal na termino)

Nasa ibaba ang isang mataas na antas ng paglalarawan ng algorithm, nang walang code ngunit may mahahalagang mekanika upang maunawaan ang pag-uugali nito. Tandaan na ang layunin ay bumuo ng isang puno (nang walang mga cycle) na nag-uugnay sa lahat ng mga cell, tulad na mayroon lamang isang simpleng landas sa pagitan ng anumang pares ng mga puntos.

• Nagsisimula ito sa isang walang laman na grid: ang isang cell ay pinili nang random at minarkahan bilang bahagi ng puno.
• Ang isa pang cell ay pinili nang random, ang isang step-by-step na random na paglalakad ay sinimulan, at kung ang landas ay tumatawid sa sarili nito, ang mga loop ay agad na tinanggal (loop-erasing).
• Kapag ang paglalakad ay umabot sa nabuo nang puno, ang buong pinong landas (walang mga loop) ay "nakadikit" sa puno.
• Umuulit ito: pumili kami ng bagong hindi nakakonektang cell, lumakad nang may loop na pagtanggal at sumali sa puno.
• Sa huli, ang lahat ng mga cell ay konektado at ang maze ay isang pare-parehong random na spanning tree, kaya walang direksyon o topological biases.

Kung ikukumpara sa ibang mga pamamaraan (tulad ng Aldous–Broder, ayos na ayos o Kruskal na inangkop sa labyrinths), namumukod-tangi si Wilson para sa pagkakapareho ng sampling ng bumubuo ng puno. Ang computational cost nito ay makatwiran sa mga tipikal na grids at, higit sa lahat, tinitiyak na ang bawat solusyon ay pantay na posibilidad, isang bagay na lubos na pinahahalagahan sa mga konteksto ng akademiko at simulation.

Iba pang kahulugan: Wilson Model o EOQ (mga imbentaryo)

Sa logistik, ang "Wilson Model" (tinatawag ding EOQ, Economic Order Quantity; o CEP, Economic Order Quantity) ay walang kinalaman sa mga maze. Ito ay isang klasikong paraan para sa pagtukoy ng pinakamainam na dami ng order na may layuning bawasan ang kabuuang halaga ng imbentaryo. Ito ay pinasikat noong 1934 ni R.H. Wilson, bagaman Ang unang panukala ay ni Ford Whitman Harris noong 1913.

Ang layunin nito ay mahanap ang lot size Q na nagbabalanse sa halaga ng pag-order at sa halaga ng paghawak ng stock. Mula sa taunang demand (D), ang cost per order (K), at ang storage cost per unit at period (G), isang dami ang nakuha na, sa loob ng balangkas ng mga pagpapalagay nito, binabawasan ang kabuuang halaga ng imbentaryo.

Ang pinakakaraniwang formula ay Q = √(2 D K/G). Nagbibigay ito ng laki ng batch; mula doon, ang bilang ng mga taunang order ay magiging D/Q, at mula dito maaari mong makuha ang time cadence. Mahalaga rin na itakda ang reorder point (isinasaalang-alang ang lead time) at ang stock na pangkaligtasan upang maiwasan ang mga stockout, bagama't ang ang pangunahing formula ay hindi nagsasama ng kawalan ng katiyakan tahasan.

Mga tipikal na aplikasyon: ginagamit kasama ng mga hilaw na materyales o anumang uri ng paninda kung saan maaasahang matukoy ang mga gastos sa pagbili at pag-iimbak. Sa pagsasagawa, kung kilala ang D, K, at G na may sapat na pagiging maaasahan, Maaaring sukatin ng kumpanya ang mga batch nito at iiskedyul ang kanilang supply na may higit na kontrol.

Mga pagpapalagay, pakinabang at limitasyon ng Wilson Model

Ang mga pagpapalagay ay kritikal sa bisa ng mga resulta. Ipinapalagay ng modelong EOQ na ang demand ay pare-pareho at kilala, na ang presyo ng yunit ay nananatiling matatag, na ang mga gastos sa pag-iimbak ay kilala at nakadepende sa antas ng imbentaryo, na ang mga oras ng supply ay pare-pareho, at, higit pa rito, ay hindi nag-iisip ng mga diskwento sa dami.

• Matatag, independiyenteng pangangailangan, walang seasonality o biglaang mga peak.
• Presyo ng pagbili naayos o halos hindi nagbabago sa panahon ng pagsusuri.
• Mga kilalang halaga ng imbakan bawat yunit at panahon.
• Walang mga diskwento sa dami at agaran o patuloy na muling pagdadagdag.

Pangunahing bentahe: Ito ay simpleng ipatupad, malawakang ginagamit, at nakakatulong na mabawasan ang mga gastos sa pag-order at imbentaryo sa ilalim ng iyong mga kundisyon. Kabilang sa mga benepisyo nito ang pagbawas ng overstocking, pagbabawas ng panganib ng stockouts (kung may kasamang reorder point at safety stock), at kalinawan sa pagpaplano ng pagbili. Pinahahalagahan ito ng maraming organisasyon dahil nag-aalok ng isang simpleng numerical na batayan para sa pagpapasya kung magkano ang order.

Mga Disadvantage: Hindi ito gumagana nang maayos sa pana-panahon o hindi regular na demand, binabalewala ang mga diskwento sa dami, at ipinapalagay ang agarang (o nakapirming) muling pagdadagdag, na hindi makatotohanan sa maraming supply chain. Samakatuwid, sa mga kapaligiran tulad ng Toyota Group, ang EOQ formula ay inilipat ng mas matatag na mga sistema tulad ng Kanban o Just in Time, na Mas mahusay nilang pinangangasiwaan ang tunay na pagkakaiba-iba at ang tuluy-tuloy na daloy.

Mga praktikal na halimbawa ng EOQ (Wilson)

Halimbawa 1 (karaniwang): Ang isang kumpanya na may taunang produksyon na 10.000 unit ay bumibili ng 1.000 kg ng hilaw na materyal. Kung ang bawat order ay nagkakahalaga ng €200 at ang kabuuang taunang halaga ng imbakan ay €2.000, ang paglalapat ng formula na Q = √(2 D K/G) na may D = 1.000, K = 200, G = 2.000 ay nagbibigay ng Q ≈ 14,14. Ito ay nagmumungkahi ng mga batch ng 14 kg at humigit-kumulang 71 mga order bawat taon. Ito ay isang mapaglarawang ehersisyo kung saan, na may katamtamang mga numero, makikita natin Paano binabalanse ng laki ng lot ang mga order at stock.

Halimbawa 2: Ang Sillas Grandes World SL ay namamahagi ng 6.000 upuan (D), ang bawat order ay nagkakahalaga ng €300 (K) at ang imbakan bawat yunit bawat taon ay €5 (G). Ang paglalapat ng equation, Q ≈ 848,52, pagkatapos ay gagawa ito ng humigit-kumulang 7,07 na mga order bawat taon. Sa laki ng lot na ito, ang firm ay patungo sa isang mas mahusay na antas ng imbentaryo, binabawasan ang mga gastos sa pag-iimbak nang hindi tumataas ang mga gastos sa paghahanda ng order.

Higit pa sa formula, magandang ideya na kalkulahin ang reorder point na isinasaalang-alang ang lead time at pagpapanatili ng stock na pangkaligtasan, dahil ang purong modelo ay hindi isinasaalang-alang ang kawalan ng katiyakan. Hindi rin nito tinatantya ang epekto ng mga diskwento sa dami, na kung minsan maaaring mabawi ang mga gastos sa stock kung mas malalaking lote ang gagamitin.

Hindi dapat malito sa teorama ni Wilson (teorya ng numero)

Ang teorama ni Wilson ay kabilang sa modular arithmetic at mahalagang sinasabi na ang isang integer n > 1 ay prime kung at kung lamang (n − 1)! ≡ −1 (mod n). Ang implikasyon na "kung n ay prime kung gayon (n − 1)! ≡ −1 (mod n)" ay madalas na mahigpit na tinatawag na "Wilson's theorem", at ang kabaligtaran na implikasyon ay totoo rin. Sa kasaysayan, iniugnay ni Edward Waring ang resulta kay John Wilson (1770), bagaman ang unang kilalang patunay ay ibinigay ni Lagrange (1771), at sa katunayan, Ang pormulasyon ay itinayo noong Alhacen noong ika-11 siglo.

Konkretong halimbawa: para sa p = 11, kapag pinagsama-sama ang bawat elemento sa multiplicative inverse nito sa set {1, 2, …, p − 1}, ang kabuuang produkto ay nagiging ≡ −1 (mod p). Ang lahat ng salik ay pantay na nagkansela bilang g g^{-1} ≡ 1, maliban sa 1 at p − 1, at iba pa 10! ≡ −1 (mod 11)Ginagamit ng diskarteng ito na, na may p prime, (Z/pZ)^× ay isang multiplicative na pangkat at bawat elemento (maliban sa 1 at p − 1) ay may natatanging inverse.

Mayroong ilang mga patunay. Isinasaalang-alang ng isang polynomial technique ang g(x) = (x − 1)(x − 2)···(x − (p − 1)) at f(x) = g(x) − (x^{p−1} − 1). Ang modulus p, f(x) ay magkakaroon ng hindi hihigit sa p − 2 na mga ugat kung hindi ito ang null polynomial, ngunit ang lahat ng 1, 2, …, p − 1 ay mawawala f(x) ng maliit na teorama ni Fermat. Kaya ang f(x) ay magkaparehong 0 mod p at ang independiyenteng termino ay humahantong sa (p − 1)! ≡ −1 (mod p).

Hindi ito ginagamit bilang isang praktikal na primality test, dahil ang computing (n − 1)! Ang mod n para sa malalaking n ay mahal at may mas mabilis na mga pagsubok (gaya ng Miller–Rabin o mga deterministikong pagsubok para sa mga partikular na hanay). Gayunpaman, kapaki-pakinabang na maghinuha ng mga kapaki-pakinabang na katangian: halimbawa, kung ang p = 2n + 1 ay prime, mayroon tayong ∏_{j=1}^{n} j^2 ≡ (−1)^{n+1} (mod p). At, bilang partial corollary, −1 ay isang quadratic residue modulo p kung p ≡ 1 (mod 4), dahil maaari itong isulat bilang square ng produkto 1 2 2k kapag p = 4k + 1, na nagpapakita kung ang −1 ay parisukat sa Z/pZ.

Mayroon ding praktikal na “inverse”: para sa anumang composite n > 5, totoo na n divide (n − 1)!. Ang case n = 4 ay ang classic exception (3! ay hindi multiple ng 4). Ang isang paraan upang makita ito ay ang bilangin ang mga kapangyarihan ng isang prime q na naghahati sa n: sa (n − 1)! mayroong sapat na multiple ng q upang masakop ang kapangyarihan na lumilitaw sa n, maliban sa ipinahiwatig na pagbubukod, na humahantong sa resulta maliban sa n = 4.

Si Gauss ay nag-generalize ng theorem: ang produkto ng lahat ng unit modulo n, ∏_{1≤a Ito ang elemento ng order 2.

Mapaglarawang talahanayan ng (n − 1)! mod n para sa n = 2…30

Sa sumusunod na talahanayan maaari mong makita ang mga partikular na halaga para sa n sa pagitan ng 2 at 30. Para sa n na prime, ang natitira sa (n − 1)! kapag hinati sa n ay katumbas ng n − 1 (na ≡ −1 mod n). Sa mga composite, ang natitira ay madalas na 0. −1 mod n ay kasama rin para sa paghahambing. Ang data na ito ay naglalarawan nang mahusay kung paano kumikilos ang teorama ni Wilson sa maliliit na kaso at nakakatulong ito ayusin ang intuwisyon.

Mga aplikasyon, limitasyon at rekomendasyon

Kung naghahanap ka upang makabuo ng walang pinapanigan na mga maze, gamitin ang algorithm ni Wilson: ang batayan nito sa mga random na paglalakad na may pagtanggal ng loop ay nagsisiguro ng magkakatulad na mga puno. Para sa mga imbentaryo, ang Wilson Model ay kapaki-pakinabang kapag ang demand, mga presyo, at mga gastos ay matatag at tiyak na alam; sa mga pabagu-bagong kapaligiran, maaaring mas angkop ang mga pamamaraan tulad ng Kanban, JIT, o advanced na software sa pagpaplano. At sa matematika, ang teorema ni Wilson ay isang teoretikal na hiyas na may kawili-wiling mga derivasyon (tulad ng mga parisukat na nalalabi), ngunit Hindi ito praktikal bilang isang primality test para sa malalaking numero.

Walang formula na "one-size-fits-all" para sa pagkalkula ng mga gastos sa pag-order at pag-iimbak: dapat hatiin ng bawat kumpanya ang mga oras, proseso, transportasyon, pagtanggap, mga tauhan, upa, enerhiya, insurance, at mga gastos sa pananalapi. Tinatantya ng maraming propesyonal ang mga oras bawat operasyon at naglalapat ng oras-oras na rate para kumita. Ang pagpapasadyang ito ay susi upang gawing kapaki-pakinabang ang kinakalkulang Q at, kasama ng isang magandang reorder point at safety stock, maiwasan ang mga stockout o labis na imbentaryo.

Ito ay nagkakahalaga ng pag-alala na ang terminong "Wilson's algorithm" sa mga paghahanap ay karaniwang tumutukoy sa maze generator, habang ang "Wilson's model" o "EOQ" ay tumutukoy sa mga imbentaryo, at "Wilson's theorem" ay tumutukoy sa number theory. Ang pagkilala sa kanila mula sa simula ay maiiwasan ang pagkalito at nagbibigay-daan sa iyong mas mahusay na magamit ang bawat diskarte: Walang pinapanigan na mga maze, pinakamainam na batch sa ilalim ng makatotohanang mga pagpapalagay, at isang eleganteng katangian ng mga prime na, bagama't hindi isang praktikal na primality test, ay isang mahalagang piraso pa rin ng mathematical puzzle.

Kaugnay na artikulo:

Kruskal's Algorithm at ang Aplikasyon nito sa Mga Graph