Giới thiệu về series Di chuyển trên mặt phẳng 2D:

Sau Quy hoạch động, mình sẽ tập trung vào giới thiệu nhiều bài tập hay về Di chuyển trên mặt phẳng 2D. Đây là series mình yêu thích, nó cũng không kém phần thử thách so với Quy hoạch động, mà ứng dụng nó khắp nơi, rất gần gũi với đời sống hàng ngày.

Vì sao lớp bài này khó nhưng hay ?

Thứ nhất, di chuyển trên một đường thẳng 1D có khá ít trường hợp phải đi, thế nên các vòng lặp, các thủ thuật (hai con trỏ, dãy tạm,…), các bảng băm… có thể dễ dàng cho ta ra lời giải. Trong khi đó, khi số chiều tăng lên, không gian sẽ trở nên “rỗng” ra, có nhiều khoảng không hơn, số lượng duyệt tăng lên gấp nhiều lần, số cách đi (và đi trùng) cũng sẽ tăng lên một cách khủng khiếp (bạn cứ thử tưởng tượng một chấm nhỏ đi ngẫu nhiên trong không gian 3D để tìm đích !). Thế nên, ứng với không gian này, nó là một thử thách lớn về kỹ năng cho lập trình viên. Nó là loại không gian để giúp phân biệt level và sự tự tin của mỗi lập trình viên. Trên không gian này, không phải cách duyệt nào cũng tốt, mà phải ưu tiên cách duyệt có phương pháp hoặc có heuristics tốt.

Thứ hai, thế giới chúng ta đang sống là 3 chiều, nhưng hầu như mọi ứng dụng đi lại (của người hay robot), xây dựng, bản đồ… đều có thể được mô hình hóa và thể hiện trên không gian 2 chiều. Chỉ cần làm tốt 2D, chúng ta đã có thể giải quyết được rất nhiều vấn đề trên thực tế và xây dựng được nhiều ứng dụng hay.

Vấn đề trên 2D tựu chung có thể chia làm hai lớp bài: Đếm và Dùng ít nhất, nhưng các yêu cầu cụ thể của từng vấn đề ngoài đời sống thì lại vô cùng đa dạng…

Với phương pháp Quy hoạch động, mình đã trình bày 2 dạng bài tập: Đếm số cách di chuyển, và Dùng ít nhất chi phí để đi đến hai điểm đã biết (từ A đến B).

Trong các videos tiếp theo, mình sẽ giới thiệu các dạng bản đồ phức tạp hơn, các bài đếm thú vị hơn (số cách di chuyển), các loại khoảng cách và di chuyển chỉ biết đầu mà chưa biết cuối (nhưng cũng vẫn phải tìm chúng ra),…

——————————————————————————————————————-
Giới thiệu về videos này:

Có 3 phương pháp thông dụng giúp giải quyết nhiều bài Di chuyển trên mặt phẳng 2D là: Quy hoạch động, DFS, BFS.

Tuy nhiên, nhiều bạn sẽ lúng túng khi nào ta có thể sử dụng phương pháp này (Quy hoạch động) mà không phải phương pháp kia (BFS, DFS) ? Có bài tập nào có thể sử dụng nhiều phương pháp cùng lúc được không (cả DFS và BFS), tại sao ? Lại có trường hợp, ta chỉ có thể sử dụng được BFS mà không thể sử dụng DFS, tại sao ?

Tất cả những câu hỏi này đều chính đáng, đều cấu thành chung sự am hiểu thuật toán để khiến góc nhìn giải thuật của chúng ta càng sắc bén hơn. Những lời giải thích cho 3 câu hỏi này đều cần phải có sẵn, có trước trong nhận thức của mỗi lập trình viên để có thể giải hiệu quả và không lúng túng khi gặp các bài trên mặt phẳng 2D.
Video này mình sẽ trả lời 2 câu hỏi đầu. Các video tiếp theo mình sẽ trả lời câu hỏi sau cùng, cũng rất quan trọng.

Cùng xem nhé.

Nguồn: https://maturegamerpodcast.com/

Xem thêm bài viết khác: https://maturegamerpodcast.com/category/giao-duc

admin

4 thoughts on “Tìm kiếm theo [chiều sâu / chiều rộng] và Mảng duyệt – Đếm đảo”

  1. cảm ơn vì sự nhiệt tình truyền đạt lại kiến thức cho những người đam mê thuật toán như e ạ <3

Leave a Reply

Your email address will not be published. Required fields are marked *