Ý bác kia chắc đang nói cái mê cung này đó lão Mai.
Đầu tiên cách giải quyết mê cung của LM là theo cách 'Chọn ngẫu nhiên (random mouse)":
Nó chỉ đơn giản là chạy theo một đường thẳng cho đến khi gặp một đường giao nhau thì đưa ra quyết định ngẫu nhiên về hướng tiếp theo để chạy. Mặc dù phương pháp này cuối cùng luôn luôn tìm ra giải pháp đúng, nhưng thuật toán này có thể cực kỳ chậm.
-wiki
=> lý do mà LM còn chạy mòng mòng tới h là do đây
.Giả sử cái mê cung này có đường ra, ta cũng vào chém gió cách thoát khỏi mê cung lần này so với lão Vong Béo.
1. Đầu tiên là thuật toán đơn giản và phổ biến nhất: "Bám theo tường":
Thuật toán bám theo tường (wall follower) là một quy tắc nổi tiếng nhất để vượt qua mê cung, còn được gọi là quy tắc tay trái hoặc quy tắc tay phải. Nếu mê cung chỉ liên thông đơn giản nghĩa là tất cả các bức tường của nó được kết nối với nhau hoặc kết nối với đường bao quanh mê cung, thì bằng cách dò một tay lên một bức tường của mê cung thì người đi đảm bảo không bị lạc và tìm được lối ra nếu có một lối ra trên đường bao; hoặc nếu không có lối ra thì sẽ quay trở lại lối vào và sẽ đi qua tất cả các đường của mê cung ít nhất 1 lần.
-wiki
Nếu mê cung có các tường rời nhau, đồng thời lối vào lối ra của mê cung nằm trên tường bao của mê cung, thì thuật toán bám tường vẫn có thể tìm được đường ra. Tuy nhiên, nếu điểm vào nằm bên trong mê cung và tách rời khỏi lối ra, thì bám theo tường sẽ chỉ có thể đi thành 1 vòng cục bộ và không tìm được lối ra.
Nhận xét thấy mê cung của LM chắc chắn là không phải dạng liên thông đơn giản nên ta chuyển sang cách thứ 2 (Về cơ bản, thuật toán này được phát hiện từ thế kỷ 19 đã được sử dụng khoảng hàng trăm năm sau như một phương pháp tìm kiếm ưu tiên chiều sâu).
2. Thứ 2 là thuật toán Trémaux được Charles Pierre Trémaux phát minh, sử dụng các dấu hiệu để ghi nhớ đường đi, ví dụ đánh dấu trên mặt sàn, là một phương pháp hiệu quả để tìm lối ra của một mê cung. Thuật toán có thể giải tất cả các mê cung có đường đi rõ ràng.
Một đường trong mê cung sẽ được ghi nhớ bằng cách đánh dấu bởi 1 trong 3 trạng thái: chưa qua, đã qua 1 lần hoặc qua 2 lần. Một đường được chọn để đi sẽ luôn được đánh dấu bằng 1 vạch dưới sàn (từ ngã giao này đến ngã giao kia). Tại điểm bắt đầu có thể chọn một hướng bất kỳ (nếu có nhiều hơn một hướng). Khi đến một ngã giao, nếu các đường rẽ đều chưa qua, thì chọn ngẫu nhiên 1 đường để đi và đánh dấu đường ấy 1 vạch. Khi gặp một ngã giao mà đường trước mặt theo hướng đi hiện tại đã có 1 dấu, và đường đang đi hiện tại chỉ mới đánh dấu 1 lần, thì quay trở lại và đánh dấu đường ấy 2 vạch. Nếu đến 1 ngã giao mà không rơi vào 2 trường hợp trên, thì chọn đường đi có ít vạch nhất, và nhớ đánh dấu đường ấy luôn. Khi đến đích, thì những con đường chỉ đánh dấu 1 vạch là đường dẫn trở về điểm xuất phát.
Nếu không có ngã ra, thì phương pháp này sẽ dẫn người đi trở về lại điểm xuất phát, và khi ấy tất cả con đường sẽ đánh dấu 2 vạch, mỗi vạch tương ứng với 1 hướng đi. Kết quả được gọi là vạch đôi 2 chiều.
-wiki
Cảm ơn wiki đã tài trợ kiến thức này và các đạo hữu chỉ cần read for fun thôi nhé
