- Wilson algoritması, döngü silme yürüyüşlerini kullanarak labirentleri tekdüze rastgele ağaçlar olarak üretir.
- Wilson Modeli (EOQ), istikrarlı talep ve fiyatlarla optimum lot büyüklüğünü hesaplar, ancak indirimleri veya mevsimselliği hesaba katmaz.
- Wilson teoremi (n−1)! ≡ −1 (mod n) olan asal sayıları karakterize eder ve klasik genellemelere sahiptir.
İnternette "Wilson" terimi birçok farklı şey için kullanılıyor ve bu oldukça kafa karıştırıcı: labirent oluşturmak için Wilson algoritması, Wilson Envanter Modeli (veya EOQ) ve sayı teorisinde Wilson teoremi gibi. Bu makalede, labirentlerdeki orijinal kullanımından başlayarak ve diğer anlamlarını dikkatlice ayırt ederek her şeyi açıklığa kavuşturacağız, çünkü bunlar aynı şey değil ve aynı alana uygulanmıyorlar.
Eğer bir labirentin kendi kendine "oluştuğu" bir demo veya uygulama gördüyseniz, muhtemelen Wilson algoritmasıyla zaten karşılaşmışsınızdır. Ayrıca ekonomik sipariş miktarını hesaplamak için kullanılan Wilson Modeli'ni veya asal sayıları faktöriyel kullanarak karakterize eden teoremi de duymuş olabilirsiniz. Burada, her kavramı tanımlayabilmeniz ve doğru şekilde kullanabilmeniz için örneklerle birlikte eksiksiz bir açıklama bulacaksınız.
Wilson'ın labirent algoritması nedir?
Wilson algoritması, döngü silinmiş rastgele yürüyüşlere dayalı bir labirent oluşturma yöntemidir. Başlıca avantajı, ızgara boyunca tekdüze rastgele bir yayılma ağacı üretmesidir: Basitçe söylemek gerekirse, her olası labirent aynı olasılıkla ortaya çıkar , belirli yönlere veya desenlere yönelik bir önyargı yoktur.
Temel fikir, mevcut ağa yollar eklenmesi, ancak rastgele bir yol kendiyle kesiştiğinde döngünün "silinmesi" ve rotanın serbest kaldığı noktadan devam etmesidir. Bu ayrıntı, gereksiz uzun yolları desteklemeyi veya döngüler oluşturmayı önleyerek, yapıyı tüm hücreleri birbirine bağlayan bir ağaç olarak korur. Sonuç "adil" bir labirenttir: hiçbir yol veya dönüşün diğerine göre istatistiksel bir avantajı yoktur.
Algoritmanın işleyişini görsel ve eğlenceli bir şekilde gösteren, topluluk tarafından oluşturulmuş projeler ve uygulamalar bulunmaktadır. Bunlar arasında, ızgara boyutunu seçebileceğiniz ve labirentin adım adım nasıl ortaya çıktığını görmek için çalıştırabileceğiniz Cruz Godar'ın bazı uygulamaları öne çıkmaktadır. Çalışmasını izlemek, döngü silme işleminin grafiğin her uzantısında olasılıkları neden eşitlediğini anlamanıza yardımcı olur.
Görünüşte oyun gibi olsa da, labirentler oluşturmak ve çözmek, arama ve optimizasyon problemleriyle yakından ilişkilidir. Bunları tasarlamak, açıklık ve merak arasında bir denge gerektirir; önemsiz çözümlerden veya imkansız çıkmazlardan kaçınmayı, sonlu bir alanı çok çeşitli kombinasyonlarla keşfetmeyi içerir. Bu nedenle, hem kağıt üzerinde hem de dijital simülasyonlarda, mantık, olasılık ve sabır konusunda mükemmel alıştırmalar olarak hizmet ederler.
Nasıl çalışır (pratik açıdan)
Aşağıda, algoritmanın davranışını anlamak için gerekli temel mekanizmaları içeren, kod içermeyen, üst düzey bir açıklaması bulunmaktadır. Amacın, tüm hücreleri birbirine bağlayan (döngü içermeyen) bir ağaç oluşturmak olduğunu, böylece herhangi iki nokta arasında yalnızca tek bir basit yolun bulunmasını sağlamak olduğunu unutmayın.
- Boş bir ızgarayla başlanır: Rastgele bir hücre seçilir ve ağacın bir parçası olarak işaretlenir.
- Rastgele başka bir hücre seçilerek adım adım rastgele yürüyüş başlatılır ve yol kendisini keserse döngüler hemen kaldırılır (döngü silme).
- Yürüyüş, daha önceden oluşturulmuş ağaca ulaştığında, rafine edilmiş yolun tamamı (döngüler olmadan) ağaca "yapıştırılır".
- Tekrarlanıyor: Bağlantısız yeni bir hücre seçiyoruz, döngü silme ile yürüyoruz ve ağaca katılıyoruz.
- Sonuç olarak, tüm hücreler birbirine bağlıdır ve labirent, tekdüze rastgele yayılan bir ağaçtır, bu nedenle yönsel veya topolojik önyargılar yoktur.
Diğer yöntemlerle (örneğin labirentlere uyarlanmış Aldous-Broder, Prim veya Kruskal yöntemleri) karşılaştırıldığında , Wilson yöntemi, yayılma ağacı örneklemesinin tekdüzeliğiyle öne çıkar. Tipik ızgaralarda hesaplama maliyeti makuldür ve her şeyden önemlisi, her çözümün eşit olasılığa sahip olmasını garanti eder ; bu da akademik ve simülasyon bağlamlarında son derece değerlidir.
Diğer anlamları: Wilson Modeli veya EOQ (envanterler)
Lojistikte, Wilson modeli (EOQ, Ekonomik Sipariş Miktarı olarak da adlandırılır) labirentlerle hiçbir ilgisi yoktur. Toplam stok maliyetlerini en aza indirmek için en uygun sipariş miktarını belirlemeye yönelik klasik bir yöntemdir. İlk kavramı 1913'te Ford Whitman Harris tarafından ortaya atılmış olsa da, 1934'te R.H. Wilson tarafından popülerleştirilmiştir.
Amacı, sipariş verme maliyeti ile stok tutma maliyetini dengeleyen parti büyüklüğü Q'yu bulmaktır. Yıllık talep (D), sipariş başına maliyet (K) ve dönem başına birim başına depolama maliyeti (G) esas alınarak, varsayımları çerçevesinde toplam stok maliyetini azaltan bir miktar elde edilir.
En yaygın formül Q = √(2·D·K/G) şeklinde ifade edilir. Bu rakam her partinin büyüklüğünü verir; buradan yıllık sipariş sayısı D/Q olur ve bununla sipariş döngüsünü türetebilirsiniz. Temel formül belirsizliği açıkça içermese de, stok tükenmesini önlemek için yeniden sipariş noktasını (teslim süresini dikkate alarak) ve güvenlik stoğunu belirlemek de önemlidir.
Tipik uygulamalar: Satın alma ve depolama maliyetlerinin güvenilir bir şekilde belirlenebildiği ham maddeler veya her türlü ticari mal için kullanılır. Uygulamada, D, K ve G değerlerini yeterli güvenilirlikle bilmek, şirketin parti büyüklüklerini belirlemesine ve tedarikini daha kontrollü bir şekilde planlamasına olanak tanır.
Wilson Modelinin varsayımları, avantajları ve sınırlamaları
Sonucun geçerliliği açısından varsayımlar kritik öneme sahiptir. EOQ modeli, talebin sabit ve bilindiğini, birim fiyatın istikrarlı kaldığını, depolama maliyetlerinin bilindiğini ve stok seviyesine bağlı olduğunu, tedarik sürelerinin sabit olduğunu varsayar ve ayrıca hacim indirimlerini dikkate almaz.
- Mevsimsellik veya ani yükselişler olmadan, istikrarlı, bağımsız talep.
- Analiz edilen dönem boyunca satın alma fiyatı sabit kaldı veya hemen hemen hiç değişmedi.
- Birim ve dönem başına bilinen depolama maliyetleri.
- Miktar indirimi yok ve anında veya sürekli yenileme.
Başlıca avantajları: Uygulaması basit, yaygın olarak kullanılıyor ve şartları gereği sipariş ve stok maliyetlerini en aza indirmeye yardımcı oluyor. Faydaları arasında aşırı stoklamanın azalması, stok tükenme riskinin azalması (yeniden sipariş noktası ve güvenlik stoğu ile birlikte kullanıldığında) ve satın alma planlaması için daha fazla netlik yer alıyor. Birçok kuruluş, sipariş miktarlarını belirlemek için basit bir sayısal temel sağladığı için bu yöntemi değerli buluyor.
Dezavantajları: Mevsimsel veya düzensiz taleplerde iyi sonuç vermez, hacim indirimlerini göz ardı eder ve birçok tedarik zincirinde gerçekçi olmayan anlık (veya sabit) ikmal varsayımına dayanır. Bu nedenle, Toyota grubu gibi ortamlarda, EOQ formülünün yerini, gerçek değişkenliği ve sürekli akışı daha iyi ele alan Kanban veya Tam Zamanında Üretim gibi daha sağlam sistemler almıştır.
EOQ'nun (Wilson) pratik örnekleri
Örnek 1 (tipik): Yıllık 10.000 adet üretim yapan bir şirket 1.000 kg hammadde satın alıyor. Her siparişin maliyeti 200 € ve toplam yıllık depolama maliyeti 2.000 € ise, D=1.000, K=200 ve G=2.000 ile Q = √(2·D·K/G) formülünü uyguladığımızda Q ≈ 14,14 elde ederiz. Bu, 14 kg'lık partiler ve yılda yaklaşık 71 sipariş anlamına gelir. Bu, mütevazı sayılarla parti büyüklüğünün siparişler ve stok arasındaki dengeyi nasıl sağladığını gösteren açıklayıcı bir alıştırmadır.
Örnek 2: Sillas Grandes World SL, 6.000 sandalye (D) dağıtıyor, her siparişin maliyeti 300 € (K) ve birim başına yıllık depolama maliyeti 5 € (G). Denklemi uygularsak, Q ≈ 848,52, yani şirket yılda yaklaşık 7,07 sipariş verecektir. Bu parti büyüklüğüyle firma, sipariş hazırlama maliyetlerini önemli ölçüde artırmadan depolama maliyetlerini azaltarak daha verimli bir envanter seviyesine doğru eğilim gösterir.
Formülün kendisinin ötesinde, tedarik süresini dikkate alarak yeniden sipariş noktasını hesaplamak ve güvenlik stoğu bulundurmak tavsiye edilir, çünkü saf model belirsizliği hesaba katmaz. Ayrıca, daha büyük partiler kullanıldığında envanter maliyetlerini bazen dengeleyebilecek hacim indirimlerinin etkisini de tahmin etmez.
Wilson teoremi (sayı teorisi) ile karıştırılmamalıdır
Wilson teoremi modüler aritmetiğe aittir ve özünde, n > 1 tamsayısının asal sayı olması için (n − 1)! ≡ −1 (mod n) olması gerektiğini belirtir. "Eğer n asal ise (n − 1)! ≡ −1 (mod n)" ifadesi genellikle "Wilson teoremi" olarak adlandırılır ve tersi de doğrudur. Tarihsel olarak, Edward Waring sonucu John Wilson'a (1770) atfetmiştir, ancak bilinen ilk ispat Lagrange (1771) tarafından yapılmıştır ve formülasyon aslında 11. yüzyılda Alhazen'e kadar uzanmaktadır.
Somut örnek: p = 11 için, her elemanı {1, 2, …, p − 1} kümesindeki çarpımsal tersiyle gruplandırarak, toplam çarpım ≡ −1 (mod p) olur. 1 ve p − 1 hariç tüm çarpanlar g·g^{-1} ≡ 1 olarak çiftler halinde birbirini götürür ve bu nedenle 10! ≡ −1 (mod 11) olur . Bu yaklaşım, p asal sayı olduğunda (Z/pZ)^×'nin çarpımsal bir grup olduğu ve her elemanın (1 ve p − 1 hariç) farklı bir tersinin olduğu gerçeğini kullanır.
Birkaç ispat yöntemi vardır. Bir polinom tekniği, g(x) = (x − 1)(x − 2)···(x − (p − 1)) ve f(x) = g(x) − (x^{p−1} − 1) ifadelerini ele alır. Modulo p'ye göre, f(x) sıfır polinomu olmasaydı en fazla p − 2 köke sahip olurdu, ancak Fermat'ın Küçük Teoremi gereği 1, 2, …, p − 1'in tümü f(x)'i sıfır yapar. Bu nedenle, f(x) mod p'ye göre özdeş olarak 0'dır; sabit terim (p − 1)! ≡ −1 (mod p) sonucuna götürür.
Bu, asal sayıların pratik bir testi olarak kullanılmaz çünkü büyük n değerleri için (n − 1)! mod n'yi hesaplamak maliyetlidir ve daha hızlı testler mevcuttur (örneğin Miller-Rabin veya belirli sıralar için deterministik testler). Yine de, yararlı özellikler elde etmek için kullanılabilir: örneğin, p = 2n + 1 asal ise, ∏_{j=1}^{n} j^2 ≡ (−1)^{n+1} (mod p) elde ederiz. Ve kısmi bir sonuç olarak, p ≡ 1 (mod 4) ise −1, p modülüne göre ikinci dereceden bir kalıntıdır, çünkü p = 4k + 1 olduğunda 1·2···2k çarpımının karesi olarak yazılabilir; bu da −1'in Z/pZ'de karesinin alındığını gösterir .
Ayrıca pratik bir "tersi" de vardır: 5'ten büyük herhangi bir bileşik sayı n için, n, (n − 1)!'i böler. n = 4 durumu klasik bir istisnadır (3!, 4'ün katı değildir). Bunu görmenin bir yolu, n'yi bölen bir asal sayı q'nun kuvvetlerini saymaktır: (n − 1)!'de, n'de görünen kuvveti kapsayacak kadar q'nun katı vardır, belirtilen istisna hariç, bu da n = 4 hariç sonuç verir.
Gauss teoremi genelleştirdi: n modülüne göre tüm birimlerin çarpımı, ∏_{1≤a<n, (a,n)=1} a, eğer n ∈ {4, p^k, 2p^k} ve p tek asal sayı ise ≡ −1 (mod n) ve diğer tüm durumlarda ≡ 1 (mod n) olur. Sonlu değişmeli gruplar açısından bakıldığında, tüm elemanlarının çarpımı, tam olarak 2. dereceden bir eleman olmadığı sürece özdeşliktir; eğer varsa, çarpım o 2. dereceden elemandır.
(n − 1)! mod n'nin n = 2…30 için açıklayıcı tablosu
Aşağıdaki tablo, 2 ile 30 arasındaki n değerleri için belirli değerleri göstermektedir. Asal sayılar için, (n − 1)! ifadesinin n'ye bölünmesinden kalan n − 1'e eşittir (yani ≡ −1 mod n). Bileşik sayılar için kalan genellikle 0'dır. Karşılaştırma için −1 mod n de eklenmiştir. Bu veriler, Wilson teoreminin küçük durumlarda nasıl davrandığını açıkça göstermekte ve sezgiyi pekiştirmeye yardımcı olmaktadır.
| 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 |
Uygulamalar, sınırlamalar ve öneriler
Tarafsız labirentler oluşturmak istiyorsanız, Wilson algoritmasını kullanın: döngü silme özelliğine sahip rastgele yürüyüşlere dayalı yapısı, tekdüze ağaçlar sağlar. Stok yönetimi için Wilson modeli, talep, fiyatlar ve maliyetler istikrarlı ve kesin olarak bilindiğinde kullanışlıdır; değişken ortamlarda, Kanban, Tam Zamanında Üretim veya gelişmiş planlama yazılımları gibi metodolojiler daha uygun olabilir. Matematikte ise Wilson teoremi, ilginç türetmeleri (örneğin ikinci dereceden kalıntılar) olan teorik bir mücevherdir, ancak büyük sayılar için asal sayı testi olarak pratik değildir.
Sipariş ve depolama maliyetlerini hesaplamak için tek bir formül yoktur: her şirket saatleri, süreçleri, nakliyeyi, teslim almayı, personeli, kirayı, enerjiyi, sigortayı ve finansal maliyetleri ayrıntılı olarak ele almalıdır. Birçok profesyonel, işlem başına saatleri tahmin eder ve parasallaştırma için saatlik bir ücret uygular. Bu özelleştirme, hesaplanan sipariş miktarının (Q) kullanışlı olmasını sağlamak için çok önemlidir ve iyi bir yeniden sipariş noktası ve güvenlik stoğu ile birlikte, stok tükenmesini veya fazla envanteri önlemeye yardımcı olur.
Arama motorlarında kullanılan "Wilson algoritması" teriminin genellikle labirent oluşturucuya, "Wilson modeli" veya "EOQ" terimlerinin envanterlere, "Wilson teoremi"nin ise sayı teorisine işaret ettiğini hatırlamakta fayda var. Bunları baştan ayırt etmek karışıklığı önler ve her yaklaşımdan daha iyi yararlanmanızı sağlar: tarafsız labirentler, gerçekçi varsayımlar altında optimal partiler ve pratik bir asal sayı ispatı olmasa da matematiksel bulmacanın değerli bir parçası olan asal sayıların zarif bir karakterizasyonu .
