Thuật toán quay lui (Back Tracking)

<p style="text-align: justify;">Một thuật to&aacute;n quay lui sẽ cố gắng x&acirc;y dựng giải ph&aacute;p cho một vấn đề theo từng bước. Bất cứ khi n&agrave;o thuật to&aacute;n cần quyết định giữa nhiều lựa chọn kh&aacute;c nhau cho th&agrave;nh phần tiếp theo của giải ph&aacute;p, n&oacute; sẽ thử tất cả c&aacute;c t&ugrave;y chọn c&oacute; thể c&oacute; bằng kỹ thuật đệ quy. Trong b&agrave;i viết n&agrave;y, ta sẽ c&ugrave;ng t&igrave;m hiểu về thuật to&aacute;n quay lui bằng c&aacute;ch h&igrave;nh ảnh v&iacute; dụ minh họa.</p> <h2 id="ftoc-heading-1" class="ftwp-heading" style="text-align: justify;">1. Kh&aacute;i niệm</h2> <p style="text-align: justify;">Thuật to&aacute;n Backtracking hay quay lui l&agrave; một thuật to&aacute;n giải quyết vấn đề bằng c&aacute;ch sử dụng c&aacute;ch tiếp cận Brute Force để t&igrave;m đầu ra mong muốn. Phương ph&aacute;p Brute force sẽ thử tất cả c&aacute;c giải ph&aacute;p c&oacute; thể v&agrave; chọn c&aacute;c giải ph&aacute;p mong muốn hoặc tốt nhất.</p> <p style="text-align: justify;">Thuật ngữ quay lui c&oacute; nghĩa l&agrave; nếu giải ph&aacute;p hiện tại kh&ocirc;ng ph&ugrave; hợp, ta sẽ quay trở lại v&agrave; thử c&aacute;c giải ph&aacute;p kh&aacute;c. Do đ&oacute;, kỹ thuật đệ quy được sử dụng trong c&aacute;ch tiếp cận n&agrave;y.</p> <p style="text-align: justify;">C&aacute;ch tiếp cận n&agrave;y được sử dụng để giải quyết c&aacute;c vấn đề c&oacute; nhiều giải ph&aacute;p. C&ograve;n nếu ta muốn c&oacute; một giải ph&aacute;p tối ưu, ta n&ecirc;n sử dụng kỹ thuật quy hoạch động.</p> <p style="text-align: justify;">Đoạn giả m&atilde; cho thuật to&aacute;n quay lui như sau:</p> <pre class="language-cpp"><code>H&agrave;m quay lui(x) Nếu x kh&ocirc;ng phải l&agrave; giải ph&aacute;p Trả về false Nếu x l&agrave; một giải ph&aacute;p mới Th&ecirc;m v&agrave;o danh s&aacute;ch c&aacute;c giải ph&aacute;p H&agrave;m quay lui(mở rộng/ triển khai th&ecirc;m cho x)</code></pre> <h2 id="ftoc-heading-2" class="ftwp-heading">2. C&acirc;y trạng th&aacute;i</h2> <p style="text-align: justify;">C&acirc;y trạng th&aacute;i l&agrave; c&acirc;y biễu diễn cho tất cả c&aacute;c trạng th&aacute;i c&oacute; thể c&oacute; (giải ph&aacute;p hoặc kh&ocirc;ng phải giải ph&aacute;p) của b&agrave;i to&aacute;n v&agrave; từ n&uacute;t gốc l&agrave; trạng th&aacute;i ban đầu đến n&uacute;t l&aacute; l&agrave; trạng th&aacute;i cuối c&ugrave;ng.</p> <p><img style="width: 100%;" src="../../../public_files/6fda14a0-f550-4888-a31d-201f12c45658" alt="thuat-toan-quay-lui" /></p> <h2 id="ftoc-heading-3" class="ftwp-heading" style="text-align: justify;">3. V&iacute; dụ về thuật to&aacute;n quay lui</h2> <p style="text-align: justify;">B&agrave;i to&aacute;n đặt ra l&agrave;: Ta muốn t&igrave;m tất cả c&aacute;c c&aacute;ch c&oacute; thể để xếp 2 nam v&agrave; 1 nữ tr&ecirc;n 3 chiếc ghế d&agrave;i.</p> <p style="text-align: justify;">R&agrave;ng buộc: Bạn nữ kh&ocirc;ng thể ngồi tr&ecirc;n ghế giữa.</p> <p style="text-align: justify;">B&agrave;i giải: C&oacute; tổng l&agrave; 3! = 6 khả năng. Ch&uacute;ng ta sẽ thử tất cả c&aacute;c khả năng v&agrave; c&oacute; được c&aacute;c giải ph&aacute;p khả thi. Ch&uacute;ng ta thử kỹ thuật đệ quy cho tất cả c&aacute;c khả năng.</p> <p style="text-align: justify;">Tất cả c&aacute;c khả năng được minh họa trong h&igrave;nh b&ecirc;n dưới bao gồm như sau:</p> <p><img style="width: 100%;" src="../../../public_files/d970c702-6b00-4ca2-81c8-ae234130e042" alt="thuat-toan-quay-lui-2" /></p> <ul> <li>C&acirc;y kh&ocirc;ng gian trạng th&aacute;i sau đ&acirc;y sẽ đưa ra c&aacute;c giải ph&aacute;p khả thi.</li> </ul> <p><img style="width: 100%;" src="../../../public_files/03aa213b-2122-49e4-8be1-a3ad05a2d03c" alt="thuat-toan-quay-lui-3" /></p> <p style="text-align: justify;">V&igrave; với r&agrave;ng buộc l&agrave; bạn nữ kh&ocirc;ng được ngồi ở giữa, do đ&oacute;, c&aacute;c giải ph&aacute;p để nữ c&oacute; thể ngồi ở giữa sẽ kh&ocirc;ng phải l&agrave; lời giải cho b&agrave;i to&aacute;n n&agrave;y. Do vậy, ta sẽ loại bỏ đi c&aacute;c giải ph&aacute;p m&agrave; trong đ&oacute; nữ ngồi ở giữa, trong h&igrave;nh tr&ecirc;n, ta sẽ đ&aacute;nh dấu X m&agrave;u đỏ cho tất cả c&aacute;c giải ph&aacute;p như vậy (chỉ c&oacute; 2 giải ph&aacute;p l&agrave; nữ ngồi ở giữa), v&agrave; thực hiện đ&aacute;nh dấu t&iacute;ch xanh cho tất cả c&aacute;c giải ph&aacute;p c&ograve;n lại cho b&agrave;i to&aacute;n.</p> <p style="text-align: justify;">&Yacute; tưởng ch&iacute;nh của b&agrave;i to&aacute;n đ&oacute; l&agrave; l&agrave; ch&uacute;ng ta c&oacute; thể x&acirc;y dựng một giải ph&aacute;p theo từng bước bằng c&aacute;ch sử dụng kỹ thuật đệ quy. Nếu trong suốt qu&aacute; tr&igrave;nh thực hiện, ch&uacute;ng ta nhận thấy đ&oacute; kh&ocirc;ng phải l&agrave; một giải ph&aacute;p hợp lệ, th&igrave; ch&uacute;ng ta ngừng việc t&iacute;nh to&aacute;n cho giải ph&aacute;p đ&oacute; v&agrave; ch&uacute;ng ta sẽ quay lại bước trước đ&oacute; (quay lui lại). Trong trường hợp b&agrave;i to&aacute;n về sắp xếp chỗ ngồi như tr&ecirc;n, khi ch&uacute;ng ta t&iacute;nh to&aacute;n rằng cho ph&eacute;p nữ ngồi ở giữa (điều kiện kh&ocirc;ng được ph&eacute;p), ch&uacute;ng ta buộc phải quay lui lại (kh&ocirc;ng t&iacute;nh tiếp nữa), nhưng cũng c&oacute; một số trường hợp kh&aacute;c m&agrave; ch&uacute;ng ta c&oacute; thể nhận ra rằng ch&uacute;ng ta đang hướng đến một giải ph&aacute;p kh&ocirc;ng hợp lệ (hoặc kh&ocirc;ng tốt) trước khi đạt được n&oacute;.</p> <h2 id="ftoc-heading-4" class="ftwp-heading" style="text-align: justify;">4. Ứng dụng của thuật to&aacute;n quay lui</h2> <ul style="text-align: justify;"> <li>Để t&igrave;m tất cả c&aacute;c đường đi Hamilton c&oacute; trong biểu đồ.</li> <li>Để giải quyết b&agrave;i to&aacute;n về N Queen.</li> <li>Giải quyết về b&agrave;i to&aacute;n trong việc t&igrave;m đường đi trong m&ecirc; cung cho r&ocirc;-bốt.</li> <li>Giải quyết b&agrave;i to&agrave;n cho t&igrave;m đường đi của qu&acirc;n kỵ sĩ tr&ecirc;n b&agrave;n cờ vua.</li> </ul> <p style="text-align: justify;">Tr&ecirc;n đ&acirc;y l&agrave; kh&aacute;i niệm v&agrave; v&iacute; dụ cơ bản về thuật to&aacute;n quay lui. Hy vọng mọi người c&oacute; thể &aacute;p dụng v&agrave;o trong chương tr&igrave;nh của m&igrave;nh. Nếu mọi người c&oacute; đ&oacute;ng g&oacute;p g&igrave; th&ecirc;m th&igrave; c&oacute; thể để c&aacute;c b&igrave;nh luận b&ecirc;n dưới b&agrave;i viết n&agrave;y. Mọi người h&atilde;y tiếp tục theo d&otilde;i c&aacute;c b&agrave;i tiếp theo v&agrave; cập nhật c&aacute;c b&agrave;i mới nhất tr&ecirc;n&nbsp;<a href="../../../">tek4</a>&nbsp;nh&eacute;!</p>