Gennítria lavyrínthou algórithmou Kruskal

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

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

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

Σχετικά με τον Αλγόριθμο του Kruskal

Ο αλγόριθμος του Kruskal δημιουργήθηκε από τον Joseph Bernard Kruskal, Jr., έναν Αμερικανό μαθηματικό, στατιστικολόγο και επιστήμονα υπολογιστών. Περιέγραψε για πρώτη φορά τον αλγόριθμο το 1956 στην εργασία του "Σχετικά με το Συντομότερο Εκτεινόμενο Υποδέντρο ενός Γράφου και το Πρόβλημα του Περιοδεύοντος Πωλητή".

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

Πώς λειτουργεί ο αλγόριθμος του Kruskal για τη δημιουργία λαβυρίνθου

Βήμα 1: Αρχικοποίηση

• Αντιμετωπίστε κάθε κύτταρο στον λαβύρινθο ως ξεχωριστό σύνολο (ένα μοναδικό στοιχείο).
• Καταγράψτε όλα τα τοιχώματα μεταξύ γειτονικών κελιών ως πιθανές ακμές.

Βήμα 2: Ταξινόμηση τοίχων

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

Βήμα 3: Τοίχοι διεργασίας

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

Βήμα 4: Συνέχεια μέχρι την ολοκλήρωση

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

Δεδομένου ότι ο αλγόριθμος του Kruskal βασίζεται σε συγχωνευμένα σύνολα, μπορεί να βελτιστοποιηθεί χρησιμοποιώντας τον αλγόριθμο Union-Find, ο οποίος παρέχει έναν αποτελεσματικό τρόπο παρακολούθησης συνδεδεμένων κελιών κατά τη δημιουργία λαβυρίνθου. Μπορείτε να δείτε την υλοποίηση του αλγορίθμου Union-Find σε PHP εδώ: Σύνδεσμος

Περαιτέρω ανάγνωση

Αν σας άρεσε αυτή η ανάρτηση, ίσως σας αρέσουν και αυτές οι προτάσεις:

• Γεννήτρια λαβύρινθου αλγορίθμου του Eller
• Γεννήτρια λαβύρινθου αλγορίθμων δέντρων
• Γεννήτρια λαβύρινθου αλγορίθμου του Wilson