Алгоритм Вілсона: повний посібник, відмінності від EOQ та теорема

Інформатек Діджитал » Машинобудування » Алгоритм Вілсона: повний посібник, відмінності від EOQ та теорема

В інтернеті термін «Вілсон» використовується для багатьох різних цілей, що досить заплутує: існує алгоритм Вілсона для генерації лабіринтів, модель інвентаризації Вілсона (або EOQ) та теорема Вілсона в теорії чисел. У цій статті ми все роз'яснюємо, починаючи з його початкового використання в лабіринтах та ретельно розрізняючи інші значення, оскільки вони не є одним і тим самим і не застосовуються до однієї й тієї ж галузі.

Якщо ви бачили демонстрацію або аплет, де лабіринт «росте» сам по собі, ви, ймовірно, вже стикалися з алгоритмом Вілсона. Ви також могли чути про модель Вілсона для обчислення економічної величини замовлення або навіть про теорему, яка характеризує прості числа за допомогою факторіалів. Тут ви знайдете повне пояснення з прикладами, щоб ви могли визначити кожне поняття та правильно його використовувати.

Що таке алгоритм Вільсона для лабіринтів?

Алгоритм Вілсона — це метод генерації лабіринтів, заснований на випадкових блуканнях зі стиранням циклів. Його головна перевага полягає в тому, що він створює рівномірне випадкове охоплююче дерево по всій сітці: простіше кажучи, кожен можливий лабіринт з'являється з однаковою ймовірністю , без упередженості до певних напрямків чи шаблонів.

Ключова ідея полягає в тому, що шляхи додаються до існуючої мережі, але коли випадковий шлях перетинається сам із собою, петля «стирається», і маршрут продовжується з точки, де він звільнився. Ця деталь запобігає тому, щоб процес надавав перевагу надлишковим довгим шляхам або створював цикли, зберігаючи структуру як дерево, яке з'єднує всі комірки. Результатом є «справедливий» лабіринт: жоден шлях чи поворот не має статистичної переваги над іншим.

Існують проекти та аплети, створені спільнотою, які візуально та цікаво демонструють алгоритм у дії. Серед них виділяються деякі аплети Круза Годара, де можна вибрати розмір сітки та запустити його, щоб крок за кроком побачити, як лабіринт з'являється. Спостереження за його виконанням допомагає зрозуміти, чому стирання циклів вирівнює ймовірності на кожному розширенні графіка.

Побудова та розв'язання лабіринтів, хоча й здаються іграми, тісно пов'язані з проблемами пошуку та оптимізації. Їх проектування вимагає балансу між ясністю та інтригою, уникнення тривіальних рішень або неможливих глухих кутів; дослідження скінченного простору з безліччю комбінацій. Тому, як на папері, так і в цифрових симуляціях, вони служать чудовими вправами на логіку, ймовірність та терпіння.

Як це працює (на практиці)

Нижче наведено загальний опис алгоритму без коду, але з основними механізмами для розуміння його поведінки. Пам'ятайте, що метою є побудова дерева (без циклів), яке з'єднує всі комірки так, щоб між будь-якими двома точками був лише один простий шлях.

• Починається з порожньої сітки: клітинка вибирається навмання та позначається як частина дерева.
• Випадковим чином вибирається інша клітинка, запускається покрокове випадкове блукання, і якщо шлях перетинає сам себе, петлі негайно видаляються (стертість петель).
• Коли маршрут досягає вже згенерованого дерева, весь уточнений шлях (без петель) «приклеюється» до дерева.
• Це повторюється: ми вибираємо нову незв'язану комірку, виконуємо цикл з видаленням циклу та приєднуємося до дерева.
• Зрештою, всі клітини з'єднані, і лабіринт являє собою однорідне випадкове остовне дерево, тому немає спрямованих або топологічних упереджень.

Порівняно з іншими методами (такими як Олдоса-Бродера, Прима або Крускала, адаптовані до лабіринтів), Вілсон вирізняється однорідністю вибірки охоплюючого дерева. Його обчислювальні витрати є прийнятними на типових сітках і, перш за все, він гарантує, що кожне рішення є рівноймовірним , що високо цінується в академічному контексті та контексті моделювання.

Інші значення: Модель Вілсона або EOQ (запаси)

У логістиці модель Вілсона (також відома як EOQ, Economic Order Quantity - економічна кількість замовлення) не має нічого спільного з лабіринтами. Це класичний метод визначення оптимальної кількості замовлення для мінімізації загальних витрат на запаси. Його популяризував у 1934 році Р. Г. Вілсон, хоча початкову концепцію запропонував Форд Вітмен Гарріс у 1913 році.

Його метою є знаходження розміру партії Q, який збалансує вартість розміщення замовлень та вартість зберігання запасів. На основі річного попиту (D), вартості замовлення (K) та вартості зберігання одиниці за період (G) визначається кількість, яка в рамках своїх припущень зменшує загальну вартість запасів.

Найпоширеніша формула виражається як Q = √(2·D·K/G). Це число дає розмір кожної партії; звідси кількість річних замовлень буде D/Q, і з цього можна вивести цикл замовлення. Також важливо встановити точку повторного замовлення (з урахуванням часу виконання) та страховий запас, щоб уникнути дефіциту, хоча базова формула явно не враховує невизначеність.

Типове застосування: використовується із сировиною або будь-яким типом товарів, для яких можна надійно визначити витрати на закупівлю та зберігання. На практиці, знаючи D, K та G з достатньою надійністю, компанія може визначати розміри своїх партій та планувати закупівлі з більшим контролем.

Припущення, переваги та обмеження моделі Вільсона

Ці припущення є критично важливими для достовірності результату. Модель EOQ припускає, що попит є постійним і відомим, що ціна за одиницю залишається стабільною, що витрати на зберігання відомі та залежать від рівня запасів, що терміни виконання замовлень є постійними, і, крім того, не враховує знижки за обсяг.

• Стабільний, незалежний попит, без сезонності чи раптових піків.
• Ціна закупівлі фіксована або практично незмінна протягом аналізованого періоду.
• Відомі витрати на зберігання на одиницю та період.
• Без знижок за кількість та негайне або постійне поповнення запасів.

Основні переваги: ​​його легко впровадити, він широко використовується та допомагає мінімізувати витрати на замовлення та зберігання запасів згідно з його умовами. Переваги включають зменшення перевитрат на запаси, зниження ризику дефіциту (у поєднанні з точкою повторного замовлення та страховим запасом) та покращену ясність планування закупівель. Багато організацій цінують його, оскільки він забезпечує просту числову основу для визначення обсягів замовлень.

Недоліки: він погано працює із сезонним або нерегулярним попитом, ігнорує знижки за обсяг та передбачає негайне (або фіксоване) поповнення запасів, що є нереалістичним у багатьох ланцюгах поставок. Тому в таких середовищах, як група Toyota, формула EOQ була замінена більш надійними системами, такими як Kanban або Just-in-Time, які краще справляються з фактичною мінливістю та безперервним потоком.

Практичні приклади EOQ (Wilson)

Приклад 1 (типовий): Компанія з річним виробництвом 10 000 одиниць закуповує 1 000 кг сировини. Якщо кожне замовлення коштує 200 євро, а загальна річна вартість зберігання становить 2 000 євро, застосування формули Q = √(2·D·K/G) з D=1 000, K=200 та G=2 000 дає Q ≈ 14,14. Це означає партії по 14 кг та приблизно 71 замовлення на рік. Це ілюстративна вправа, де з невеликими цифрами ми можемо побачити, як розмір партії балансує замовлення та запаси.

Приклад 2: Sillas Grandes World SL розповсюджує 6.000 стільців (D), кожне замовлення коштує 300 євро (K), а річна вартість зберігання на одиницю становить 5 євро (G). Застосовуючи рівняння, Q ≈ 848,52, що означає, що компанія розміщуватиме приблизно 7,07 замовлень щорічно. За такого розміру партії фірма прагне до більш ефективного рівня запасів , зменшуючи витрати на зберігання без суттєвого збільшення витрат на підготовку замовлень.

Окрім самої формули, доцільно розраховувати точку повторного замовлення з урахуванням часу виконання замовлення та підтримки страхового запасу, оскільки чиста модель не враховує невизначеність. Вона також не оцінює вплив знижок на обсяг, які іноді можуть компенсувати витрати на запаси, якщо використовуються більші партії.

Не плутати з теоремою Вільсона (теорія чисел)

Теорема Вільсона належить до модульної арифметики і по суті стверджує, що ціле число n > 1 є простим тоді і тільки тоді, коли (n − 1)! ≡ −1 (mod n). Імплікацію «якщо n є простим, то (n − 1)! ≡ −1 (mod n)» зазвичай називають строго «теоремою Вільсона», і зворотна імплікація також вірна. Історично Едвард Варінг приписував цей результат Джону Вільсону (1770), хоча перший відомий доказ був наданий Лагранжем (1771), а формулювання насправді датується часами Альхазена в 11 столітті.

Конкретний приклад: для p = 11, групуючи кожен елемент з його мультиплікативним оберненим у множині {1, 2, …, p − 1}, отримуємо загальний добуток ≡ −1 (mod p). Усі множники попарно скорочуються, оскільки g·g^{-1} ≡ 1, крім 1 та p − 1, а отже, 10! ≡ −1 (mod 11) . Цей підхід використовує той факт, що з p штивим, (Z/pZ)^× є мультиплікативною групою, і кожен елемент (крім 1 та p − 1) має окремий обернений елемент.

Існує кілька доказів. Один поліноміальний метод розглядає g(x) = (x − 1)(x − 2)···(x − (p − 1)) та f(x) = g(x) − (x^{p−1} − 1). За модулем p, f(x) мала б не більше p − 2 коренів, якби не була нульовим поліномом, але всі 1, 2, …, p − 1 роблять f(x) нульовою згідно з малою теоремою Ферма. Отже, f(x) тотожно 0 mod p; постійний член призводить до (p − 1)! ≡ −1 (mod p).

Його не використовують як практичний тест на простоту, оскільки обчислення (n − 1)! mod n для великих n є дорогим, і існують швидші тести (такі як тест Міллера-Рабіна або детерміновані тести для певних рангів). Навіть попри це, його можна використовувати для виведення корисних властивостей: наприклад, якщо p = 2n + 1 є простим числом, ми отримуємо ∏_{j=1}^{n} j^2 ≡ (−1)^{n+1} (mod p). І, як частковий наслідок, −1 є квадратичним залишком за модулем p, якщо p ≡ 1 (mod 4), оскільки його можна записати як квадрат добутку 1·2···2k, коли p = 4k + 1, що видно, коли −1 зведено до квадрата в Z/pZ.

Існує також практичне «обернене» явище: для будь-якого складеного числа n > 5, n ділить (n − 1)!. Випадок n = 4 є класичним винятком (3! не є кратним 4). Один зі способів побачити це — підрахувати степені простого числа q, яке ділить n: в (n − 1)! є достатньо кратних q, щоб покрити степінь, що з'являється в n, за винятком зазначеного винятку, який призводить до результату, за винятком випадку n = 4.

Гаусс узагальнив теорему: добуток усіх одиниць за модулем n, ∏_{1≤a<n, (a,n)=1} a, дорівнює ≡ −1 (mod n), якщо n ∈ {4, p^k, 2p^k} з p непарним простим числом, та ≡ 1 (mod n) у всіх інших випадках. З точки зору скінченних абелевих груп, добуток усіх їхніх елементів є одиницею, якщо не існує рівно один елемент порядку 2, і в цьому випадку добуток є цим елементом порядку 2.

Ілюстративна таблиця (n − 1)! mod n для n = 2…30

У наступній таблиці наведено конкретні значення для n від 2 до 30. Для простих чисел остача від (n − 1)! при діленні на n дорівнює n − 1 (що ≡ −1 mod n). Для складених чисел остача часто дорівнює 0. −1 mod n також включено для порівняння. Ці дані чітко ілюструють, як теорема Вільсона поводиться в малих випадках, і допомагають закріпити інтуїцію.

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

Застосування, обмеження та рекомендації

Якщо ви хочете генерувати неупереджені лабіринти, використовуйте алгоритм Вілсона: його основа на випадкових блуканнях зі стиранням циклів забезпечує однорідність дерев. Для управління запасами модель Вілсона корисна, коли попит, ціни та витрати стабільні та точно відомі; у нестабільних середовищах можуть бути більш придатними такі методології, як Канбан, Just-in-Time або програмне забезпечення для розширеного планування. А в математиці теорема Вілсона є теоретичною перлиною з цікавими висновками (такими як квадратичні залишки), але вона непрактична як тест на простоту для великих чисел.

Не існує єдиної формули для розрахунку витрат на замовлення та зберігання: кожна компанія повинна розбити витрати на години, процеси, транспортування, приймання, персонал, оренду, енергію, страхування та фінансові витрати. Багато фахівців оцінюють кількість годин на операцію та застосовують погодинну ставку для монетизації. Таке налаштування є ключовим для забезпечення корисності розрахованого обсягу замовлення (Q) і, разом із гарною точкою повторного замовлення та страховим запасом, допомагає уникнути дефіциту товару або надлишку запасів.

Варто пам'ятати, що термін «алгоритм Вілсона» в пошукових запитах зазвичай вказує на генератор лабіринтів, тоді як «модель Вілсона» або «EOQ» стосується інвентаризації, а «теорема Вілсона» — теорії чисел. Розрізнення їх з самого початку дозволяє уникнути плутанини та краще використовувати кожен підхід: неупереджені лабіринти, оптимальні партії за реалістичних припущень та елегантна характеристика простих чисел, яка, хоча й не є практичним доказом простоти, залишається цінним елементом математичної головоломки.