Algoritma Wilson: Panduan Lengkap, Perbedaan dengan EOQ dan Teorema

Informatec Digital » Teknik » Algoritma Wilson: Panduan Lengkap, Perbedaan dengan EOQ dan Teorema

Di internet, orang-orang menggunakan istilah "Wilson" untuk tujuan yang sangat berbeda, dan ini cukup membingungkan: ada algoritma Wilson untuk menghasilkan labirin, Model Wilson (atau EOQ) untuk inventaris, dan teorema Wilson dalam teori bilangan. Dalam artikel ini, kami akan menjelaskan semuanya, mulai dari penggunaan aslinya dalam labirin dan dengan cermat membedakan makna lainnya, karena Mereka tidak sama dan tidak berlaku pada area yang sama.

Jika Anda pernah melihat demo atau applet di mana labirin "tumbuh" dengan sendirinya, Anda mungkin sudah pernah menemukan algoritma Wilson. Anda juga pernah mendengar tentang Model Wilson untuk menghitung kuantitas pesanan ekonomi atau bahkan teorema yang mengkarakterisasi bilangan prima menggunakan faktorial. Di sini Anda akan menemukan penjelasan lengkap dengan contoh, sehingga Anda dapat Anda dapat mengidentifikasi setiap konsep dan menggunakannya dengan tepat.

Apa algoritma Wilson untuk labirin?

Algoritma Wilson adalah metode pembangkitan labirin berdasarkan lintasan acak yang dihapus loop. Keunggulan utamanya adalah menghasilkan pohon rentang acak yang seragam di seluruh grid: sederhananya, Setiap labirin yang mungkin muncul dengan probabilitas yang sama, tanpa bias terhadap arah atau pola tertentu.

Ide utamanya adalah jalur ditambahkan ke set yang sudah dibangun, tetapi ketika sebuah jalur acak berpotongan dengan dirinya sendiri, loop tersebut "dihapus" dan rute berlanjut dari titik terakhirnya. Detail ini mencegah proses menciptakan jalur atau loop yang panjang dan redundan, sehingga strukturnya tetap seperti pohon yang menghubungkan semua sel. Hasilnya adalah labirin yang "adil": tidak ada koridor atau belokan yang memiliki keunggulan statistik dibandingkan yang lain.

Ada beberapa proyek dan applet buatan komunitas yang menunjukkan algoritma ini beraksi secara visual dan sangat menghibur. Di antaranya, beberapa applet karya Cruz Godar menonjol, di mana Anda dapat memilih ukuran kisi dan mengaturnya agar berfungsi untuk melihat bagaimana labirin muncul langkah demi langkah. Menyaksikannya berjalan akan membantu Anda memahami alasannya. Penghapusan loop menyeimbangkan peluang di setiap perluasan grafik.

Membangun dan memecahkan labirin adalah tugas yang, meskipun tampak seperti permainan, berkaitan erat dengan masalah pencarian dan optimasi. Merancangnya membutuhkan keseimbangan antara kejelasan dan daya tarik, menghindari solusi yang remeh atau jalan buntu; menjelajahi ruang terbatas dengan kombinasi yang sangat besar. Oleh karena itu, baik di atas kertas maupun dalam simulasi digital, mereka bekerja sebagai Latihan hebat dalam logika, probabilitas, dan kesabaran.

Cara kerjanya (dalam istilah praktis)

Berikut adalah deskripsi tingkat tinggi dari algoritma ini, tanpa kode tetapi dengan mekanisme penting untuk memahami perilakunya. Ingat bahwa tujuannya adalah membangun pohon (tanpa siklus) yang menghubungkan semua sel, sehingga hanya ada satu jalur sederhana antara setiap pasangan titik.

• Dimulai dengan kotak kosong: sel dipilih secara acak dan ditandai sebagai bagian dari pohon.
• Sel lain dipilih secara acak, jalan acak langkah demi langkah dimulai, dan jika lintasan tersebut bersilangan dengan dirinya sendiri, putarannya segera dihapus (penghapusan putaran).
• Ketika jalur mencapai pohon yang sudah dibuat, seluruh jalur yang sudah disempurnakan (tanpa loop) akan “direkatkan” ke pohon.
• Ia berulang: kita memilih sel baru yang tidak terhubung, berjalan dengan penghapusan loop dan bergabung dengan pohon.
• Pada akhirnya, semua sel terhubung dan labirin adalah pohon rentang acak yang seragam, jadi tidak ada bias arah atau topologi.

Dibandingkan dengan metode lain (seperti Aldous–Broder, pertama atau Kruskal yang diadaptasi untuk labirin), Wilson menonjol karena keseragaman pengambilan sampel pohon pembangkit. Biaya komputasinya masuk akal pada grid umum dan, yang terpenting, memastikan bahwa setiap solusi memiliki kemungkinan yang sama, sesuatu yang sangat dihargai dalam konteks akademis dan simulasi.

Arti lainnya: Model Wilson atau EOQ (persediaan)

Dalam logistik, "Model Wilson" (juga disebut EOQ, Economic Order Quantity; atau CEP, Economic Order Quantity) tidak ada hubungannya dengan labirin. Model ini merupakan metode klasik untuk menentukan kuantitas pesanan optimal dengan tujuan meminimalkan total biaya inventaris. Model ini dipopulerkan pada tahun 1934 oleh R.H. Wilson, meskipun Usulan pertama diajukan oleh Ford Whitman Harris pada tahun 1913.

Tujuannya adalah untuk menemukan ukuran lot Q yang menyeimbangkan biaya pemesanan dan biaya penyimpanan stok. Dari permintaan tahunan (D), biaya per pesanan (K), dan biaya penyimpanan per unit dan periode (G), diperoleh kuantitas yang, dalam kerangka asumsinya, mengurangi total biaya persediaan.

Rumus yang paling umum adalah Q = √(2 D K/G). Rumus ini menghasilkan ukuran batch; dari sana, jumlah pesanan tahunan akan menjadi D/Q, dan dari sini Anda dapat memperoleh irama waktu. Penting juga untuk menetapkan titik pemesanan ulang (dengan mempertimbangkan waktu tunggu) dan stok pengaman untuk menghindari kehabisan stok, meskipun rumus dasar tidak mengandung ketidakpastian secara eksplisit.

Aplikasi umum: digunakan untuk bahan baku atau jenis barang dagangan apa pun yang biaya pembelian dan penyimpanannya dapat ditentukan dengan andal. Dalam praktiknya, jika D, K, dan G diketahui dengan cukup andal, Perusahaan dapat menentukan ukuran batch dan menjadwalkan pasokannya dengan kontrol yang lebih besar.

Asumsi, kelebihan dan keterbatasan Model Wilson

Asumsi sangat penting untuk validitas hasil. Model EOQ mengasumsikan bahwa permintaan konstan dan diketahui, bahwa harga satuan tetap stabil, bahwa biaya penyimpanan diketahui dan bergantung pada tingkat persediaan, bahwa waktu pasokan konstan, dan, lebih lanjut, tidak mempertimbangkan diskon volume.

• Permintaan stabil dan independen, tanpa musim atau puncak yang tiba-tiba.
• Harga pembelian tetap atau hampir tidak berubah selama periode yang dianalisis.
• Biaya penyimpanan yang diketahui per unit dan periode.
• Tidak ada diskon kuantitas dan pengisian ulang langsung atau konstan.

Keunggulan utama: Mudah diimplementasikan, digunakan secara luas, dan membantu meminimalkan biaya pemesanan dan inventaris sesuai kondisi Anda. Manfaatnya meliputi berkurangnya stok berlebih, berkurangnya risiko kehabisan stok (jika disertai titik pemesanan ulang dan stok pengaman), serta kejelasan dalam perencanaan pembelian. Banyak organisasi menghargai sistem ini karena menawarkan dasar numerik sederhana untuk memutuskan berapa banyak yang harus dipesan.

Kekurangan: Sistem ini tidak efektif untuk permintaan musiman atau tidak teratur, mengabaikan diskon volume, dan mengasumsikan pengisian ulang segera (atau tetap), yang tidak realistis dalam banyak rantai pasokan. Oleh karena itu, dalam lingkungan seperti Toyota Group, rumus EOQ telah digantikan oleh sistem yang lebih tangguh seperti Kanban atau Just in Time, yang Mereka menangani variabilitas nyata dengan lebih baik dan aliran berkelanjutan.

Contoh praktis EOQ (Wilson)

Contoh 1 (umum): Sebuah perusahaan dengan produksi tahunan 10.000 unit membeli 1.000 kg bahan baku. Jika setiap pesanan berharga €200 dan total biaya penyimpanan tahunan adalah €2.000, dengan menerapkan rumus Q = √(2 D K/G) dengan D = 1.000, K = 200, G = 2.000, diperoleh Q ≈ 14,14. Ini menunjukkan batch dengan berat 14 kg dan sekitar 71 pesanan per tahun. Ini adalah latihan ilustrasi di mana, dengan angka-angka sederhana, kita dapat melihat Bagaimana ukuran lot menyeimbangkan pesanan dan stok.

Contoh 2: Sillas Grandes World SL mendistribusikan 6.000 kursi (D), setiap pesanan berharga €300 (K) dan biaya penyimpanan per unit per tahun adalah €5 (G). Dengan menggunakan persamaan Q ≈ 848,52, maka akan dihasilkan sekitar 7,07 pesanan per tahun. Dengan ukuran lot ini, perusahaan cenderung menuju tingkat persediaan yang lebih efisien, mengurangi biaya penyimpanan tanpa meningkatkan biaya persiapan pesanan.

Selain rumus tersebut, sebaiknya hitung titik pemesanan ulang dengan mempertimbangkan waktu tunggu dan menjaga stok pengaman, karena model murni tidak memperhitungkan ketidakpastian. Model ini juga tidak memperkirakan dampak diskon volume, yang terkadang bisa mengimbangi biaya saham jika lot yang lebih besar digunakan.

Jangan sampai tertukar dengan teorema Wilson (teori bilangan)

Teorema Wilson termasuk dalam aritmatika modular dan pada dasarnya menyatakan bahwa bilangan bulat n > 1 adalah bilangan prima jika dan hanya jika (n − 1)! ≡ −1 (mod n). Implikasi "jika n prima maka (n − 1)! ≡ −1 (mod n)" sering disebut "Teorema Wilson", dan implikasi kebalikannya juga benar. Secara historis, Edward Waring mengaitkan hasil tersebut dengan John Wilson (1770), meskipun pembuktian pertama yang diketahui diberikan oleh Lagrange (1771), dan faktanya, Formulasi ini berasal dari Alhacen pada abad ke-11.

Contoh konkret: untuk p = 11, ketika mengelompokkan setiap elemen dengan invers perkaliannya dalam himpunan {1, 2, …, p − 1}, hasil perkalian totalnya menjadi ≡ −1 (mod p). Semua faktor saling meniadakan secara merata, yaitu g g^{-1} ≡ 1, kecuali 1 dan p − 1, sehingga 10! ≡ −1 (mod 11)Pendekatan ini menggunakan fakta bahwa, dengan p prima, (Z/pZ)^× adalah grup perkalian dan setiap elemen (kecuali 1 dan p − 1) mempunyai invers yang berbeda.

Ada beberapa pembuktian. Salah satu teknik polinomial mempertimbangkan g(x) = (x − 1)(x − 2)···(x − (p − 1)) dan f(x) = g(x) − (x^{p−1} − 1). Modulus p, f(x) akan memiliki paling banyak akar p − 2 jika bukan polinomial nol, tetapi semua 1, 2, …, p − 1 menghilangkan f(x) berdasarkan teorema kecil Fermat. Oleh karena itu, f(x) identik dengan 0 mod p dan suku independennya mengarah ke (p − 1)! ≡ −1 (mod p).

Ini tidak digunakan sebagai uji prima praktis, karena menghitung (n − 1)! mod n untuk n besar mahal dan ada uji yang lebih cepat (seperti uji Miller–Rabin atau uji deterministik untuk rentang tertentu). Meskipun demikian, berguna untuk menyimpulkan sifat-sifat yang berguna: misalnya, jika p = 2n + 1 prima, maka kita memiliki ∏_{j=1}^{n} j^2 ≡ (−1)^{n+1} (mod p). Dan, sebagai akibat wajar parsial, −1 adalah residu kuadrat modulo p jika p ≡ 1 (mod 4), karena dapat ditulis sebagai kuadrat dari produk 1 2 2k ketika p = 4k + 1, yang menunjukkan saat −1 kuadrat dalam Z/pZ.

Terdapat pula "invers" praktis: untuk setiap bilangan komposit n > 5, benar bahwa n membagi (n − 1)!. Kasus n = 4 merupakan pengecualian klasik (3! bukan kelipatan 4). Salah satu cara untuk melihat hal ini adalah dengan menghitung pangkat bilangan prima q yang membagi n: dalam (n − 1)! terdapat kelipatan q yang cukup untuk menutupi pangkat yang muncul dalam n, kecuali untuk pengecualian yang ditunjukkan, yaitu mengarah ke hasil kecuali untuk n = 4.

Gauss menggeneralisasi teorema: produk semua unit modulo n, ∏_{1≤a Itu adalah elemen orde 2.

Tabel ilustrasi (n − 1)! mod n untuk n = 2…30

Pada tabel berikut, Anda dapat melihat nilai spesifik untuk n antara 2 dan 30. Untuk n yang prima, sisa (n − 1)! ketika dibagi dengan n sama dengan n − 1 (yaitu ≡ −1 mod n). Dalam komposit, sisa seringkali 0. −1 mod n juga disertakan untuk perbandingan. Data ini menggambarkan dengan sangat baik bagaimana teorema Wilson berlaku dalam kasus-kasus kecil dan membantu untuk memperbaiki intuisi.

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

Aplikasi, batasan dan rekomendasi

Jika Anda ingin menghasilkan labirin yang tidak bias, gunakan algoritma Wilson: basisnya pada jalur acak dengan penghapusan loop memastikan pohon yang seragam. Untuk inventaris, Model Wilson berguna ketika permintaan, harga, dan biaya stabil dan diketahui secara tepat; dalam lingkungan yang volatil, metodologi seperti Kanban, JIT, atau perangkat lunak perencanaan tingkat lanjut mungkin lebih tepat. Dan dalam matematika, teorema Wilson adalah permata teoretis dengan derivasi yang menarik (seperti residu kuadrat), tetapi Ini tidak praktis sebagai uji keutamaan untuk angka yang besar.

Tidak ada formula "satu ukuran untuk semua" untuk menghitung biaya pemesanan dan penyimpanan: setiap perusahaan harus merinci jam kerja, proses, transportasi, penerimaan, personel, sewa, energi, asuransi, dan biaya keuangan. Banyak profesional memperkirakan jam kerja per operasi dan menerapkan tarif per jam untuk mendapatkan keuntungan. Penyesuaian ini penting agar Q yang dihitung bermanfaat dan, bersama dengan titik pemesanan ulang dan stok pengaman yang baik, menghindari kehabisan stok atau kelebihan inventaris.

Perlu diingat bahwa istilah "algoritma Wilson" dalam penelusuran biasanya merujuk pada generator labirin, sementara "model Wilson" atau "EOQ" merujuk pada inventaris, dan "teorema Wilson" merujuk pada teori bilangan. Membedakan keduanya sejak awal akan menghindari kebingungan dan memungkinkan Anda memanfaatkan setiap pendekatan dengan lebih baik: Labirin yang tidak bias, kumpulan optimal dengan asumsi realistis, dan karakterisasi bilangan prima yang elegan yang, meskipun bukan uji primalitas praktis, tetap merupakan bagian berharga dari teka-teki matematika.