Tìm hiểu thuật toán loang

Tư tưởng của thuật toán loang thật ra cũng rất đơn giản. Hãy tưởng tượng có một nàng công chúa bị bắt giam vào 1 mê cung, nàng bí quá, lôi ĐTDĐ ra fone cho hoàng tử. Hoàng tử tức tốc dẫn theo một đạo quân (giả sử rằng số quân của chàng ta là ko giới hạn). Khi đến cổng vào mê cung, chàng may mắn gặp một "bậc thánh nhân", người cho chàng biết rằng công chúa đang bị giam trong phòng [X,Y] nào đó. À, bây giờ trong đầu chàng nghĩ đến 2 hướng sau:
  • Chàng quyết định solo đi vào mê cung, dĩ nhiên trên tay cầm 1 cuộn chỉ. Khi vào cổng, chàng bắt gặp T căn phòng, chàng sẽ đi vào từng phòng một, bước vào T1, chàng lại gặp T2 cửa, ... , cứ thế đến khi ko có đường đi, chàng sẽ lần ngược theo đường chỉ, đánh dấu vào cánh cửa chàng đã đi rồi, và chọn 1 cửa khác. Với cách này, chàng sẽ tìm được phòng có công chúa, dĩ nhiên, nếu chàng ko gục ở giữa đường.
  • Tận dụng nguồn binh lực hùng hậu của mình, chàng ra hiệu lệnh "Toàn lực lục soát". Đi vào mê cung, bắt gặp T căn phòng, chàng chia đoàn binh thành T đạo, cứ thế. Dĩ nhiên, mỗi binh sĩ đều đc trang bị phương tiện liên lạc để khi tìm thấy công chúa sẽ phát hiệu lệnh "Rút lui". Vậy, với cách này ta sẽ tìm được công chúa với quãng đường đi từ cửa mê cung đến phòng giam là ngắn nhất. Nhưng, nảy sinh một bất cập là, nếu binh sĩ tìm được công chúa rồi, thì làm sao lần ra lại cửa mê cung đây??? Đương nhiên hoàng tử ko thể chấp nhận chuyện để người yêu mình chung phòng với một đám binh sĩ ~~. Chàng ra lệnh rằng, trước khi vào mỗi cửa, phải dùng kiếm vạch mũi tên xuống đất, mũi tên này sẽ hướng đến cửa các binh sĩ đã đi vào trước khi gặp căn phòng. Ví dụ khi vào cổng mê cung, 1 tốp binh sĩ đi vào cửa T1, gặp N2 cửa khác, chia binh lực ra, với mỗi cửa T2, các binh sĩ sẽ vạch mũi tên hướng về cửa T1, tức cửa đã dẫn họ tới N2 căn phòng. Nhờ đó họ sẽ lần được đường thoát khỏi mê cung.

Từ đây, ta sẽ hình thành 2 phương pháp tìm đường đi, trong bài viết này, chúng ta sẽ tìm hiểu cách thứ hai, mà theo cách gọi thông thường là LOANG: Từ một vị trí có tọa độ A(x,y) cho sẵn, bạn buộc phải tìm đến một vị trí B(x’,y’) sao cho quảng đường đi là ít nhất có thể và in ra đường đi từ A đến B đó.

(Tham khảo)

Không có nhận xét nào:

Đăng nhận xét