Máy phát mê cung thuật toán Kruskal

Thuật toán Kruskal là thuật toán cây bao trùm nhỏ nhất có thể được điều chỉnh để tạo mê cung. Thuật toán này đặc biệt hiệu quả để tạo ra mê cung hoàn hảo. Một giải pháp thay thế cho thuật toán Kruskal là thuật toán Prim, cũng là thuật toán cây bao trùm nhỏ nhất, nhưng vì chúng tạo ra các mê cung giống hệt nhau và Kruskal chạy nhanh hơn nên tôi không bận tâm đến việc triển khai Prim.

Một mê cung hoàn hảo là một mê cung mà chỉ có đúng một đường đi từ bất kỳ điểm nào trong mê cung đến bất kỳ điểm nào khác. Điều đó có nghĩa là bạn không thể đi vòng tròn, nhưng bạn sẽ thường gặp ngõ cụt, buộc bạn phải quay lại và quay trở lại.

Bản đồ mê cung được tạo ở đây bao gồm một phiên bản mặc định không có bất kỳ vị trí bắt đầu và kết thúc nào, vì vậy bạn có thể tự quyết định: sẽ có một giải pháp từ bất kỳ điểm nào trong mê cung đến bất kỳ điểm nào khác. Nếu bạn muốn có cảm hứng, bạn có thể bật vị trí bắt đầu và kết thúc được đề xuất - và thậm chí xem giải pháp giữa hai điểm đó.

Về thuật toán Kruskal

Thuật toán Kruskal được tạo ra bởi Joseph Bernard Kruskal, Jr., một nhà toán học, nhà thống kê và nhà khoa học máy tính người Mỹ. Ông lần đầu tiên mô tả thuật toán vào năm 1956 trong bài báo "On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem."

Thuật toán được thiết kế để tìm cây bao trùm nhỏ nhất (MST) của đồ thị, đảm bảo rằng tất cả các đỉnh đều được kết nối với tổng trọng số cạnh nhỏ nhất có thể trong khi tránh chu trình.

Thuật toán Kruskal hoạt động như thế nào để tạo ra mê cung

Bước 1: Khởi tạo

• Xử lý mỗi ô trong mê cung như một tập hợp riêng biệt (một thành phần duy nhất).
• Liệt kê tất cả các bức tường giữa các ô liền kề thành các cạnh tiềm năng.

Bước 2: Sắp xếp các bức tường

• Xáo trộn hoặc sắp xếp ngẫu nhiên các bức tường. Nếu triển khai nó như một thuật toán Kruskal thực sự, hãy sắp xếp các bức tường theo thứ tự ngẫu nhiên (vì việc tạo mê cung không yêu cầu trọng số).

Bước 3: Xử lý tường

• Lặp lại qua các bức tường bị xáo trộn.
• Nếu hai ô được chia bởi bức tường thuộc hai tập hợp khác nhau (tức là chúng chưa được kết nối trong mê cung), hãy loại bỏ bức tường và hợp nhất các tập hợp.
• Nếu chúng đã nằm trong cùng một bộ, hãy bỏ qua bức tường (để tránh chu kỳ).

Bước 4: Tiếp tục cho đến khi hoàn thành

• Lặp lại quá trình này cho đến khi tất cả các ô được kết nối, tạo thành một cây mở rộng duy nhất.
• Cuối cùng, mỗi ô được kết nối với nhau mà không cần vòng lặp hay các phần riêng biệt.

Vì thuật toán Kruskal dựa vào việc hợp nhất các tập hợp, nên nó có thể được tối ưu hóa bằng cách sử dụng thuật toán Union-Find, cung cấp một cách hiệu quả để theo dõi các ô được kết nối trong quá trình tạo mê cung. Bạn có thể xem triển khai PHP của tôi về thuật toán Union-Find tại đây: Tập hợp rời rạc (Thuật toán hợp nhất-tìm kiếm) trong PHP