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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Недоліки: він погано працює із сезонним або нерегулярним попитом, ігнорує знижки за обсяг та передбачає негайне (або фіксоване) поповнення запасів, що є нереалістичним у багатьох ланцюгах поставок. Тому в таких середовищах, як Toyota Group, формула 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 − 1)! mod n для n = 2…30

У наступній таблиці ви можете побачити конкретні значення для n від 2 до 30. Для простого n остача від (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

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

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

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

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