Trong quá trình làm case study thì mình có gặp vấn đề liên quan đến một thuật toán hay ho là trace path, blog này mình sẽ nói về trace path
Trace path là gì?
Trace path là thuật toán dùng để xử lí bài toán cụ thể sau: Trên một mặt phẳng toạ độ Oxy (Ở đây mình chỉ nói đến bối cảnh 2D) có 2 điểm A và B với toạ độ (Ax,Ay) và (Bx,By), hãy tìm con đường đi từ điểm A đến điểm B, hãy nhớ là A chỉ có 4 hướng di chuyển, mỗi lần chi chuyển chỉ được 1 ô và sẽ có những vật cản.
Ý tưởng thuật toán
Điểm A sẽ di chuyển theo cả 4 hướng để tìm đường, với mỗi lần di chuyển thì sẽ kiểm tra đã đến B chưa, nếu đến B rồi thì dừng lại và in ra con đường đi từ A đến B, có thể là một mảng các toạ độ hoặc một mảng 2 chiều với các điểm A đã đi qua được đánh dấu, nếu chưa thì lại tiếp tục di chuyển theo 4 hướng.
Khi di chuyển thì điểm đã đi qua sẽ không đi lại nữa, gặp vật cản sẽ không di chuyển vào đấy.
Triển khai thuật toán bằng Javascript
Ở đây mình sẽ triển khai thuật toán tìm đường bằng Javascript, với yêu cầu bài toán cụ thể như sau: Cho một mảng array2D, hãy in ra các con đường để đi từ điểm A đến điểm B trong array2D
Viết trace path và chạy, link git toàn bộ mình để ở dưới cùng nhé!
Kết quả như sau
Cải tiến thuật toán
Bạn có thể dễ dàng nhận ra là các hướng di chuyển đang được để mặc định là xuống, trái, phải, lên, vậy nên quá trình dò đường sẽ mất thời gian hơn, và đặc biệt là với mảng còn nhỏ là 4×4, nếu size mảng lớn hoặc vô cùng thì việc tìm đường gần như không thể thực hiện được hoặc mất rất nhiều thời gian.
Ở đây mình sẽ để một phương án khá hay, mình gọi là better direction, tức là từ việc so sánh Ax với Bx, Ay với By mà sẽ đưa ra các phương án theo thứ tự thích hợp hơn, ví dụ khi B ở dưới A thì sẽ ưu tiên A đi xuống dưới trước rồi mới đi theo các hướng còn lại, tương tự như thế nếu A ở bên trái của B.
Thuật toán mình đã đặt trên git: https://github.com/KyPT2503/Algorithm_TracePath.git
