Wilsons Algorithmus: Vollständige Anleitung, Unterschiede zu EOQ und dem Theorem

Informatec Digital » Maschinenbau » Wilsons Algorithmus: Vollständige Anleitung, Unterschiede zu EOQ und dem Theorem

Im Internet wird der Begriff „Wilson“ für ganz unterschiedliche Zwecke verwendet, was ziemlich verwirrend ist: Es gibt den Wilson-Algorithmus zur Generierung von Labyrinthen, das Wilson-Modell (oder EOQ) für Inventare und den Wilson-Satz in der Zahlentheorie. In diesem Artikel klären wir alles, beginnend mit der ursprünglichen Verwendung in Labyrinthen und sorgfältiger Unterscheidung der anderen Bedeutungen, denn Sie sind nicht gleich und gelten auch nicht für denselben Bereich.

Wenn Sie schon einmal eine Demo oder ein Applet gesehen haben, in dem ein Labyrinth von selbst „wächst“, sind Sie wahrscheinlich schon auf Wilsons Algorithmus gestoßen. Sie haben auch vom Wilson-Modell zur Berechnung der wirtschaftlichen Bestellmenge gehört oder sogar vom Theorem, das Primzahlen mithilfe von Fakultäten charakterisiert. Hier finden Sie eine vollständige Erklärung mit Beispielen, damit Sie Sie können jedes Konzept identifizieren und richtig verwenden.

Was ist Wilsons Algorithmus für Labyrinthe?

Wilsons Algorithmus ist eine Methode zur Labyrinthgenerierung, die auf schleifengelöschten Zufallswegen basiert. Sein großer Vorteil besteht darin, dass er einen gleichmäßigen zufälligen Spannbaum über dem Gitter erzeugt: Einfach ausgedrückt: Jedes mögliche Labyrinth erscheint mit der gleichen Wahrscheinlichkeit, ohne Voreingenommenheit gegenüber bestimmten Richtungen oder Mustern.

Die Grundidee besteht darin, dass Pfade zu den bereits erstellten Pfaden hinzugefügt werden. Wenn sich ein Zufallspfad jedoch selbst kreuzt, wird die Schleife „gelöscht“ und die Route wird dort fortgesetzt, wo sie aufgehört hat. Dieses Detail verhindert, dass lange, redundante Pfade oder Schleifen entstehen, und erhält die Struktur als Baum, der alle Zellen verbindet. Das Ergebnis ist ein „faires“ Labyrinth: kein Korridor oder keine Kurve hat einen statistischen Vorteil gegenüber einem anderen.

Es gibt von der Community erstellte Projekte und Applets, die den Algorithmus auf visuelle und höchst unterhaltsame Weise in Aktion zeigen. Besonders hervorzuheben sind einige Applets von Cruz Godar, bei denen man die Rastergröße wählen und die Arbeit starten kann, um zu sehen, wie das Labyrinth Schritt für Schritt entsteht. Wenn man es laufen sieht, versteht man, warum. Schleifenlöschung gleicht die Chancen aus in jeder Erweiterung des Graphen.

Das Erstellen und Lösen von Labyrinthen sind Aufgaben, die zwar wie Spiele erscheinen, aber eng mit Such- und Optimierungsproblemen verknüpft sind. Bei ihrer Gestaltung ist ein Gleichgewicht zwischen Klarheit und Interesse erforderlich, wobei triviale Lösungen oder Sackgassen vermieden werden müssen. einen begrenzten Raum erkunden mit enormen Kombinationen. Daher funktionieren sie sowohl auf dem Papier als auch in digitalen Simulationen als Tolle Übungen in Logik, Wahrscheinlichkeit und Geduld.

So funktioniert es (in der Praxis)

Nachfolgend finden Sie eine allgemeine Beschreibung des Algorithmus, ohne Code, aber mit den wesentlichen Mechanismen zum Verständnis seines Verhaltens. Denken Sie daran, dass das Ziel darin besteht, einen Baum (ohne Zyklen) zu erstellen, der alle Zellen verbindet, sodass Es gibt nur einen einfachen Pfad zwischen jedem Punktpaar.

• Es beginnt mit einem leeren Raster: Eine Zelle wird zufällig ausgewählt und als Teil des Baums markiert.
• Eine andere Zelle wird zufällig ausgewählt, ein schrittweiser Zufallspfad wird gestartet, und wenn sich der Pfad selbst kreuzt, werden die Schleifen sofort entfernt (Schleifenlöschung).
• Wenn der Spaziergang den bereits generierten Baum erreicht, wird der gesamte verfeinerte Pfad (ohne Schleifen) an den Baum „geklebt“.
• Es wiederholt sich: Wir wählen eine neue, nicht verbundene Zelle aus, gehen mit Schleifenlöschung und verbinden den Baum.
• Am Ende sind alle Zellen miteinander verbunden und das Labyrinth ist ein gleichmäßiger, zufälliger Spannbaum, also Es gibt keine Richtungs- oder topologischen Verzerrungen.

Im Vergleich zu anderen Methoden (wie Aldous-Broder, zuerst oder Kruskal, angepasst an Labyrinthe), Wilson zeichnet sich durch die Gleichmäßigkeit der Stichprobenziehung des generierenden Baums aus. Der Rechenaufwand ist auf typischen Gittern angemessen und vor allem stellt sicher, dass jede Lösung gleich wahrscheinlich ist, etwas, das in akademischen und Simulationskontexten sehr geschätzt wird.

Andere Bedeutungen: Wilson-Modell oder EOQ (Inventare)

In der Logistik hat das „Wilson-Modell“ (auch EOQ, Economic Order Quantity; oder CEP, Economic Order Quantity) nichts mit Labyrinthen zu tun. Es ist eine klassische Methode zur Bestimmung der optimalen Bestellmenge mit dem Ziel, die Gesamtkosten des Lagerbestands zu minimieren. Es wurde 1934 von R.H. Wilson populär gemacht, obwohl Der erste Vorschlag kam von Ford Whitman Harris im Jahr 1913.

Ziel ist es, die Losgröße Q zu ermitteln, die die Kosten der Bestellung und die Kosten der Lagerhaltung im Gleichgewicht hält. Aus dem Jahresbedarf (D), den Kosten pro Bestellung (K) und den Lagerkosten pro Einheit und Zeitraum (G) ergibt sich eine Menge, die im Rahmen der Annahmen reduziert die Gesamtkosten des Lagerbestands.

Die gebräuchlichste Formel ist Q = √(2 D K/G). Daraus ergibt sich die Losgröße; daraus ergibt sich die Anzahl der jährlichen Bestellungen D/Q, woraus sich die Zeitabfolge ableiten lässt. Es ist auch wichtig, den Nachbestellpunkt (unter Berücksichtigung der Vorlaufzeit) und den Sicherheitsbestand festzulegen, um Fehlbestände zu vermeiden, obwohl die Grundformel berücksichtigt keine Unsicherheit ausdrücklich.

Typische Anwendungen: Wird bei Rohstoffen oder Waren aller Art verwendet, deren Einkaufs- und Lagerkosten zuverlässig ermittelt werden können. In der Praxis gilt: Wenn D, K und G ausreichend zuverlässig bekannt sind, Das Unternehmen kann seine Chargen dimensionieren und ihre Lieferung planen mit größerer Kontrolle.

Annahmen, Vorteile und Einschränkungen des Wilson-Modells

Annahmen sind entscheidend für die Gültigkeit der Ergebnisse. Das EOQ-Modell geht davon aus, dass die Nachfrage konstant und bekannt ist, dass der Stückpreis stabil bleibt, dass die Lagerkosten bekannt sind und vom Lagerbestand abhängen, dass die Lieferzeiten konstant sind und außerdem sieht keine Mengenrabatte vor.

• Stabile, unabhängige Nachfrage ohne Saisonalität oder plötzliche Spitzen.
• Kaufpreis während des Analysezeitraums fest oder praktisch unverändert.
• Bekannte Lagerkosten pro Einheit und Zeitraum.
• Keine Mengenrabatte und sofortiger bzw. ständiger Nachschub.

Hauptvorteile: Es ist einfach zu implementieren, weit verbreitet und trägt dazu bei, Bestell- und Lagerkosten unter Ihren Bedingungen zu minimieren. Zu den Vorteilen gehören die Reduzierung von Überbeständen, das geringere Risiko von Fehlbeständen (bei gleichzeitiger Festlegung von Nachbestellpunkten und Sicherheitsbeständen) und die Transparenz in der Einkaufsplanung. Viele Unternehmen schätzen es, weil bietet eine einfache numerische Grundlage für die Entscheidung, wie viel bestellt werden soll.

Nachteile: Es funktioniert nicht gut bei saisonaler oder unregelmäßiger Nachfrage, ignoriert Mengenrabatte und geht von einer sofortigen (oder festen) Nachschubmenge aus, was in vielen Lieferketten unrealistisch ist. Daher wurde die EOQ-Formel in Umgebungen wie der Toyota Group durch robustere Systeme wie Kanban oder Just in Time verdrängt, die Sie bewältigen reale Variabilität besser und der kontinuierliche Fluss.

Praktische Beispiele der EOQ (Wilson)

Beispiel 1 (typisch): Ein Unternehmen mit einer Jahresproduktion von 10.000 Einheiten kauft 1.000 kg Rohmaterial. Bei einem Auftragswert von 200 € und den gesamten jährlichen Lagerkosten von 2.000 € ergibt sich mit der Formel Q = √(2 D K/G) mit D = 1.000, K = 200, G = 2.000 Q ≈ 14,14. Dies lässt auf Chargen von 14 kg und etwa 71 Aufträge pro Jahr schließen. Dies ist eine anschauliche Übung, die anhand bescheidener Zahlen zeigt, Wie die Losgröße Bestellungen und Lagerbestände ausgleicht.

Beispiel 2: Sillas Grandes World SL vertreibt 6.000 Stühle (D), jede Bestellung kostet 300 € (K) und die Lagerkosten pro Stück und Jahr betragen 5 € (G). Mit der Gleichung Q ≈ 848,52 ergäben sich daraus etwa 7,07 Bestellungen pro Jahr. Mit dieser Losgröße tendiert zu einem effizienteren Lagerbestand, wodurch die Lagerkosten gesenkt werden, ohne die Kosten für die Auftragsvorbereitung zu erhöhen.

Über die Formel hinaus ist es sinnvoll, den Nachbestellpunkt unter Berücksichtigung der Vorlaufzeit und der Aufrechterhaltung des Sicherheitsbestands zu berechnen, da das reine Modell Unsicherheiten nicht berücksichtigt. Es schätzt auch nicht die Auswirkungen von Mengenrabatten, die manchmal könnte die Lagerkosten ausgleichen wenn größere Lose verwendet werden.

Nicht zu verwechseln mit dem Wilson-Theorem (Zahlentheorie)

Wilsons Theorem gehört zu den modulare Arithmetik und besagt im Wesentlichen, dass eine ganze Zahl n > 1 genau dann eine Primzahl ist, wenn (n − 1)! ≡ −1 (mod n) ist. Die Implikation „Wenn n eine Primzahl ist, dann ist (n − 1)! ≡ −1 (mod n)“ wird oft streng als „Wilsons Theorem“ bezeichnet, und die umgekehrte Implikation ist ebenfalls wahr. Historisch schrieb Edward Waring das Ergebnis John Wilson (1770) zu, obwohl der erste bekannte Beweis von Lagrange (1771) erbracht wurde. Tatsächlich Die Formulierung stammt aus Alhacen im 11. Jahrhundert.

Konkretes Beispiel: Für p = 11 wird das Gesamtprodukt ≡ −1 (mod p) berechnet, wenn jedes Element mit seinem multiplikativen Inversen in der Menge {1, 2, …, p − 1} gruppiert wird. Alle Faktoren heben sich gleichmäßig auf, da g g^{-1} ≡ 1, außer 1 und p − 1. Somit 10! ≡ −1 (mod 11)Dieser Ansatz nutzt die Tatsache, dass (Z/pZ)^× mit p eine Primzahl ist und dass jedes Element (außer 1 und p − 1) eine eindeutige Inverse hat.

Es gibt mehrere Beweise. Eine polynomische Methode betrachtet g(x) = (x − 1)(x − 2)···(x − (p − 1)) und f(x) = g(x) − (x^{p−1} − 1). Modulo p, f(x) hätte höchstens p − 2 Nullstellen, wenn es nicht das Nullpolynom wäre, aber alle 1, 2, …, p − 1 verschwinden nach dem kleinen Fermatschen Theorem von f(x). Daher ist f(x) identisch 0 mod p und der unabhängige Term führt zu (p − 1)! ≡ −1 (mod p).

Es wird nicht als praktischer Primzahltest verwendet, da die Berechnung von (n − 1)! mod n für große n aufwendig ist und schnellere Tests existieren (wie Miller-Rabin oder deterministische Tests für bestimmte Bereiche). Trotzdem ist es nützlich, nützliche Eigenschaften abzuleiten: Wenn beispielsweise p = 2n + 1 eine Primzahl ist, dann gilt ∏_{j=1}^{n} j^2 ≡ (−1)^{n+1} (mod p). Und als partielles Korollar ist −1 ein quadratischer Residuum modulo p, wenn p ≡ 1 (mod 4), da es als Quadrat des Produkts 1 2 2k geschrieben werden kann, wenn p = 4k + 1, was zeigt, wenn −1 quadratisch ist in Z/pZ.

Es gibt auch eine praktische „Inverse“: Für jedes zusammengesetzte n > 5 gilt, dass n ein Teiler von (n − 1)! ist. Der Fall n = 4 ist die klassische Ausnahme (3! ist kein Vielfaches von 4). Eine Möglichkeit, dies zu sehen, besteht darin, die Potenzen einer Primzahl q zu zählen, die n teilen: In (n − 1)! gibt es genügend Vielfache von q, um die in n vorkommende Potenz abzudecken, mit Ausnahme der angegebenen Ausnahme, die führt zu dem Ergebnis außer für n = 4.

Gauss verallgemeinerte den Satz: das Produkt aller Einheiten modulo n, ∏_{1≤a Es ist das Element der Ordnung 2.

Illustrative Tabelle von (n − 1)! mod n für n = 2…30

In der folgenden Tabelle sehen Sie spezifische Werte für n zwischen 2 und 30. Für n, das eine Primzahl ist, ist der Rest von (n − 1)! geteilt durch n gleich n − 1 (was ≡ −1 mod n ist). In zusammengesetzten Zahlen ist der Rest oft 0. −1 mod n ist zum Vergleich ebenfalls angegeben. Diese Daten veranschaulichen sehr gut, wie sich Wilsons Theorem in kleinen Fällen verhält und helfen, Intuition reparieren.

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

Anwendungen, Grenzen und Empfehlungen

Wenn Sie unvoreingenommene Labyrinthe erzeugen möchten, verwenden Sie Wilsons Algorithmus: Seine Basis in Zufallswegen mit Schleifenlöschung gewährleistet einheitliche Bäume. Für Lagerbestände ist das Wilson-Modell nützlich, wenn Nachfrage, Preise und Kosten stabil und genau bekannt sind; in volatilen Umgebungen können Methoden wie Kanban, JIT oder fortschrittliche Planungssoftware geeigneter sein. Und in der Mathematik ist Wilsons Theorem ein theoretisches Juwel mit interessanten Ableitungen (wie quadratischen Residuen), aber Es ist nicht praktikabel als Primzahltest für große Zahlen.

Es gibt keine allgemeingültige Formel zur Berechnung von Bestell- und Lagerkosten: Jedes Unternehmen muss Stunden, Prozesse, Transport, Wareneingang, Personal, Miete, Energie, Versicherung und Finanzkosten aufschlüsseln. Viele Fachleute schätzen die Stunden pro Vorgang und wenden einen Stundensatz an, um diese Kosten zu monetarisieren. Diese individuelle Anpassung ist der Schlüssel zur Nutzbarkeit des berechneten Q und, zusammen mit einem guten Nachbestellpunkt und Sicherheitsbestand, vermeiden Sie Fehlbestände oder überschüssige Lagerbestände.

Es ist wichtig zu wissen, dass sich der Begriff „Wilsons Algorithmus“ bei Suchanfragen in der Regel auf den Labyrinthgenerator bezieht, während sich „Wilsons Modell“ oder „EOQ“ auf Inventare und „Wilsons Theorem“ auf die Zahlentheorie bezieht. Eine Unterscheidung von vornherein vermeidet Verwirrung und ermöglicht es Ihnen, jeden Ansatz besser zu nutzen: Unvoreingenommene Labyrinthe, optimale Batches unter realistischen Annahmen und eine elegante Charakterisierung von Primzahlen Dies ist zwar kein praktischer Primzahltest, aber dennoch ein wertvolles Stück des mathematischen Puzzles.