01/10/2018, 10:11
Xin ý tưởng giái thuật tìm đường dài nhất trong ma trận 2 chiều
Chào mọi người, như tiêu đề mọi người cho e xin ý tưởng giải bài. E xin nói cụ thể bài toán thế này ạ
Cho 1 ma trận M x N. Tìm 1 đường gấp khúc bắt đầu từ hàng 1 và kết thúc tại hàng cuối cùng sao cho tổng các phần tử mà đường đi qua là lớn nhất và đi theo quy tắc sau:
- Từ ô ở hàng trên chỉ đi thẳng đứng xuống dưới, hoặc chéo sang trái 1 ô hoặc chéo sang phải 1 ô.
Cụ thể, chẳng hạn đang ở ô [x, y] thì được đi xuống ô [x+1,y] hoặc [x+1,y+1] hoặc [x+1,y-1].
Bác nào biết xin chỉ giáo
E xin cảm ơn trước
Bài liên quan
Bài này QHĐ cơ bản mà bạn, vì để max 1 ô thì bạn phải max hết những ô dẫn đến nó đã.
Cho chạy thử tất cả các trường hợp, cái nào dài nhất thì trả về.
A nói cụ thể giúp e được không ạ?
Nếu làm vậy với những bài có M, N lớn sẽ không làm được và nó cũng k phải giải thuật nữa ạ
Để giải bài bằng QHĐ thì bài toán phải có thể chia nhỏ và lời giải của bài toán lớn là sự kết hợp lời giải (tối ưu) của những bài toán con. Có hai dạng là tổ hợp (combinatoric) và tối ưu.
Có thể thấy để đi đến ô nào đó, ví dụ như ô (3, 2) thì chỉ có thể đi từ 3 ô xuống: (2, 1); (2, 2); (2, 3). Vậy vấn đề trở thành tìm đường đến những ô này dài nhất.
Ok r ạ, e cám ơn a!
…
Bạn có thể thấy là với mỗi ô A chỉ có tối đa 3 cách để đi ô tiếp theo. Như vậy độ phức tạp của thuật toán nhỏ hơn O(m x n^3), chỉ là bậc 4 thôi mà :))
Nhưng QHĐ là O(m*n) nhé và chỉ cần lưu 2 dòng.
Ô :))
vi.wikipedia.org
Quy hoạch động
Trong ngành khoa học máy tính, quy hoạch động là một phương pháp giảm thời gian chạy của các thuật toán thể hiện các tính chất của các bài toán con gối nhau (overlapping subproblem) và cấu trúc con tối ưu (optimal substructure). Nhà toán học Richard Bellman đã phát minh phương pháp quy hoạch động vào năm 1953. Ngành này đã được thành lập như là một chủ đề về kỹ nghệ và phân tích hệ thống đã được tổ chức IEEE thừa nhận. Cấu trúc con tối ưu có nghĩa là các lời giải tối ưu cho các bài toán con có ...