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

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

Giới thiệu 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 mô tả thuật toán này lần đầu tiên vào năm 1956 trong bài báo "Về cây con bao trùm ngắn nhất của một đồ thị và bài toán người bán hàng rong".

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

Cách thuật toán Kruskal hoạt động để tạo mê cung

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

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

Bước 2: Phân loại các bức tường

• 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ý các bức tường

• Lặp lại thao tác với các bức tường đã được xáo trộn.
• Nếu hai ô bị ngăn cách bởi bức tường thuộc về các 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 nhóm, hãy bỏ qua bức tường (để tránh vòng lặp).

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 với nhau, tạo thành một cây bao trùm duy nhất.
• Cuối cùng, mọi tế bào đều được kết nối với nhau mà không có vòng lặp hay đoạn bị cô lập.

Vì thuật toán Kruskal dựa trên việc hợp nhất các tập hợp, 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 thuật toán Union-Find bằng PHP của tôi tại đây: [Link]

Đọc thêm

Nếu bạn thích bài viết này, bạn cũng có thể thích những gợi ý sau:

• Máy phát mê cung săn và giết
• Trình tạo mê cung Recursive Backtracker
• Máy phát mê cung thuật toán cây phát triển