Bật mí các phương pháp tìm đường mê cung

Mê cung là hệ thống chứa rất nhiều nhánh, ngã rẽ đường khác nhau trong đó có cả ngõ cụt và chỉ có 1 đường thoát duy nhất. Các đường trong mê cung được ngăn cách bởi những vách ngăn lớn, người đi vào mê cung chỉ có thể nhìn thấy 1 phần con đường, rất khó xác định phương hướng. Để giải đáp và tìm đường đi đúng trong 1 mê cung mời bạn cùng Tomcity điểm qua các phương pháp tìm đường mê cung ngay sau đây.

Phương pháp bám theo tường

Phương pháp bám tường

Phương pháp bám theo tường còn gọi là Wall Follower hay quy tắc bàn tay trái/ tay phải, một trong các phương pháp tìm đường mê cung được biết đến nhiều nhất. Nội dung của phương pháp này là việc bạn chọn 1 hướng cố định để đi, dùng tay trái hoặc tay phải bám vào 1 bờ tường trong mê cung và đi theo nó. Phương pháp này giúp bạn không bị lạc và dễ tìm thấy lối ra.

Nhược điểm của phương pháp này ở điểm nó chỉ áp dụng được cho các mê cung có liên kết đường cơ bản, nghĩa là các ngã rẽ trong mê cung ít, ngõ cụt không quá nhiều, đường đi liên kết trực tiếp với nhau hoặc kết nối với đường bao xung quanh mê cung. Ngược lại đối với mê cung phức tạp thì cách này hoàn toàn kém hiệu quả.

Phương pháp lắp đường cụt

Phương pháp lắp kín ngõ cụt

Trong các mê cung lớn có chứa rất nhiều ngõ cụt khác nhau, muốn dễ dàng thoát được khỏi mê cung thì lắp kín các đường cụt tránh đi lạc mất thời gian là cách hữu hiệu. Tuy nhiên, phương pháp này chỉ có thể giải được các mê cung được vẽ trên giấy hay một chương trình máy tính, trên thực tế nó chỉ phát hiệu hiệu quả khi bạn đã biết hết trước thiết kế của toàn bộ mê cung.

Để thực hiện được phương pháp này bạn thực hiện theo các bước sau:

Bước 1: Xem xét toàn bộ kiến trúc của mê cung, sau đó tìm kiếm tất cả các ngõ cụt trong mê cung.
Bước 2: Dùng phương pháp “lấp kín” toàn bộ các ngõ cụt từ điểm cụt đầu tiên đến ngã giao gần nhất.

Phương pháp thuật toán

Ngoài các phương pháp tìm đường mê cung thiên về cảm tính và có phần mơ hồ bên trên, hiện nay các chuyên gia đã và đang thử nghiệm nhiều phương pháp giải mê cung bằng thuật toán. Sau đây là 3 thuật toán giải mê cung được biết đến nhiều nhất:

Thuật toán chọn đường ngẫu nhiên

Thuật toán chọn đường ngẫu nhiên

Đây là một thuật toán rất đơn giản thực hiện bằng cách cho một robot thông minh hoặc một chú chuột (Random Mouse) chạy vào mê cung. Cách vận hành thuật toán không hề phức tạp, Robot được thiết lập chạy theo đường thẳng, khi đến ngã rẽ nó sẽ quyết định chọn hướng để đi tiếp. Với phương pháp này chắc chắn robot sẽ thoát khỏi mê cung, tuy nhiên trong một số trường hợp thời gian diễn ra sẽ cực kỳ chậm.

Thuật toán Pledge

Thuật toán Pledge do John Pledge tìm ra, phương pháp này được áp dụng cho các mê cung phức tạp có lối ra không kết nối với tường bao và các đường đi trong mê cung rời rạc. Thuật toán Pledge dùng chủ yếu trong trường hợp vượt các vật cản trong mê cung, từ đó xác định hướng đi chính xác nhất.

Nội dung thuật toán, khi gặp một vật cản bất kỳ sẽ bám dọc theo bờ tường của vật cản, đồng thời điếm góc quay. Sau khi thực hiện hành động bám tường và quay về đúng với hướng đi xác định ban đầu, và hướng góc quay bằng 0 thì xem như vượt vật cản thành công, lúc này chỉ cần đi theo hướng đã chọn ban đầu là được. Lưu ý: Với thuật toán này, bạn chỉ có thể thoát khỏi mê cung khi thỏa mãn 2 điều kiện là hướng hiện tại trùng với hướng bạn đã chọn ban đầu và tổng số góc đã quay bằng 0.

Thuật toán Tremaux

Thuật toán Tremaux

Thuật toán Tremaux là một trong các phương pháp tìm đường mê cung hữu hiệu nhất, có thể giải được mọi mê cung có đường đi rõ ràng. Thuật toán này do Charles Pierre Trémaux phát minh ra . Nội dung thuật toán cơ bản là việc dùng các dấu hiệu để ghi nhớ đường trong mê cung, ví dụ: đánh dấu đường đi.

Theo thuật toán, 1 đường trong mê cung phải được đánh dấu bằng 1 trong 3 trạng thái là chưa đi qua, đã đi qua 1 lần và đã đi qua 2 lần. Cách thức vận hành thuật toán như sau:

Khi bắt đầu vào mê cung chọn hướng 1 hướng đi bất kỳ, đến ngã giao các đường thì đánh dấu 1 vạch. Khi đến ngã giao chưa có vạch nào thì đánh dấu 1 vạch và đi tiếp. Nếu đến ngã giao mà đường đi hướng trước mặt đã được đánh 1 vạch và đường hiện tại cũng đã có 1 vạch, thì quay lại rồi đi tiếp đồng thời đánh dấu vạch thứ 2. Bạn cứ đi vào những ngã có ít vạch nhất, và đánh dấu chúng. Những đoạn đường có 1 vạch chính là đường chính xác để bạn thoát khỏi mê cung.

VƯƠNG QUỐC ĐỒ CHƠI TOMCITY - TOMCITY TOYS FOR KIDS
------------------------
☆ Xem thêm nhiều đồ chơi tại: https://tomcity.vn/
☆ Ghé thăm Fanpage của chúng mình: https://www.facebook.com/tomcityvietnam
☆ Gian hàng shopee: https://shopee.vn/tomcity_store
☆ Liên hệ với chúng mình: 0906018559 hoặc 0979362737