Thuật toán Wilson: Hướng dẫn đầy đủ, Sự khác biệt với EOQ và Định lý

Informatec Digital » Kỹ thuật » Thuật toán Wilson: Hướng dẫn đầy đủ, Sự khác biệt với EOQ và Định lý

Trên internet, thuật ngữ "Wilson" được sử dụng cho nhiều thứ khác nhau, điều này khá gây nhầm lẫn: có thuật toán Wilson để tạo mê cung, Mô hình tồn kho Wilson (hay EOQ), và định lý Wilson trong lý thuyết số. Trong bài viết này, chúng tôi sẽ làm rõ mọi thứ, bắt đầu từ cách sử dụng ban đầu của nó trong mê cung và phân biệt cẩn thận các ý nghĩa khác, bởi vì chúng không giống nhau và không áp dụng cho cùng một lĩnh vực.

Nếu bạn đã từng xem bản demo hoặc applet nào đó mà mê cung "tự phát triển", có lẽ bạn đã bắt gặp thuật toán Wilson. Bạn cũng có thể đã nghe nói về Mô hình Wilson để tính toán số lượng đặt hàng kinh tế tối thiểu hoặc thậm chí là định lý xác định số nguyên tố bằng giai thừa. Ở đây, bạn sẽ tìm thấy một lời giải thích đầy đủ kèm theo ví dụ, để bạn có thể nhận biết từng khái niệm và sử dụng chúng một cách chính xác.

Thuật toán Wilson cho mê cung là gì?

Thuật toán Wilson là một phương pháp tạo mê cung dựa trên các bước đi ngẫu nhiên xóa vòng lặp. Ưu điểm chính của nó là tạo ra một cây bao trùm ngẫu nhiên đồng đều trên toàn lưới: nói một cách đơn giản, mọi mê cung có thể xuất hiện với cùng xác suất , không thiên vị theo hướng hoặc mẫu cụ thể nào.

Ý tưởng chính là các đường đi được thêm vào mạng lưới hiện có, nhưng khi một đường đi ngẫu nhiên tự giao nhau, vòng lặp sẽ bị "xóa bỏ", và tuyến đường tiếp tục từ điểm mà nó trở nên tự do. Chi tiết này ngăn chặn quá trình tạo ra các đường đi dài dư thừa hoặc tạo ra các vòng lặp, duy trì cấu trúc dạng cây kết nối tất cả các ô. Kết quả là một mê cung "công bằng": không có đường đi hay ngã rẽ nào có lợi thế thống kê hơn đường đi hoặc ngã rẽ khác.

Có những dự án và ứng dụng nhỏ do cộng đồng tạo ra, minh họa trực quan và thú vị cách thuật toán hoạt động. Trong số đó, một số ứng dụng nhỏ của Cruz Godar nổi bật, cho phép bạn chọn kích thước lưới và chạy để xem mê cung hình thành từng bước. Quan sát quá trình hoạt động giúp bạn hiểu tại sao việc xóa vòng lặp lại làm giảm xác suất ở mỗi lần mở rộng đồ thị.

Việc xây dựng và giải mê cung, dù thoạt nhìn có vẻ giống trò chơi, lại liên quan mật thiết đến các bài toán tìm kiếm và tối ưu hóa. Thiết kế chúng đòi hỏi sự cân bằng giữa sự rõ ràng và tính hấp dẫn, tránh những giải pháp tầm thường hoặc những ngõ cụt không thể vượt qua; khám phá một không gian hữu hạn với vô số tổ hợp. Do đó, cả trên giấy và trong các mô phỏng kỹ thuật số, chúng đều là những bài tập tuyệt vời về logic, xác suất và tính kiên nhẫn.

Cách thức hoạt động (thực tế)

Dưới đây là mô tả tổng quan về thuật toán, không kèm mã lệnh nhưng nêu rõ cơ chế hoạt động thiết yếu. Hãy nhớ rằng mục tiêu là xây dựng một cây (không có chu trình) kết nối tất cả các ô, sao cho chỉ có một đường đi đơn giản giữa bất kỳ hai điểm nào.

• Nó bắt đầu với một lưới trống: một ô được chọn ngẫu nhiên và được đánh dấu là một phần của cây.
• Một ô khác được chọn ngẫu nhiên, một cuộc đi bộ ngẫu nhiên từng bước được bắt đầu và nếu đường đi tự cắt nhau, các vòng lặp sẽ ngay lập tức bị loại bỏ (xóa vòng lặp).
• Khi đường đi đến cây đã được tạo, toàn bộ đường đi đã được tinh chỉnh (không có vòng lặp) sẽ được "dán" vào cây.
• Lặp lại: chúng ta chọn một ô mới không liên kết, thực hiện xóa vòng lặp và tham gia vào cây.
• Cuối cùng, tất cả các ô đều được kết nối và mê cung là một cây mở rộng ngẫu nhiên đồng nhất, do đó không có sự thiên vị về hướng hoặc về mặt tôpô.

So với các phương pháp khác (như Aldous-Broder, Prim , hoặc Kruskal được điều chỉnh cho mê cung), phương pháp Wilson nổi bật nhờ tính đồng nhất trong việc lấy mẫu cây bao trùm. Chi phí tính toán của nó hợp lý trên các lưới điển hình và trên hết, nó đảm bảo rằng mỗi lời giải đều có xác suất như nhau , điều này được đánh giá cao trong bối cảnh học thuật và mô phỏng.

Ý nghĩa khác: Mô hình Wilson hoặc EOQ (hàng tồn kho)

Trong lĩnh vực hậu cần, mô hình Wilson (còn được gọi là EOQ, Economic Order Quantity - Số lượng đặt hàng kinh tế) không liên quan gì đến mê cung. Đây là một phương pháp kinh điển để xác định số lượng đặt hàng tối ưu nhằm giảm thiểu tổng chi phí tồn kho. Mô hình này được R.H. Wilson phổ biến vào năm 1934, mặc dù ý tưởng ban đầu được Ford Whitman Harris đề xuất vào năm 1913.

Mục đích của phương pháp này là tìm ra quy mô lô hàng Q sao cho cân bằng chi phí đặt hàng và chi phí lưu trữ hàng tồn kho. Dựa trên nhu cầu hàng năm (D), chi phí mỗi đơn hàng (K) và chi phí lưu trữ mỗi đơn vị mỗi kỳ (G), ta thu được một lượng hàng tồn kho mà, trong khuôn khổ các giả định của nó, làm giảm tổng chi phí tồn kho.

Công thức phổ biến nhất được biểu thị là Q = √(2·D·K/G). Con số này cho biết quy mô của mỗi lô hàng; từ đó, số lượng đơn đặt hàng hàng năm sẽ là D/Q, và với điều này bạn có thể tính ra chu kỳ đặt hàng. Điều quan trọng nữa là phải thiết lập điểm đặt hàng lại (có tính đến thời gian giao hàng) và lượng hàng tồn kho an toàn để tránh tình trạng hết hàng, mặc dù công thức cơ bản không thể hiện rõ ràng sự không chắc chắn.

Ứng dụng điển hình: Phương pháp này được sử dụng với nguyên liệu thô hoặc bất kỳ loại hàng hóa nào mà chi phí mua và lưu trữ có thể được xác định một cách đáng tin cậy. Trên thực tế, bằng cách biết D, K và G với độ tin cậy đủ cao, công ty có thể xác định quy mô lô hàng và lên kế hoạch thu mua với khả năng kiểm soát tốt hơn.

Giả định, ưu điểm và hạn chế của Mô hình Wilson

Các giả định là rất quan trọng đối với tính hợp lệ của kết quả. Mô hình EOQ giả định rằng nhu cầu là không đổi và đã biết, giá đơn vị không đổi, chi phí lưu trữ đã biết và phụ thuộc vào mức tồn kho, thời gian giao hàng là không đổi, và hơn nữa, không xem xét đến chiết khấu theo số lượng.

• Nhu cầu ổn định, độc lập, không theo mùa hoặc tăng đột ngột.
• Giá mua cố định hoặc thực tế không thay đổi trong suốt thời gian phân tích.
• Chi phí lưu trữ đã biết theo từng đơn vị và thời kỳ.
• Không giảm giá theo số lượng và bổ sung hàng ngay lập tức hoặc liên tục.

Ưu điểm chính: Phương pháp này dễ triển khai, được sử dụng rộng rãi và giúp giảm thiểu chi phí đặt hàng và tồn kho theo các điều khoản của nó. Lợi ích bao gồm giảm tình trạng tồn kho quá mức, giảm rủi ro hết hàng (khi kết hợp với điểm đặt hàng lại và lượng hàng tồn kho an toàn), và cải thiện tính minh bạch cho việc lập kế hoạch mua hàng. Nhiều tổ chức đánh giá cao phương pháp này vì nó cung cấp cơ sở số liệu đơn giản để xác định số lượng đặt hàng.

Nhược điểm: Phương pháp này không hiệu quả với nhu cầu theo mùa hoặc không đều, bỏ qua chiết khấu theo số lượng và giả định việc bổ sung hàng hóa ngay lập tức (hoặc cố định), điều này không thực tế trong nhiều chuỗi cung ứng. Do đó, trong các môi trường như tập đoàn Toyota, công thức EOQ đã được thay thế bằng các hệ thống mạnh mẽ hơn như Kanban hoặc Just-in-Time, giúp xử lý tốt hơn sự biến động thực tế và dòng chảy liên tục.

Ví dụ thực tế về EOQ (Wilson)

Ví dụ 1 (điển hình): Một công ty có sản lượng hàng năm là 10.000 đơn vị mua 1.000 kg nguyên liệu thô. Nếu mỗi đơn đặt hàng có giá 200 € và tổng chi phí lưu trữ hàng năm là 2.000 €, áp dụng công thức Q = √(2·D·K/G) với D=1.000, K=200 và G=2.000 ta được Q ≈ 14,14. Điều này cho thấy các lô hàng có khối lượng 14 kg và khoảng 71 đơn đặt hàng mỗi năm. Đây là một bài tập minh họa, với số liệu khiêm tốn, chúng ta có thể thấy cách kích thước lô hàng cân bằng giữa đơn đặt hàng và hàng tồn kho.

Ví dụ 2: Công ty Sillas Grandes World SL phân phối 6.000 chiếc ghế (D), mỗi đơn hàng có giá 300 € (K), và chi phí lưu trữ hàng năm cho mỗi đơn vị là 5 € (G). Áp dụng phương trình, Q ≈ 848,52, có nghĩa là công ty sẽ đặt khoảng 7,07 đơn hàng mỗi năm. Với quy mô lô hàng này, công ty hướng tới mức tồn kho hiệu quả hơn , giảm chi phí lưu trữ mà không làm tăng đáng kể chi phí chuẩn bị đơn hàng.

Ngoài công thức tính toán, nên tính toán điểm đặt hàng lại dựa trên thời gian giao hàng và duy trì lượng hàng tồn kho an toàn, vì mô hình thuần túy không tính đến sự không chắc chắn. Nó cũng không ước tính tác động của chiết khấu theo số lượng, điều này đôi khi có thể bù đắp chi phí tồn kho nếu sử dụng các lô hàng lớn hơn.

Không nên nhầm lẫn với định lý Wilson (lý thuyết số)

Định lý Wilson thuộc về số học modulo và về cơ bản phát biểu rằng một số nguyên n > 1 là số nguyên tố khi và chỉ khi (n − 1)! ≡ −1 (mod n). Mệnh đề "nếu n là số nguyên tố thì (n − 1)! ≡ −1 (mod n)" thường được gọi chính xác là "định lý Wilson", và mệnh đề đảo cũng đúng. Về mặt lịch sử, Edward Waring cho rằng kết quả này thuộc về John Wilson (1770), mặc dù bằng chứng đầu tiên được biết đến là của Lagrange (1771), và cách diễn đạt thực tế có từ thời Alhazen vào thế kỷ 11.

Ví dụ cụ thể: với p = 11, bằng cách nhóm mỗi phần tử với nghịch đảo phép nhân của nó trong tập hợp {1, 2, …, p − 1}, tổng tích là ≡ −1 (mod p). Tất cả các thừa số triệt tiêu từng cặp vì g·g^{-1} ≡ 1, ngoại trừ 1 và p − 1, và do đó 10! ≡ −1 (mod 11) . Phương pháp này sử dụng thực tế là, với p là số nguyên tố, (Z/pZ)^× là một nhóm phép nhân và mỗi phần tử (ngoại trừ 1 và p − 1) đều có một nghịch đảo khác nhau.

Có một số cách chứng minh. Một kỹ thuật đa thức xem xét g(x) = (x − 1)(x − 2)···(x − (p − 1)) và f(x) = g(x) − (x^{p−1} − 1). Modulo p, f(x) sẽ có tối đa p − 2 nghiệm nếu nó không phải là đa thức không, nhưng tất cả 1, 2, …, p − 1 đều làm cho f(x) bằng 0 theo Định lý nhỏ Fermat. Do đó, f(x) đồng nhất bằng 0 modulo p; hằng số dẫn đến (p − 1)! ≡ −1 (mod p).

Nó không được sử dụng như một phép thử thực tế về tính nguyên tố vì việc tính toán (n − 1)! mod n đối với n lớn rất tốn kém, và tồn tại các phép thử nhanh hơn (chẳng hạn như phép thử Miller–Rabin hoặc các phép thử xác định cho các hạng cụ thể). Tuy nhiên, nó có thể được sử dụng để suy ra các tính chất hữu ích: ví dụ, nếu p = 2n + 1 là số nguyên tố, ta thu được ∏_{j=1}^{n} j^2 ≡ (−1)^{n+1} (mod p). Và, như một hệ quả một phần, −1 là phần dư bậc hai modulo p nếu p ≡ 1 (mod 4), vì nó có thể được viết dưới dạng bình phương của tích 1·2···2k khi p = 4k + 1, điều này cho thấy khi nào −1 được bình phương trong Z/pZ.

Ngoài ra còn có một "ngược" thực tế: với bất kỳ số hợp số n > 5 nào, n đều chia hết cho (n − 1)!. Trường hợp n = 4 là ngoại lệ kinh điển (3! không phải là bội số của 4). Một cách để thấy điều này là đếm lũy thừa của một số nguyên tố q chia hết cho n: trong (n − 1)! có đủ bội số của q để bao phủ lũy thừa xuất hiện trong n, ngoại trừ trường hợp ngoại lệ đã nêu, dẫn đến kết quả ngoại trừ trường hợp n = 4.

Gauss đã khái quát hóa định lý: tích của tất cả các phần tử đơn vị modulo n, ∏_{1≤a<n, (a,n)=1} a, bằng ≡ −1 (mod n) nếu n ∈ {4, p^k, 2p^k} với p là số nguyên tố lẻ, và bằng 1 (mod n) trong tất cả các trường hợp khác. Từ quan điểm của các nhóm Abel hữu hạn, tích của tất cả các phần tử của chúng là phần tử đơn vị trừ khi tồn tại chính xác một phần tử có bậc 2, trong trường hợp đó tích là phần tử có bậc 2 đó.

Bảng minh họa của (n − 1)! mod n với n = 2…30

Bảng sau đây hiển thị các giá trị cụ thể cho n từ 2 đến 30. Đối với số nguyên tố, phần dư của (n − 1)! khi chia cho n bằng n − 1 (tức là ≡ −1 mod n). Đối với số hợp số, phần dư thường bằng 0. −1 mod n cũng được đưa vào để so sánh. Dữ liệu này minh họa rõ ràng cách định lý Wilson hoạt động trong các trường hợp nhỏ và giúp củng cố trực giác.

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

Ứng dụng, giới hạn và khuyến nghị

Nếu bạn muốn tạo ra các mê cung không thiên vị, hãy sử dụng thuật toán Wilson: nền tảng của nó dựa trên các bước đi ngẫu nhiên với việc xóa vòng lặp đảm bảo các cây đồng nhất. Đối với quản lý hàng tồn kho, mô hình Wilson hữu ích khi nhu cầu, giá cả và chi phí ổn định và được biết chính xác; trong môi trường biến động, các phương pháp như Kanban, Just-in-Time hoặc phần mềm lập kế hoạch tiên tiến có thể phù hợp hơn. Và trong toán học, định lý Wilson là một viên ngọc quý về mặt lý thuyết với những dẫn xuất thú vị (chẳng hạn như phần dư bậc hai), nhưng nó không thực tế khi dùng làm phép thử tính nguyên tố cho các số lớn.

Không có công thức duy nhất nào để tính toán chi phí đặt hàng và lưu trữ: mỗi công ty phải phân tích chi tiết số giờ làm việc, quy trình, vận chuyển, tiếp nhận hàng hóa, nhân sự, tiền thuê nhà, năng lượng, bảo hiểm và chi phí tài chính. Nhiều chuyên gia ước tính số giờ làm việc cho mỗi hoạt động và áp dụng mức giá theo giờ để tính toán lợi nhuận. Việc tùy chỉnh này rất quan trọng để đảm bảo số lượng đặt hàng (Q) được tính toán là hữu ích và, cùng với điểm đặt hàng lại hợp lý và lượng hàng tồn kho an toàn, giúp tránh tình trạng hết hàng hoặc tồn kho dư thừa.

Cần nhớ rằng thuật ngữ "thuật toán Wilson" trong tìm kiếm thường đề cập đến trình tạo mê cung, trong khi "mô hình Wilson" hoặc "EOQ" đề cập đến hàng tồn kho, và "định lý Wilson" đề cập đến lý thuyết số. Phân biệt chúng ngay từ đầu sẽ tránh nhầm lẫn và cho phép bạn sử dụng tốt hơn từng phương pháp: mê cung không thiên vị, lô hàng tối ưu dựa trên các giả định thực tế, và một đặc điểm thanh lịch của số nguyên tố mà, mặc dù không phải là bằng chứng thực tiễn về tính nguyên tố, vẫn là một mảnh ghép quý giá của bài toán toán học.