I-Wilson's Algorithm: Umhlahlandlela Ophelele, Umehluko nge-EOQ kanye neTheorem

Informatec Digital » Ubunjiniyela » I-Wilson's Algorithm: Umhlahlandlela Ophelele, Umehluko nge-EOQ kanye neTheorem

Ku-inthanethi, igama elithi "Wilson" lisetshenziselwa izinto eziningi ezahlukene, okuyinto edidayo kakhulu: kukhona i-algorithm kaWilson yokukhiqiza ama-maze, i-Wilson Inventory Model (noma i-EOQ), kanye ne-Wilson's theorem ku-number theory. Kulesi sihloko, sichaza konke, siqala ngokusetshenziswa kwayo kwasekuqaleni kuma-maze futhi sihlukanise ngokucophelela ezinye izincazelo, ngoba azifani futhi azisebenzi ensimini efanayo.

Uma uke wabona idemo noma i-applet lapho i-maze "ikhula" yodwa, cishe usuvele uhlangane ne-algorithm kaWilson. Kungenzeka ukuthi uke wezwa nge-Wilson Model yokubala inani le-oda lezomnotho noma ngisho ne-theorem echaza izinombolo eziyinhloko kusetshenziswa ama-factorial. Lapha uzothola incazelo ephelele enezibonelo, ukuze ukwazi ukubona umqondo ngamunye bese uwusebenzisa kahle.

Iyini i-algorithm kaWilson yama-mazes?

I-algorithm kaWilson iyindlela yokukhiqiza i-maze esekelwe ekuhambeni okungahleliwe okusulwe nge-loop. Inzuzo yayo eyinhloko ukuthi ikhiqiza umuthi obanzi ongahleliwe ofanayo kugridi: kalula nje, yonke i-maze engenzeka ivela inethuba elifanayo , ngaphandle kokuchelela eziqondisweni noma emaphethini athile.

Umqondo oyinhloko ukuthi izindlela zenezelwa kunethiwekhi ekhona, kodwa lapho indlela engahleliwe izihlanganisa, iluphu "iyasulwa," bese umzila uqhubeka kusukela lapho waba khona ukhululekile. Le mininingwane ivimbela inqubo ekuthandeni izindlela ezinde eziphindaphindayo noma ekudaleni imijikelezo, igcine isakhiwo njengesihlahla esixhumanisa wonke amaseli. Umphumela uba yi-maze "efanele": akukho ndlela noma ukujika okunenzuzo yezibalo ngaphezu kwenye.

Kukhona amaphrojekthi nama-applet adalwe ngumphakathi abonisa ngokubonakalayo nangokujabulisayo i-algorithm isebenza. Phakathi kwawo, amanye ama-applet kaCruz Godar avelele, lapho ungakhetha khona usayizi wegridi bese uwusebenzisa ukuze ubone ukuthi i-maze ivela kanjani isinyathelo ngesinyathelo. Ukuyibuka isebenza kukusiza ukuthi uqonde ukuthi kungani ukusula i-loop kulinganisa amathuba esandiso ngasinye segrafu.

Ukwakha nokuxazulula ama-maze, yize kubonakala sengathi imidlalo, kuhlobene kakhulu nezinkinga zokusesha nokwenza ngcono. Ukuwaklama kudinga ibhalansi phakathi kokucaca nokuthakazelisa, ukugwema izixazululo ezincane noma iziphetho ezingenakwenzeka; ukuhlola indawo elinganiselwe enezinhlanganisela ezinkulu. Ngakho-ke, kokubili ephepheni kanye nasekulingiseni kwedijithali, kusebenza njengezivivinyo ezinhle kakhulu ekucabangeni, emathubeni, kanye nasekubekezeleni.

Isebenza kanjani (ngokwemibandela)

Ngezansi incazelo esezingeni eliphezulu ye-algorithm, ngaphandle kwekhodi kodwa ngendlela ebalulekile yokuqonda ukuziphatha kwayo. Khumbula ukuthi umgomo ukwakha umuthi (ngaphandle kwemijikelezo) oxhumanisa wonke amaseli, ukuze kube nendlela eyodwa elula phakathi kwamaphuzu amabili.

• Iqala ngegridi engenalutho: iseli likhethwa ngokungahleliwe futhi limakwe njengengxenye yesihlahla.
• Elinye iseli likhethwa ngokungahleliwe, ukuhamba kwesinyathelo ngesinyathelo okungahleliwe kuyaqalwa, futhi uma indlela iziphambana yona, izihibe zisuswa ngokushesha (i-loop-erasing).
• Lapho uhambo lufinyelela esihlahleni esivele senziwa, yonke indlela ecwengiwe (ngaphandle kwama-loops) "inamathiselwe" esihlahleni.
• Iyaphinda: sikhetha iseli entsha engaxhunyiwe, hamba ngokususa iluphu bese ujoyina isihlahla.
• Ekugcineni, wonke amangqamuzana axhunyiwe futhi i-maze iyisihlahla esifanayo esinqamula ngokungahleliwe, ngakho-ke akukho ukuchema okuqondile noma kwe-topological.

Uma kuqhathaniswa nezinye izindlela (ezifana ne-Aldous-Broder, i-Prim , noma i-Kruskal ezivumelaniswe nama-maze), i-Wilson ivelele ngokufana kokuthatha amasampula esihlahla sayo esibanzi. Izindleko zayo zokubala zifanelekile kumagridi ajwayelekile futhi, ngaphezu kwakho konke, iqinisekisa ukuthi ikhambi ngalinye liyakwazi ukuhlonyiswa , into ebaluleke kakhulu ezimweni zezemfundo kanye nokulingisa.

Ezinye izincazelo: Wilson Model noma EOQ (intories)

Kwezokuthutha, imodeli ye-Wilson (ebizwa nangokuthi i-EOQ, i-Economic Order Quantity) ayihlobene neze nama-maze. Kuyindlela ejwayelekile yokunquma inani elifanele le-oda ukuze kuncishiswe izindleko eziphelele zempahla. Yathandwa kakhulu ngo-1934 ngu-R.H. Wilson, yize umqondo wokuqala waphakanyiswa nguFord Whitman Harris ngo-1913.

Inhloso yayo ukuthola usayizi we-lot Q olinganisa izindleko zokubeka ama-oda kanye nezindleko zokubamba isitokwe. Ngokusekelwe esidingweni sonyaka (D), izindleko nge-oda (K), kanye nezindleko zokugcina ngeyunithi ngesikhathi (G), inani elitholakalayo, ngaphakathi kohlaka lwezibikezelo zalo, elinciphisa izindleko zesitokwe esiphelele.

Ifomula evame kakhulu ivezwa njengo-Q = √(2·D·K/G). Lesi sibalo sinikeza usayizi webhetshi ngayinye; kusukela lapho, inani lama-oda wonyaka lizoba yi-D/Q, futhi ngalokhu ungathola umjikelezo we-oda. Kubalulekile futhi ukusetha iphuzu loku-oda kabusha (kucatshangelwa isikhathi sokuhola) kanye nesitoko sokuphepha ukuze ugweme ukuphela kwesitoko, yize ifomula eyisisekelo ingafaki ngokusobala ukungaqiniseki.

Izicelo ezijwayelekile: Isetshenziswa nezinto zokusetshenziswa noma yiluphi uhlobo lwempahla lapho izindleko zokuthenga nokugcina zinganqunywa khona ngokwethembeka. Empeleni, ngokwazi u-D, u-K, no-G ngokuthembeka okwanele, inkampani ingalinganisa amaqoqo ayo futhi ihlele ukuthengwa kwayo ngokulawula okukhulu.

Okucatshangwayo, izinzuzo kanye nemikhawulo ye-Wilson Model

Ukuqagela kubalulekile ekubalukeni komphumela. Imodeli ye-EOQ icabanga ukuthi isidingo sihlala njalo futhi siyaziwa, ukuthi intengo yeyunithi ihlala izinzile, ukuthi izindleko zokugcina ziyaziwa futhi zincike ezingeni lesitoko, ukuthi izikhathi zokuhola zihlala njalo, futhi, ngaphezu kwalokho, ayicabangi ngezaphulelo zevolumu.

• Ukufunwa okuzinzile, okuzimele, ngaphandle kwesizini noma ukuphakama okungazelelwe.
• Intengo yokuthenga ilungisiwe noma cishe ayishintshile phakathi nesikhathi esicutshungulwayo.
• Izindleko zesitoreji ezaziwayo ngeyunithi ngayinye nesikhathi.
• Azikho izaphulelo zenani kanye nokugcwaliswa ngokushesha noma okuqhubekayo.

Izinzuzo Eziyinhloko: Kulula ukuyisebenzisa, isetshenziswa kabanzi, futhi iyasiza ekunciphiseni izindleko zoku-oda kanye nezokuqoqwa kwempahla ngaphansi kwemigomo yayo. Izinzuzo zifaka phakathi ukwehla kokuqoqwa kwempahla ngokweqile, ukwehla kwengozi yokuphelelwa yimpahla (uma kuhlanganiswa nendawo yoku-oda kabusha kanye nesitoko sokuphepha), kanye nokucaca okuthuthukisiwe kokuhlela ukuthenga. Izinhlangano eziningi ziyakwazisa ngoba inikeza isisekelo sezinombolo esiqondile sokunquma inani le-oda.

Okubi: Ayisebenzi kahle ngesidingo sesizini noma esingajwayelekile, ayinaki izaphulelo zevolumu, futhi icabanga ukuthi kuzophinde kugcwaliswe ngokushesha (noma okuhleliwe), okuyinto engenakwenzeka ezinhlotsheni eziningi zokuhlinzeka. Ngakho-ke, ezindaweni ezifana neqembu leToyota, ifomula ye-EOQ ithathelwe indawo yizinhlelo eziqinile njengeKanban noma i-Just-in-Time, ezisingatha kangcono ukuguquguquka kwangempela kanye nokugeleza okuqhubekayo.

Izibonelo ezisebenzayo ze-EOQ (Wilson)

Isibonelo 1 (esijwayelekile): Inkampani ekhiqiza amayunithi ayi-10.000 ngonyaka ithola ama-1.000 kg ezinto zokusetshenziswa. Uma i-oda ngalinye libiza ama-€200 futhi izindleko zokugcina zonyaka zingu-€2.000, kusetshenziswa ifomula ethi Q = √(2·D·K/G) ene-D=1.000, K=200, kanye ne-G=2.000 iveza u-Q ≈ 14,14. Lokhu kusikisela amaqoqo angu-14 kg kanye nama-oda angaba ngu-71 ngonyaka. Kuwumsebenzi obonisa lapho, ngezinombolo ezincane, singabona ukuthi usayizi weqoqo ulinganisa kanjani ama-oda kanye nesitoko.

Isibonelo 2: I-Sillas Grandes World SL isabalalisa izihlalo ezingu-6.000 (D), i-oda ngalinye libiza u-€300 (K), kanti izindleko zokugcina ngonyaka ngeyunithi ngayinye zingu-€5 (G). Ukusebenzisa i-equation, Q ≈ 848,52, okusho ukuthi inkampani izobeka ama-oda angaba ngu-7,07 ngonyaka. Ngalobu bukhulu be-lot, inkampani ithambekele ezingeni lempahla elisebenza kahle kakhulu , inciphisa izindleko zokugcina ngaphandle kokukhulisa kakhulu izindleko zokulungiselela ama-oda.

Ngale kwefomula ngokwayo, kuyalulekwa ukubala iphuzu lokuhlela kabusha ucabangele isikhathi sokulethwa nokugcina isitoko sokuphepha, ngoba imodeli emsulwa ayibaleli ukungaqiniseki. Futhi ayilinganisi umthelela wezaphulelo zevolumu, okungase ngezinye izikhathi kunciphise izindleko zesitokwe uma kusetshenziswa amaqoqo amakhulu.

Akufanele kudidaniswe nethiyori kaWilson (ithiyori yenombolo)

I-theorem kaWilson ingeyezibalo ze-modular futhi ngokuyisisekelo ithi inombolo ephelele u-n > 1 iyinhloko uma futhi kuphela uma (n − 1)! ≡ −1 (mod n). Incazelo ethi "uma u-n eyinhloko khona-ke (n − 1)! ≡ −1 (mod n)" ivame ukubizwa ngokuthi "i-theorem kaWilson," futhi impikiswano ephikisanayo nayo iyiqiniso. Ngokomlando, u-Edward Waring wathi umphumela uvela kuJohn Wilson (1770), yize ubufakazi bokuqala obaziwayo bunikezwe nguLagrange (1771), futhi empeleni le ndlela yokuqamba isukela ku-Alhazen ngekhulu le-11.

Isibonelo esiphathekayo: ku-p = 11, ngokuhlanganisa isici ngasinye ne-multiplicative inverse yaso kusethi {1, 2, …, p − 1}, umkhiqizo ophelele ungu-≡ −1 (mod p). Zonke izici ziyakhansela ngokuphindaphindiwe njengo-g·g^{-1} ≡ 1, ngaphandle kuka-1 no-p − 1, ngakho-ke u -10! ≡ −1 (mod 11) . Le ndlela isebenzisa iqiniso lokuthi, nge-p prime, (Z/pZ)^× iyiqembu eliphindaphindayo futhi isici ngasinye (ngaphandle kuka-1 no-p − 1) sinokuphambene okuhlukile.

Kunezibonakaliso eziningana. Indlela eyodwa ye-polynomial ibheka i-g(x) = (x − 1)(x − 2)···(x − (p − 1)) kanye ne-f(x) = g(x) − (x^{p−1} − 1). I-Modulo p, f(x) ibingaba nezimpande okungenani ze-p − 2 ukube bekungeyona i-polynomial engu-zero, kodwa yonke i-1, 2, …, p − 1 yenza i-f(x) engu-zero nge-Little Theorem ka-Fermat. Ngakho-ke, i-f(x) ifana ne-0 mod p; igama elihlala njalo liholela ku- (p − 1)! ≡ −1 (mod p).

Ayisetshenziswa njengesivivinyo esisebenzayo sokubaluleka ngoba ukubala i-(n − 1)! mod n ye-n enkulu kuyabiza, futhi kukhona izivivinyo ezisheshayo (ezifana ne-Miller-Rabin noma izivivinyo eziqondile zezikhundla ezithile). Noma kunjalo, ingasetshenziswa ukuthola izakhiwo eziwusizo: isibonelo, uma i-p = 2n + 1 iyi-prime, sithola i-∏_{j=1}^{n} j^2 ≡ (−1)^{n+1} (mod p). Futhi, njenge-corollary engaphelele, i-−1 iyi-quadratic residue modulo p uma i-p ≡ 1 (mod 4), njengoba ingabhalwa njengesikwele somkhiqizo i-1·2··2k uma i-p = 4k + 1, ekhombisa lapho i-−1 i-squared ku-Z/pZ.

Kukhona futhi "okuphambene" okusebenzayo: kwanoma iyiphi inombolo ehlanganisiwe n > 5, n ihlukanisa (n − 1)!. Icala n = 4 liyi-exception yakudala (3! akuyona i-multiple ka-4). Enye indlela yokubona lokhu ukubala amandla e-prime q ehlukanisa u-n: ku-(n − 1)! kune-multiples eyanele ka-q ukumboza amandla avela ku-n, ngaphandle kwe-exception ephawuliwe, eholela emphumeleni ngaphandle kuka-n = 4.

UGauss uhlanganise i-theorem: umkhiqizo wawo wonke amayunithi i-modulo n, ∏_{1≤a<n, (a,n)=1} a, ungu-≡ −1 (mod n) uma u-n ∈ {4, p^k, 2p^k} ene-p odd prime, kanye no-≡ 1 (mod n) kuzo zonke ezinye izimo. Ngokombono wamaqembu e-abelian aphelele, umkhiqizo wazo zonke izakhi zawo uwubunikazi ngaphandle kokuthi kukhona into eyodwa ye-oda 2, lapho umkhiqizo uyileyo nto ye-oda 2.

Ithebula elinemifanekiso lika (n − 1)! mod n ye-n = 2…30

Ithebula elilandelayo libonisa amanani athile ka-n phakathi kuka-2 no-30. Kumanani ayinhloko, okusele kuka-(n − 1)! uma kuhlukaniswa ngo-n kulingana no-n − 1 (okuyi-≡ −1 mod n). Kumanani ahlanganisiwe, okusele kuvame ukuba ngu-0. −1 mod n kufakiwe futhi ukuze kuqhathaniswe. Le datha ibonisa ngokucacile ukuthi i-theorem kaWilson iziphatha kanjani ezimweni ezincane futhi isiza ekuqiniseni intuition.

Izicelo, imikhawulo nezincomo

Uma ufuna ukukhiqiza ama-maze angachemile, sebenzisa i-algorithm kaWilson: isisekelo sayo ekuhambeni okungahleliwe ngokusula okujikelezayo kuqinisekisa izihlahla ezifanayo. Ngokuphathwa kwempahla, imodeli kaWilson iwusizo lapho isidingo, amanani, kanye nezindleko kuzinzile futhi kwaziwa kahle; ezindaweni eziguquguqukayo, izindlela ezifana neKanban, i-Just-in-Time, noma isofthiwe yokuhlela ethuthukisiwe zingase zifaneleke kakhulu. Futhi kwizibalo, i-theorem kaWilson iyigugu lethiyori elinemvelaphi ethakazelisayo (njengezinsalela ze-quadratic), kodwa ayisebenzi njengesivivinyo sokubaluleka kwezinombolo ezinkulu.

Ayikho ifomula eyodwa yokubala izindleko zoku-oda nezokugcina: inkampani ngayinye kumele ihlukanise amahora, izinqubo, ezokuthutha, ezokwamukela, abasebenzi, irenti, amandla, umshwalense, kanye nezindleko zezimali. Ochwepheshe abaningi balinganisela amahora ngokusebenza ngakunye futhi basebenzise isilinganiso sehora sokwenza imali. Lokhu kuhlela ngokwezifiso kuyisihluthulelo sokuqinisekisa ukuthi inani le-oda elibaliwe (Q) liwusizo futhi, kanye nendawo enhle yoku-oda kabusha kanye nesitoko sokuphepha, kusiza ukugwema ukuphela kwesitoko noma isitokwe esiningi.

Kuhle ukukhumbula ukuthi igama elithi "i-algorithm kaWilson" ekusesheni livame ukukhomba ku-generator ye-maze, kuyilapho elithi "imodeli kaWilson" noma elithi "EOQ" libhekisela ezinqolobaneni, kanye nethiyori yezinombolo ethi "i-Wilson's theorem". Ukuzihlukanisa kusukela ekuqaleni kugwema ukudideka futhi kukuvumela ukuthi usebenzise kangcono indlela ngayinye: ama-maze angachemile, ama-batches amahle ngaphansi kokuqagela okungokoqobo, kanye nokuchazwa okuhle kwama-prime , yize kungesibo ubufakazi obusebenzayo bokuthi abalulekile, okuhlala kuyingcezu ebalulekile yephazili yezibalo.

I-athikili ehlobene:

I-algorithm ye-Kruskal kanye nokusebenzisa kwayo kumagrafu