- Алгоритм Уилсона генерирует лабиринты как однородные случайные деревья, используя обходы с удалением циклов.
- Модель Уилсона (EOQ) рассчитывает оптимальный размер партии при стабильном спросе и ценах, но не учитывает скидки и сезонность.
- Теорема Уилсона характеризует простые числа с (n−1)! ≡ −1 (mod n) и имеет классические обобщения.
В интернете термин «Уилсон» используется для обозначения множества разных вещей, что довольно запутывает: существует алгоритм Уилсона для генерации лабиринтов, модель инвентаризации Уилсона (или EOQ) и теорема Уилсона в теории чисел. В этой статье мы все проясним, начиная с его первоначального использования в лабиринтах и тщательно различая другие значения, поскольку они не являются одним и тем же и не относятся к одной и той же области.
Если вы видели демонстрацию или апплет, где лабиринт «растет» сам по себе, вы, вероятно, уже сталкивались с алгоритмом Вильсона. Возможно, вы также слышали о модели Вильсона для расчета оптимального размера заказа или даже о теореме, характеризующей простые числа с помощью факториалов. Здесь вы найдете полное объяснение с примерами, чтобы вы могли определить каждое понятие и правильно его использовать.
Что такое алгоритм Уилсона для лабиринтов?
Алгоритм Уилсона — это метод генерации лабиринтов, основанный на случайных блужданиях без зацикливания. Его главное преимущество заключается в том, что он создает равномерное случайное остовное дерево по всей сетке: проще говоря, каждый возможный лабиринт появляется с одинаковой вероятностью , без смещения в сторону определенных направлений или шаблонов.
Ключевая идея заключается в том, что пути добавляются к существующей сети, но когда случайный путь пересекает сам себя, петля «стирается», и маршрут продолжается с того места, где он стал свободным. Эта деталь предотвращает предпочтение избыточных длинных путей или создание циклов, поддерживая структуру в виде дерева, соединяющего все ячейки. В результате получается «справедливый» лабиринт: ни один путь или поворот не имеет статистического преимущества перед другим.
Существуют созданные сообществом проекты и апплеты, которые наглядно и занимательно демонстрируют алгоритм в действии. Среди них выделяются некоторые апплеты Круза Годара, где можно выбрать размер сетки и запустить его, чтобы увидеть, как лабиринт появляется шаг за шагом. Наблюдение за процессом помогает понять, почему удаление циклов выравнивает вероятности на каждом расширении графа.
Создание и решение лабиринтов, хотя и кажутся играми, тесно связаны с задачами поиска и оптимизации. Разработка лабиринтов требует баланса между ясностью и интригой, избегая тривиальных решений или невозможных тупиков; исследования конечного пространства с огромным количеством комбинаций. Поэтому, как на бумаге, так и в цифровых симуляциях, они служат отличными упражнениями на логику, теорию вероятностей и терпение.
Как это работает (на практике)
Ниже приведено общее описание алгоритма без кода, но с основными механизмами для понимания его работы. Помните, что цель состоит в построении дерева (без циклов), соединяющего все ячейки, так чтобы между любыми двумя точками существовал только один простой путь.
- Все начинается с пустой сетки: ячейка выбирается случайным образом и отмечается как часть дерева.
- Случайным образом выбирается другая клетка, начинается пошаговый случайный обход, и если путь пересекает сам себя, петли немедленно удаляются (стирание петель).
- Когда маршрут достигает уже сгенерированного дерева, весь уточненный путь (без петель) «приклеивается» к дереву.
- Он повторяется: мы выбираем новую несвязанную ячейку, проходим с удалением цикла и присоединяемся к дереву.
- В конце концов, все клетки соединены, и лабиринт представляет собой равномерное случайное остовное дерево, поэтому нет никаких направленных или топологических смещений.
По сравнению с другими методами (такими как Олдос-Бродер, Прим или Крускала, адаптированными для лабиринтов), метод Уилсона выделяется равномерностью выборки остовного дерева. Его вычислительная стоимость приемлема на типичных сетках, и, что наиболее важно, он гарантирует равновероятность каждого решения , что высоко ценится в академических и имитационных контекстах.
Другие значения: Модель Уилсона или EOQ (запасы)
В логистике модель Уилсона (также называемая EOQ, экономически оптимальным размером заказа) не имеет ничего общего с лабиринтами. Это классический метод определения оптимального размера заказа для минимизации общих затрат на хранение запасов. Он был популяризирован в 1934 году Р. Х. Уилсоном, хотя первоначальная концепция была предложена Фордом Уитменом Харрисом в 1913 году.
Цель состоит в том, чтобы определить размер партии Q, который уравновешивает затраты на размещение заказов и затраты на хранение запасов. На основе годового спроса (D), стоимости одного заказа (K) и стоимости хранения единицы продукции за период (G) определяется количество, которое в рамках сделанных предположений снижает общие затраты на хранение запасов.
Наиболее распространенная формула выражается как Q = √(2·D·K/G). Эта величина показывает размер каждой партии; отсюда количество годовых заказов будет равно D/Q, и с помощью этого можно рассчитать цикл заказов. Также важно установить точку повторного заказа (с учетом времени выполнения) и страховой запас, чтобы избежать дефицита, хотя базовая формула явно не учитывает неопределенность.
Типичные области применения: Используется с сырьем или любыми видами товаров, для которых можно надежно определить затраты на закупку и хранение. На практике, зная D, K и G с достаточной степенью надежности, компания может определять размеры партий и планировать закупки с большей точностью.
Предположения, преимущества и ограничения модели Уилсона
Предположения имеют решающее значение для достоверности результата. Модель EOQ предполагает, что спрос постоянен и известен, что цена за единицу товара остается стабильной, что затраты на хранение известны и зависят от уровня запасов, что сроки поставки постоянны, и, кроме того, не учитывает скидки за объем.
- Стабильный, независимый спрос, без сезонности и резких пиков.
- Цена покупки фиксированная или практически не менялась в течение анализируемого периода.
- Известны затраты на хранение за единицу и период.
- Никаких скидок за количество и немедленное или постоянное пополнение запасов.
Основные преимущества: Простота внедрения, широкое распространение и помощь в минимизации затрат на заказы и складские запасы в соответствии с его условиями. Преимущества включают в себя снижение избыточных запасов, уменьшение риска дефицита (в сочетании с точкой повторного заказа и страховым запасом) и повышение ясности планирования закупок. Многие организации ценят его, поскольку он обеспечивает простую числовую основу для определения объемов заказов.
Недостатки: плохо работает с сезонным или нерегулярным спросом, игнорирует скидки за объем и предполагает немедленное (или фиксированное) пополнение запасов, что нереалистично во многих цепочках поставок. Поэтому в таких условиях, как в группе Toyota, формула EOQ была заменена более надежными системами, такими как Kanban или Just-in-Time, которые лучше справляются с фактической изменчивостью и непрерывным потоком.
Практические примеры EOQ (Уилсон)
Пример 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), а формулировка фактически восходит к Альхазену в XI веке.
Конкретный пример: для 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 по модулю 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. Эти данные наглядно демонстрируют поведение теоремы Вильсона в малых случаях и помогают укрепить интуитивное понимание.
| п> 1 | (n − 1)! | (n − 1)! mod n | −1 мод 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 |
Приложения, ограничения и рекомендации
Если вы хотите создавать непредвзятые лабиринты, используйте алгоритм Вильсона: его основа на случайных блужданиях с удалением циклов обеспечивает равномерное строение деревьев. Для управления запасами модель Вильсона полезна, когда спрос, цены и затраты стабильны и точно известны; в нестабильных условиях более подходящими могут быть такие методологии, как Канбан, «точно в срок» или программное обеспечение для расширенного планирования. А в математике теорема Вильсона — это теоретическая жемчужина с интересными выводами (например, квадратичные остатки), но она непрактична в качестве проверки простоты для больших чисел.
Единой формулы для расчета затрат на заказ и хранение не существует: каждая компания должна учитывать рабочее время, процессы, транспортировку, приемку, персонал, аренду, энергию, страхование и финансовые затраты. Многие специалисты оценивают количество часов на одну операцию и применяют почасовую ставку для монетизации. Такая индивидуальная настройка является ключом к обеспечению полезности рассчитанного количества заказа (Q) и, наряду с хорошей точкой повторного заказа и страховым запасом, помогает избежать дефицита или избытка товаров на складе.
Стоит помнить, что термин «алгоритм Вильсона» в поисковых запросах обычно указывает на генератор лабиринтов, в то время как «модель Вильсона» или «EOQ» относится к инвентаризации, а «теорема Вильсона» — к теории чисел. Разграничение этих подходов с самого начала позволяет избежать путаницы и лучше использовать каждый из них: несмещенные лабиринты, оптимальные пакеты при реалистичных предположениях и элегантная характеристика простых чисел, которая, хотя и не является практическим доказательством простоты, остается ценной частью математической головоломки.
