Key: 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
Hình 1: 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
Hình 2: 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
Hình 3: 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
Hình 4: 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.
Như vậy, chúng ta vừa điểm qua các phương pháp tìm đường mê cung, mong rằng bài viết đã mang đến kiến thức hữu ích cho bạn. Nếu muốn thử giải các mê cung thông qua mô hình trò chơi, thì hãy ghé đến Tomcity tại địa chỉ SN14, Ngõ 455, đường 72 Dương Nội, Hà Đông – Hà Nội để sở hữu các trò chơi mê cung đặc sắc. Nếu bạn ở xa, hãy liên hệ với hotline 0906.019.556- 0979.362.737 để được hỗ trợ mua hàng.