Αλγόριθμος Wilson: Πλήρης οδηγός, διαφορές με το EOQ και το θεώρημα

Informatec Digital » Μηχανική » Αλγόριθμος Wilson: Πλήρης οδηγός, διαφορές με το EOQ και το θεώρημα

Στο διαδίκτυο, ο όρος «Wilson» χρησιμοποιείται για πολλά διαφορετικά πράγματα, κάτι που προκαλεί αρκετή σύγχυση: υπάρχει ο αλγόριθμος του Wilson για τη δημιουργία λαβυρίνθων, το Μοντέλο Απογραφής Wilson (ή EOQ) και το θεώρημα του Wilson στη θεωρία αριθμών. Σε αυτό το άρθρο, διευκρινίζουμε τα πάντα, ξεκινώντας από την αρχική του χρήση στους λαβύρινθους και διακρίνοντας προσεκτικά τις άλλες έννοιες, επειδή δεν είναι το ίδιο πράγμα και δεν εφαρμόζονται στον ίδιο τομέα.

Αν έχετε δει κάποια επίδειξη ή μικροεφαρμογή όπου ένας λαβύρινθος «μεγαλώνει» μόνος του, πιθανότατα έχετε ήδη συναντήσει τον αλγόριθμο του Wilson. Μπορεί επίσης να έχετε ακούσει για το Μοντέλο Wilson για τον υπολογισμό της οικονομικής ποσότητας παραγγελίας ή ακόμα και για το θεώρημα που χαρακτηρίζει τους πρώτους αριθμούς χρησιμοποιώντας παραγοντικά. Εδώ θα βρείτε μια πλήρη εξήγηση με παραδείγματα, ώστε να μπορείτε να αναγνωρίσετε κάθε έννοια και να τη χρησιμοποιήσετε σωστά.

Ποιος είναι ο αλγόριθμος του Wilson για τους λαβύρινθους;

Ο αλγόριθμος του Wilson είναι μια μέθοδος δημιουργίας λαβυρίνθου που βασίζεται σε τυχαίους περιπάτους με διαγραφή βρόχου. Το κύριο πλεονέκτημά του είναι ότι παράγει ένα ομοιόμορφο τυχαίο δέντρο που εκτείνεται σε όλο το πλέγμα: με απλά λόγια, κάθε πιθανός λαβύρινθος εμφανίζεται με την ίδια πιθανότητα , χωρίς προκατάληψη προς συγκεκριμένες κατευθύνσεις ή μοτίβα.

Η βασική ιδέα είναι ότι προστίθενται διαδρομές στο υπάρχον δίκτυο, αλλά όταν μια τυχαία διαδρομή τέμνει τον εαυτό της, ο βρόχος «διαγράφεται» και η διαδρομή συνεχίζεται από το σημείο όπου ελευθερώθηκε. Αυτή η λεπτομέρεια εμποδίζει τη διαδικασία να ευνοήσει περιττές μεγάλες διαδρομές ή να δημιουργήσει κύκλους, διατηρώντας τη δομή ως δέντρο που συνδέει όλα τα κελιά. Το αποτέλεσμα είναι ένας «δίκαιος» λαβύρινθος: καμία διαδρομή ή στροφή δεν έχει στατιστικό πλεονέκτημα έναντι μιας άλλης.

Υπάρχουν έργα και μικροεφαρμογές που δημιουργούνται από την κοινότητα και παρουσιάζουν οπτικά και ψυχαγωγικά τον αλγόριθμο σε δράση. Ανάμεσά τους, ξεχωρίζουν μερικά από τα μικροεφαρμογές του Cruz Godar, όπου μπορείτε να επιλέξετε το μέγεθος του πλέγματος και να το εκτελέσετε για να δείτε πώς αναδύεται ο λαβύρινθος βήμα προς βήμα. Παρακολουθώντας την εκτέλεση του, σας βοηθά να κατανοήσετε γιατί η διαγραφή βρόχου ισοπεδώνει τις πιθανότητες σε κάθε επέκταση του γραφήματος.

Η κατασκευή και η επίλυση λαβυρίνθων, ενώ μοιάζουν με παιχνίδια, συνδέονται στενά με προβλήματα αναζήτησης και βελτιστοποίησης. Ο σχεδιασμός τους απαιτεί ισορροπία μεταξύ σαφήνειας και ενδιαφέροντος, αποφεύγοντας ασήμαντες λύσεις ή αδύνατα αδιέξοδα, εξερευνώντας έναν πεπερασμένο χώρο με τεράστιους συνδυασμούς. Επομένως, τόσο σε χαρτί όσο και σε ψηφιακές προσομοιώσεις, χρησιμεύουν ως εξαιρετικές ασκήσεις λογικής, πιθανοτήτων και υπομονής.

Πώς λειτουργεί (στην πράξη)

Παρακάτω ακολουθεί μια περιγραφή υψηλού επιπέδου του αλγορίθμου, χωρίς κώδικα αλλά με τους απαραίτητους μηχανισμούς για την κατανόηση της συμπεριφοράς του. Να θυμάστε ότι ο στόχος είναι να κατασκευαστεί ένα δέντρο (χωρίς κύκλους) που να συνδέει όλα τα κελιά, έτσι ώστε να υπάρχει μόνο μία απλή διαδρομή μεταξύ οποιωνδήποτε δύο σημείων.

• Ξεκινά με ένα άδειο πλέγμα: ένα κελί επιλέγεται τυχαία και σημειώνεται ως μέρος του δέντρου.
• Ένα άλλο κελί επιλέγεται τυχαία, ξεκινά μια βήμα προς βήμα τυχαία περιήγηση και, εάν η διαδρομή διασταυρωθεί, οι βρόχοι αφαιρούνται αμέσως (διαγραφή βρόχου).
• Όταν η διαδρομή φτάσει στο ήδη δημιουργημένο δέντρο, ολόκληρη η βελτιωμένη διαδρομή (χωρίς βρόχους) «κολλάει» στο δέντρο.
• Επαναλαμβάνεται: επιλέγουμε ένα νέο μη συνδεδεμένο κελί, περπατάμε με διαγραφή βρόχου και εντασσόμαστε στο δέντρο.
• Στο τέλος, όλα τα κελιά είναι συνδεδεμένα και ο λαβύρινθος είναι ένα ομοιόμορφο τυχαίο δέντρο που εκτείνεται, έτσι δεν υπάρχουν κατευθυντικές ή τοπολογικές προκαταλήψεις.

Σε σύγκριση με άλλες μεθόδους (όπως οι Aldous-Broder, Prim ή Kruskal προσαρμοσμένες σε λαβύρινθους), η Wilson ξεχωρίζει για την ομοιομορφία της δειγματοληψίας spanning tree. Το υπολογιστικό της κόστος είναι λογικό σε τυπικά πλέγματα και, πάνω απ 'όλα, εγγυάται ότι κάθε λύση είναι ισοπιθανή , κάτι που έχει μεγάλη αξία σε ακαδημαϊκά και προσομοιωτικά πλαίσια.

Άλλες σημασίες: Μοντέλο Wilson ή EOQ (αποθέματα)

Στην εφοδιαστική, το μοντέλο Wilson (που ονομάζεται επίσης EOQ, Οικονομική Ποσότητα Παραγγελίας) δεν έχει καμία σχέση με τους λαβύρινθους. Είναι μια κλασική μέθοδος για τον προσδιορισμό της βέλτιστης ποσότητας παραγγελίας με σκοπό την ελαχιστοποίηση του συνολικού κόστους αποθεμάτων. Διαδόθηκε το 1934 από τον R.H. Wilson, αν και η αρχική ιδέα προτάθηκε από τον Ford Whitman Harris το 1913.

Σκοπός του είναι να βρει το μέγεθος παρτίδας Q που εξισορροπεί το κόστος υποβολής παραγγελιών και το κόστος διατήρησης αποθέματος. Με βάση την ετήσια ζήτηση (D), το κόστος ανά παραγγελία (K) και το κόστος αποθήκευσης ανά μονάδα ανά περίοδο (G), λαμβάνεται μια ποσότητα που, στο πλαίσιο των υποθέσεων της, μειώνει το συνολικό κόστος αποθέματος.

Ο πιο συνηθισμένος τύπος εκφράζεται ως Q = √(2·D·K/G). Αυτός ο αριθμός δίνει το μέγεθος κάθε παρτίδας. Από εκεί, ο αριθμός των ετήσιων παραγγελιών θα είναι D/Q, και με αυτόν μπορείτε να εξαγάγετε τον κύκλο παραγγελίας. Είναι επίσης σημαντικό να ορίσετε το σημείο αναπαραγγελίας (λαμβάνοντας υπόψη τον χρόνο παράδοσης) και το απόθεμα ασφαλείας για να αποφύγετε τις ελλείψεις αποθεμάτων, αν και ο βασικός τύπος δεν ενσωματώνει ρητά την αβεβαιότητα.

Τυπικές εφαρμογές: Χρησιμοποιείται με πρώτες ύλες ή οποιοδήποτε είδος εμπορεύματος για το οποίο το κόστος αγοράς και αποθήκευσης μπορεί να προσδιοριστεί με αξιοπιστία. Στην πράξη, γνωρίζοντας τα D, K και G με επαρκή αξιοπιστία, η εταιρεία μπορεί να διαστασιολογήσει τις παρτίδες της και να προγραμματίσει τις προμήθειές της με μεγαλύτερο έλεγχο.

Υποθέσεις, πλεονεκτήματα και περιορισμοί του μοντέλου Wilson

Οι υποθέσεις αυτές είναι κρίσιμες για την εγκυρότητα του αποτελέσματος. Το μοντέλο 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 παραγγελίες ετησίως. Με αυτό το μέγεθος παρτίδας, η εταιρεία τείνει προς ένα πιο αποτελεσματικό επίπεδο αποθεμάτων , μειώνοντας το κόστος αποθήκευσης χωρίς να αυξάνει σημαντικά το κόστος προετοιμασίας παραγγελιών.

Πέρα από τον ίδιο τον τύπο, συνιστάται να υπολογίζεται το σημείο αναπαραγγελίας λαμβάνοντας υπόψη τον χρόνο παράδοσης και να διατηρείται το απόθεμα ασφαλείας, επειδή το καθαρό μοντέλο δεν λαμβάνει υπόψη την αβεβαιότητα. Επίσης, δεν εκτιμά τον αντίκτυπο των εκπτώσεων όγκου, οι οποίες μερικές φορές θα μπορούσαν να αντισταθμίσουν το κόστος αποθεμάτων εάν χρησιμοποιούνται μεγαλύτερες παρτίδες.

Δεν πρέπει να συγχέεται με το θεώρημα του Wilson (θεωρία αριθμών)

Το θεώρημα του Wilson ανήκει στην αρθρωτή αριθμητική και ουσιαστικά δηλώνει ότι ένας ακέραιος αριθμός n > 1 είναι πρώτος αν και μόνο αν (n − 1)! ≡ −1 (mod n). Η συνέπεια «αν το n είναι πρώτο τότε (n − 1)! ≡ −1 (mod n)» συνήθως ονομάζεται αυστηρά «θεώρημα του Wilson», και η αντίστροφη συνέπεια ισχύει επίσης. Ιστορικά, ο Edward Waring απέδωσε το αποτέλεσμα στον John Wilson (1770), αν και η πρώτη γνωστή απόδειξη δόθηκε από τον Lagrange (1771), και η διατύπωση χρονολογείται στην πραγματικότητα από τον Alhazen τον 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). Modulo 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 είναι δαπανηρός και υπάρχουν ταχύτερες δοκιμές (όπως οι Miller-Rabin ή οι ντετερμινιστικές δοκιμές για συγκεκριμένες τάξεις). Ακόμα κι έτσι, μπορεί να χρησιμοποιηθεί για την εξαγωγή χρήσιμων ιδιοτήτων: για παράδειγμα, αν το p = 2n + 1 είναι πρώτος, λαμβάνουμε ∏_{j=1}^{n} j^2 ≡ (−1)^{n+1} (mod p). Και, ως μερικό πόρισμα, το −1 είναι ένα τετραγωνικό υπόλοιπο modulo 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.

Ο Γκάους γενίκευσε το θεώρημα: το γινόμενο όλων των μονάδων modulo 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 περιλαμβάνεται επίσης για σύγκριση. Αυτά τα δεδομένα δείχνουν ξεκάθαρα πώς συμπεριφέρεται το θεώρημα του Wilson σε μικρές περιπτώσεις και βοηθούν στην εδραίωση της διαίσθησης.

Εφαρμογές, όρια και συστάσεις

Αν θέλετε να δημιουργήσετε αμερόληπτους λαβύρινθους, χρησιμοποιήστε τον αλγόριθμο του Wilson: η βάση του σε τυχαίους περιπάτους με διαγραφή βρόχου εξασφαλίζει ομοιόμορφα δέντρα. Για τη διαχείριση αποθεμάτων, το μοντέλο Wilson είναι χρήσιμο όταν η ζήτηση, οι τιμές και το κόστος είναι σταθερά και γνωστά με ακρίβεια. Σε ασταθή περιβάλλοντα, μεθοδολογίες όπως το Kanban, το Just-in-Time ή το προηγμένο λογισμικό σχεδιασμού μπορεί να είναι πιο κατάλληλες. Και στα μαθηματικά, το θεώρημα του Wilson είναι ένα θεωρητικό διαμάντι με ενδιαφέρουσες παράγωγες (όπως τετραγωνικά υπόλοιπα), αλλά δεν είναι πρακτικό ως δοκιμή πρωτογένειας για μεγάλους αριθμούς.

Δεν υπάρχει ένας ενιαίος τύπος για τον υπολογισμό του κόστους παραγγελιών και αποθήκευσης: κάθε εταιρεία πρέπει να αναλύει τις ώρες, τις διαδικασίες, τη μεταφορά, την παραλαβή, το προσωπικό, το ενοίκιο, την ενέργεια, την ασφάλιση και το χρηματοοικονομικό κόστος. Πολλοί επαγγελματίες εκτιμούν τις ώρες ανά λειτουργία και εφαρμόζουν μια ωριαία χρέωση για τη δημιουργία εσόδων. Αυτή η προσαρμογή είναι το κλειδί για να διασφαλιστεί ότι η υπολογισμένη ποσότητα παραγγελίας (Q) είναι χρήσιμη και, μαζί με ένα καλό σημείο αναπαραγγελίας και ένα απόθεμα ασφαλείας, βοηθά στην αποφυγή ελλείψεων ή πλεονάζοντος αποθέματος.

Αξίζει να θυμηθούμε ότι ο όρος «αλγόριθμος του Wilson» στις αναζητήσεις συνήθως υποδεικνύει τη γεννήτρια λαβυρίνθου, ενώ το «μοντέλο Wilson» ή «EOQ» αναφέρεται σε αποθέματα και το «θεώρημα του Wilson» στη θεωρία αριθμών. Η διάκρισή τους από την αρχή αποφεύγει τη σύγχυση και σας επιτρέπει να αξιοποιήσετε καλύτερα κάθε προσέγγιση: αμερόληπτοι λαβύρινθοι, βέλτιστες παρτίδες υπό ρεαλιστικές υποθέσεις και ένας κομψός χαρακτηρισμός των πρώτων αριθμών που, αν και δεν αποτελεί πρακτική απόδειξη πρωτογένειας, παραμένει ένα πολύτιμο κομμάτι του μαθηματικού παζλ.

Σχετικό άρθρο:

Ο αλγόριθμος του Kruskal και η εφαρμογή του σε γραφήματα