[Mỗi ngày 1 thuật toán] Bài toán Vượt qua mê cung

1. Ý tưởng chính của bài toán

Bài toán Mê Cung yêu cầu tìm đường đi từ điểm bắt đầu đến điểm kết thúc trong một mê cung. Mê cung được biểu diễn dưới dạng một ma trận, trong đó các ô có thể là đường đi hoặc chướng ngại vật. Chỉ có thể di chuyển theo phương ngang hoặc thẳng đứng, không thể di chuyển chéo.

Thuật toán phổ biến nhất để giải quyết bài toán này là thuật toán tìm kiếm theo chiều sâu (Depth-First Search – DFS) hoặc thuật toán tìm kiếm theo chiều rộng (Breadth-First Search – BFS). Cả hai thuật toán đều có ưu và nhược điểm riêng, tùy vào yêu cầu của bài toán mà ta chọn thuật toán phù hợp.

1.1. Thuật toán DFS

• Ý tưởng: Khám phá sâu vào một nhánh của cây tìm kiếm trước khi chuyển sang nhánh khác.
• Ưu điểm: Đơn giản, dễ cài đặt.
• Nhược điểm: Có thể mắc kẹt trong các nhánh vô hạn và không tìm được đường đi ngắn nhất.

1.2. Thuật toán BFS

• Ý tưởng: Khám phá tất cả các nút ở một mức độ trước khi chuyển sang mức độ tiếp theo.
• Ưu điểm: Luôn tìm được đường đi ngắn nhất (nếu có đường đi).
• Nhược điểm: Tốn nhiều bộ nhớ hơn DFS.

2. Mã nguồn C++

3. Mã nguồn Java

4. Mã nguồn Python

5. Giải thích

• Hàm isValid: Kiểm tra xem một ô có hợp lệ để di chuyển đến hay không.
• Hàm DFS:
  • Đánh dấu ô hiện tại là đã đi qua.
  • Thêm tọa độ ô vào path để lưu lại đường đi.
  • Kiểm tra điều kiện đích.
  • Khám phá các ô lân cận bằng cách đệ quy gọi hàm DFS.
  • Quay lui khi không tìm thấy đường đi.
• Path: Một vector để lưu trữ đường đi, giúp in ra kết quả.

6. Lưu ý

• Mảng visited: Dùng để đánh dấu các ô đã đi qua, tránh lặp vô hạn.
• Điều kiện dừng: Khi gặp tường hoặc ô đã đi qua, hoặc khi tìm thấy đích.
• Khám phá các ô lân cận: Thực hiện đệ quy để khám phá các ô lên, xuống, trái, phải.

7. Cải tiến và mở rộng

7.1. Cải tiến

• Có thể tạo một kiểu dữ liệu để để lưu trữ tọa độ của một ô, giúp code gọn gàng hơn.
• In đường đi: In ra đường đi tìm được.
• Điều kiện đích: Bạn có thể tùy chỉnh điều kiện đích theo yêu cầu của bài toán.
• Tối ưu hóa: Có thể tối ưu hóa bằng cách sử dụng các kỹ thuật như cắt tỉa tìm kiếm, đánh dấu các ô đã bị loại bỏ.

7.2. Mở rộng

• BFS: Để tìm đường đi ngắn nhất, bạn có thể sử dụng thuật toán BFS.
• A:* Để tìm đường đi ngắn nhất hiệu quả hơn trong các mê cung lớn, bạn có thể sử dụng thuật toán A*.
• Mê cung 3 chiều: Mở rộng bài toán sang không gian 3 chiều.
• Mê cung có trọng số: Mỗi ô trong mê cung có một trọng số thể hiện chi phí di chuyển qua ô đó.

Xem thêm các bài viết thú vị về Thuật toán tại đây!