Dạo trước, thầy mình có cho giải 1 bài mê cung đơn giản. Ở nhà khá là có hứng thú nên mình có tìm hiểu kĩ hơn về nó. Với lại mình cũng muốn thử viết tool game giải mê cung (do là game 3d nên không thể nào bao quát được hết toàn bộ mê cung được).
=> Đề: Bắt đầu xuất phát ở 1 địa điểm bất kì trong mê cung vô định hình, tìm được lối ra (không nhất thiết là đường đi ngắn nhất)
- Không dùng góc nhìn từ trên xuống
- Không thể đi xuyên tường (tất nhiên)
- Mê cung chỉ có 1 lối ra duy nhất
Nguồn
Qua những gì mình đọc qua và kiếm trên Wikipedia thì mình thấy có 3 phương pháp chính để giải:
Đặt bàn tay trái/phải lên tường và đi. Nhưng bởi vì phương pháp chỉ áp dụng khi tường của mê cung nối với nhau hay vị trí xuất phát là từ phía bên ngoài. Nên nếu gặp trường hợp như này (x là vị trí xuất phát):
##### ######
# #
# ### ### #
# # # # # #
# # # x # # #
# ### ### #
# #
################
thì bạn có đặt tay trái/phải gì cũng sẽ đi vòng quanh bức tường nên phương pháp này coi như bỏ.
Còn Pledge Algorithm và Trémaux’s Algorithm. (Mình vẫn đang tìm hiểu về cộng góc của thuật toán Pledge).
Có trường hợp nào mà 1 trong 2 thuật toán này hoạt động không hiệu quả không?
Vì Pledge Algorithm vẫn dựa trên việc đặt tay lên tường nên nếu trong một mê cung 3 chiều (ví dụ: tại điểm giao có 6 hướng: tiến, lùi, trái, phải, lên, xuống) thì thuật toán có hoạt động hiệu quả hay không (vì mình từng đọc đâu đó nói rằng phương pháp đặt tay lên tường sẽ vô dụng trước loại mê cung này.)
Vậy Trémaux’s Algorithm vẫn sẽ áp dụng hiệu quả trên loại mê cung này không? Hay còn phương pháp nào khác?
Nếu nói chung chung về các giải thuật để giải mê cung thì còn phương pháp nào khác không (Mình biết vẫn có cái đi random nhưng mình thấy nó không hiệu quả lắm, có khả năng sẽ mất rất lâu để giải mê cung)?
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?