Giải mã mê cung

Author: Quang Nguyễn

Trong blog này, chúng ta sẽ cùng tìm hiểu qua hai thuật toán tìm kiếm rất phổ biến trong khoa học máy tính là DFS và BFS để giúp máy tính thực hiện nhiệm vụ tìm đường đi trong mê cung này nhé. Hai thuật toán này có sử dụng hai kiểu cấu trúc dữ liệu đã được học ở trong bài 6 của lớp CS101 đấy!!!

1. Mê cung:

Một mê cung của chúng sẽ được biểu diễn như hình dưới đây, với các tường được biểu diễn dưới ô vuông màu xám, đường đi dưới dạng các ô vuông màu vàng đất, điểm bắt đầu với biển bàn tay chỉ dẫn màu xanh lá cây, và điểm kết thúc là lá cờ màu đỏ:

Các bạn có thấy hình ảnh về mê cung có quen không nào?? Chúng ta đã được biết đến khái niệm mảng hai chiều, và mê cung có thể được biểu diễn bằng mảng hai chiều gồm các hàng và cột. Nhiệm vụ của chúng ta là phải tìm ra đường đi từ điểm bắt đầu cho đến điểm kết thúc:

• 

2. Thuật toán Depth-first search (DFS):

Đầu tiên hãy tưởng tượng rằng bạn đang đi du lịch Bà Nà Hills ở Đà Nẵng, và bạn được trải nghiệm giải mã mê cung ngoài đời thật tại Khu vườn bí ẩn. Và bạn chợt nhận ra là trong thực tế, thay vì nhìn trước được toàn bộ mê cung như các trò chơi được in trên báo, giờ đây bạn chỉ có thể nhìn được một vài vị trí xung quanh bản thân để quyết định xem hướng nào sẽ đi tiếp.

Và máy tính của chúng ta cũng vậy, trong thực tế máy tính chỉ có thể nhìn thấy đường đi xung quanh kế bên mình. 

Vậy ở tại mỗi vị trí chúng ta sẽ quyết định đường đi tiếp theo như thế nào nhỉ? Làm sao để chúng ta tránh đi lòng vòng và quay đi quay lại đường mình đã đi? Chọn bừa một hướng đi và hy vọng nó sẽ dẫn đến lối thoát hay có một chiến thuật thông minh hơn? Ở phần này chúng ta sẽ cùng tìm hiểu cách tiếp cận đầu tiên thông qua thuật toán DFS. 

Thuật toán DFS là viết tắt của Depth-First Search, có nghĩa là tìm kiếm theo chiều sâu. Khi thực hiện thuật toán này chúng ta sẽ sử dụng cấu trúc dữ liệu ngăn xếp (stack) đã được học ở trong bài 6. Ý tưởng là chúng ta sẽ tìm theo một nhánh đến khi tìm được đường ra, nếu hết đường thì mới quay lại đến khi thấy nhánh mới.

Để hiểu rõ hơn về thuật toán này chúng ta sẽ giúp bạn Trẩu tìm đường đi từ điểm bắt đầu đến điểm kết thúc qua ví dụ đơn giản dưới đây:

Ở ví dụ này, chúng ta sẽ minh hoạ cấu trúc dữ liệu ngăn xếp bằng một chiếc hộp carton với các phần tử trong stack là các tờ giấy đánh số được bỏ vào hộp. Các bước của thuật toán DFS sẽ như sau:

• Bước 1: Đến điểm xuất phát
• Bước 2: Đánh số vị trí hiện tại (lưu ý rằng các số không được trùng nhau)
• Bước 3: Nhìn xung quanh theo thứ tự Trên – Dưới – Trái – Phải xem có đường nào chưa được đánh dấu không. Nếu có, sang bước 4. Nếu không, sang bước 5.
• Bước 4: Đi sang ô tiếp theo, ghi lại số của ô cũ vào trong tờ giấy rồi bỏ vào hộp. Quay lại bước 2.
• Bước 5: Lấy lại 1 tờ giấy trong hộp, quay lại vị trí trong tờ giấy. Quay lại bước 3.

Đầu tiên theo bước 1 và bước 2 bạn Trẩu sẽ đến điểm xuất phát và đánh số vị trí bạn đang đứng hiện tại là số 1 và hiện tại chiếc hộp vẫn đang rỗng:

Sau đó, bạn Trẩu tiếp tục thực hiện bước 3 nhìn xung quanh xem có đường nào theo thứ tự Trên – Dưới – Trái – Phải chưa được đánh dấu không, ở bước này chúng ta thấy chỉ có một đường duy nhất cho bạn Trẩu là đi sang phải:

Bạn Trẩu thực hiện bước 4 quyết định đi sang ô bên phải, đồng thời ghi lại số của ô cũ vào trong tờ giấy và bỏ vào hộp:

Sau đó, chúng ta quay lại bước 2 bằng cách đánh số vị trí hiện tại là 2. Tiếp theo thực hiện bước 3 bằng các xác định đường đi theo thứ tự Trên – Dưới – Trái – Phải và được kết quả như sau:

Ở đây bạn Trẩu của chúng ta có hai lựa chọn di chuyển sang phải hoặc di chuyển xuống dưới. Tại vì trong số 4 hướng di chuyển Trên – Dưới – Trái – Phải, hướng di chuyển Dưới được ưu tiên trước hướng di chuyển Phải nên ở bước này bạn Trẩu sẽ di chuyển xuống dưới, đồng thời ghi lại số của ô cũ là 2 và bỏ vào hộp:

Tiếp tục thực hiện các bước của thuật toán, chúng ta sẽ đến được trạng thái như sau:

Ở bước này, bạn Trẩu có hai hướng di chuyển là lên trên và sang phải, tuy nhiên vì lựa chọn Trên được ưu tiên trước lựa chọn Phải trong bước 3 của thuật toán nên bạn Trẩu tiếp tục di chuyển lên trên và thực hiện tiếp các bước của thuật toán chúng ta sẽ được:

Theo như bước 3, đến vị trí này thì chúng ta thấy xung quanh bạn Trẩu tất ở các đường đều đã được đánh dấu, vì vậy chúng ta sẽ di chuyển đến bước 5 để hướng dẫn bạn Trẩu tiếp tục di chuyển. Đầu tiên chúng ta sẽ lấy 1 tờ giấy ờ trong hộp ra, tờ giấy này có đánh số 8, vì vậy bạn Trẩu sẽ di chuyển đến vị trí được đánh dấu số 8 trên mê cung và quay lại bước 3:

Ở vị trí này chúng ta thấy tất cả các vị trí xung quanh Trẩu đều đã được đánh dấu nên chúng ta sẽ tiến đến thực hiện bước 5 đưa Trẩu quay lại về vị trí 7:

Sau khi quay lại hai vị trí cuối cùng bạn Trẩu cũng tìm được một hướng đi chưa được đánh dấu là di chuyển sang bên phải vị trí số 7:

Bạn Trẩu đi theo hướng bên phải và tiếp tục thực hiện các bước của thuật toán. Và voila, cuối cùng bạn Trẩu của chúng ta cũng đến được vị trí đích:

Vậy bây giờ làm thế nào để đi lại vị trí ban đầu nhỉ? Rất đơn giản, tất cả các thông tin về đường đi từ vị trí ban đầu đã được lưu lại trong chiếc hộp. Thứ tự các mảnh giấy từ trên xuống dưới trong chiếc hộp, bước nào đi sau cùng sẽ được thực hiện trước (Last in First out – LIFO): 12 – 11 – 10 – 7 – 6 – 5 – 4 – 3 – 2 – 1. (Lưu ý rằng các mảnh giấy ví dụ như số 8 sẽ không nằm trong hộp vì đã được loại bỏ ở các bước trước do không thuộc đường đi). 

3. Thuật toán Breadth-First-Search (BFS):

Thuật toán BFS là viết tắt của Breadth-First Search, có nghĩa là tìm kiếm theo chiều rộng. Khi thực hiện thuật toán này chúng ta sẽ sử dụng cấu trúc dữ liệu hàng đợi (queue) đã được học ở trong bài 6. Ý tưởng là chúng ta sẽ duyệt tất cả các nhánh để xem nhánh nào có lối ra thì dừng lại.

Để hiểu rõ hơn thuật toán này chúng ta sẽ cùng quay lại ví dụ của bạn Trẩu ở phần 2. Ở phần này, chúng ta sẽ minh hoạ cấu trúc dữ liệu hàng đợi là một chiếc thước kẻ với các phần tử bên trong là các mẩu giấy có đánh số được dán lên thước kẻ.

 Các bước của thuật toán BFS sẽ như sau:

• Bước 1: Đến điểm xuất phát và đánh dấu điểm xuất phát.
• Bước 2: Đánh dấu các ô xung quanh có thể đi được. (Lưu ý rằng không dùng các số trùng nhau)
• Bước 3: Ghi số của các ô xung quanh vào mẩu giấy, rồi dán chúng lên thước kẻ theo chiều từ trái qua phải.
• Bước 4: Lấy một mẩu giấy bên trái ngoài cùng ghi trên thước kẻ, đi đến ô ghi trên mẩu giấy. Quay lại bước 2. 

Đầu tiên chúng ta sẽ bắt đầu và đánh số 1 ở vị trí đầu tiên, lúc này thước kẻ vẫn trống chưa có mảnh giấy nào được dán lên:

Sau đó thực hiện bước 2 và bước 3, đánh dấu các ô xung quanh có thể đi được từ vị trí đang đứng và dán các mẩu giấy có ghi số các ô xung quanh lên trên thước kẻ:

Thực hiện bước 4, chúng ta lấy mẩu giấy bên trái ngoài cùng có ghi số 2 trên thước kẻ và bạn Trẩu di chuyển đến vị trí 2 có ghi trên mẩu giấy:

Tiếp tục quay lại thực hiện bước 2 và bước 3, ở vị trí hiện tại bạn Trẩu có hai lựa chọn ở xung quanh có thể đi được, đánh số các ô đó tương ứng với số 3 và 4 và dán các mẩu giấy lên trên thước kẻ:

Thực hiện bước 4 chúng ta lấy ra mẩu giấy bên trái ngoài cùng của thước kẻ là mẩu giấy có chứa số 3 và di chuyển bạn Trẩu đến vị trí số 3:

Quay lại thực hiện bước 2 và bước 3, bạn Trẩu có một lựa chọn bên phải có thể đi được, đánh số vị trí này là 5 và dán mẩu giấy lên trên thước kẻ:

Thực hiện bước 4 chúng ta lấy ra mẩu giấy bên trái ngoài cùng của thước kẻ là mẩu giấy có chứa số 4 và di chuyển bạn Trẩu đến vị trí số 4:

Tiếp tục thực hiện các bước của thuật toán và tada, cuối cùng bạn Trẩu sẽ đến được vị trí đích với các số được đánh dấu trên mê cung như sau:

Để đi lại về vị trí ban đầu, bạn Trẩu của chúng ta chỉ cần đi ngược lại theo các ô có số nhỏ hơn là được (nếu có từ 2 ô số nhỏ hơn, chọn ô có số nhỏ nhất): 13 – 12 – 11 – 9 – 7 – 5 – 3 – 2 – 1. Mảnh giấy ở bên trái trên thước kẻ sẽ được thực hiện trước trong queue (First In First Out – FIFO).

4. So sánh DFS và BFS:

Wow, như vậy là chúng ta đã giúp bạn Trẩu tìm đường di chuyển ra khỏi mê cung bằng hai thuật toán DFS và BFS, thật là ảo diệu phải không các bạn? Để kết thúc blog này, chúng ta sẽ cùng điểm qua một vài sự khác biệt giữa hai thuật toán này nhé:

DFS	BFS
Tìm theo một nhánh đến khi gặp đường cụt hoặc đích Dùng hộp giấy (ngăn xếp) Cả con người và máy tính có thể thực hiện Đường đi tìm được có thể không phải là ngắn nhất	Tìm cùng lúc nhiều nhánh Dùng thước kẻ (hàng đợi) Chỉ áp dụng hợp lý với máy tính Đường đi tìm được luôn là đường đi ngắn nhất

— — —

STEAM for Vietnam Foundation là tổ chức phi lợi nhuận 501(c)(3) được thành lập tại Hoa Kỳ với sứ mệnh thúc đẩy các hoạt động liên quan tới giáo dục STEAM (Science — Khoa học, Technology — Công nghệ, Engineering — Kỹ thuật, Arts — Nghệ thuật, Mathematics — Toán học) tại Việt nam. STEAM for Vietnam được thành lập và vận hành bởi đội ngũ tình nguyện viên là du học sinh và chuyên gia người Việt trên khắp thế giới.

— — —

📧Email: hello@steamforvietnam.org

🌐Website: www.steamforvietnam.org

🌐Fanpage: STEAM for Vietnam

📺YouTube:  http://bit.ly/S4V_YT

🌐Zalo: Zalo Official

📍Donation: https://www.steamforvietnam.org/donation