(43) Back-tracking algorithm: Thuật toán quay lui. Phần 1 – Bùi Thế Tâm

backtrack là gì Đang rất được mọi người quan tâm và chú ý đến thuthuat.net Là kênh chuyên chia sẻ về bản tin của máy tính, công nghệ, cũng như chia sẻ các thủ thuật tiện ích hữu ích cho người dùng. Hôm nay , thuthuat.net Sẽ giới thiệu đến các bạn (43) Back-tracking algorithm: Thuật toán quay lui. Phần 1 – Bùi Thế Tâm. Vui lòng xem kĩ hướng dẫn tại video bên dưới bên dưới :

Các tập hợp hữu hạn (Finite Set): Duyệt tất cả các hoán vị của tập n phần tử
Bùi Thế Tâm – Hanoi, Vietnam
Để giải quyết một Bài toán đặt ra ta cần xây dựng các bộ giá trị (x(1), x(2), . . ., x(n)). Giả sử đã xác định được k-1 thành phần đầu tiên (x(1), x(2), . . ., x(k-1)), bây giờ ta cần xác định x(k) bằng cách duyệt tất cả các khả năng mà x(k) có thể nhận giá trị, đánh số các khả năng từ 1 đến s(k). Với mỗi khả năng j ta kiểm tra xem nó có chấp nhận được hay không, hai trường hợp xảy ra:
– Nếu chấp nhận khả năng j thì xác định x(k) theo j, sau đó nếu k = n thì ta được một bộ giá trị (x(1), x(2), . . ., x(n)) và ta có thể xử lý tiếp bộ giá trị này theo yêu cầu của Bài toán, nếu k nhỏ hơn n thì ta lại tiến hành xác định tiếp x(k+1).
– Nếu thử tất cả các khả năng của x(k) mà không có khả năng nào được chấp nhận thì quay lại bước trước để xác đinh
x(k-1) theo khả năng tiếp theo của x(k-1).
Thuật toán quay lui rất phù hợp với những phép gọi đệ qui trong các ngôn ngữ lập trình. Thuật toán quay lui xác định thành phần thứ k có thể được mô tả bằng thủ tục Try(k)
Điểm quan trọng nhất của thuật toán là cần đưa ra danh sách các khả năng mà x(k) có thể nhận giá trị, xác định giá trị của biểu thức logic (chấp nhận j). Giá trị này ngoài việc phụ thuộc j còn phụ thuộc vào việc đã chọn các khả năng tại k-1 bước trước. Vì thế cần ghi nhớ trạng thái mới của quá trình tìm kiếm sau khi (xác định x(k) theo j) và trả lại trạng thái cũ sau lời gọi Try(k + 1). Chiến lược quay lui tương tự với tìm kiếm theo chiều sâu trên cây. Ưu điểm: chương trình ngắn gọn, ứng dụng để giải nhiều bài toán. Nhược điểm: lợi dụng hàm đệ quy trong ngôn ngữ lập trình (hàm gọi cuối cùng sẽ thoát ra đầu tiên cùng với việc xóa các biến tự động) do đó việc gỡ rối chương trình là rất khó khi bị lỗi.
Bài toán 1. Duyệt tất cả các hoán vị của tập ( 1, 2, 3, … , n )
Một hoán vị được biểu diễn dưới dạng ( p(1), p(2), …. , p(n) ), trong đó p(i) nhận giá trị từ 1 đến n và p(i) khác p(j) với i khác j. Thành phần p(k) có khả năng nhận giá trị từ 1 đến n, trong đó giá trị j được dùng nếu nó chưa được dùng. Vì thế phải ghi nhớ với mỗi j nó được dùng hay chưa. Điều này được thực hiện nhờ mảng logic b, lúc đầu các b(j) đều gán bằng 1 (chưa được dùng). Mỗi lần gán p(k) = j ta cần cho b(j) = 0. Mỗi lần ghi lại trạng thái mới hay gọi hàm đệ quy HoanVi(k+1) ta cũng phải gán lại b(j) = 1 để trả lại trạng thái cũ.
HỌC TIN HỌC ONLINE MIỄN PHÍ
Dạy lập trình ngôn ngữ C – Back-tracking algorithm – Bùi Thế Tâm | Ngôn ngữ lập trình C
Bài giảng về lập trình C, tin học văn phòng, word, excel, powerpoint, thuật toán
Kênh Yotube chính thức của Bùi Thế Tâm.
Youtube: https://www.youtube.com/channel/UCKis…
Bùi Thế Tâm là kênh đào tạo về lĩnh vực công nghệ thông tin, Lập trình ngôn ngữ C, tin học văn phòng, các thuật toán toán tối ưu và lập trình trên C, hướng dẫn sử dụng Microsoft office 2007, 2010, 2013.
Kênh Bùi Thế Tâm hướng dẫn sử dụng word, excel, powerpoint, lập trình ngôn ngữ C cho người mới bắt đầu, cho học sinh, sinh viên, sinh viên năm thứ nhất, sinh viên năm thứ hai, cho học sinh, giáo viên vùng sâu vùng xa, người cao tuổi muốn học tin học ở nhà, các bạn thi viên chức và người đi làm…
Với nhiều năm kinh nghiệm giảng dậy và viết sách nên các bài giảng trong kênh Bùi Thế Tâm rất dễ hiểu, đơn giản, chính xác và đầy đủ.
Trong bài giảng phần lý thuyết, bài tập xen kẽ nhau, với nhiều dạng bài tập từ dễ đến khó có hướng dẫn giải chi tiết cẩn thận giúp các bạn có thể nắm vững được kiến thức.
Facebook: https://www.facebook.com/buitamhh
Twitter: https://twitter.com/buitam23
Blog: http://buithetamblog.blogspot.com/
Youtube: http://goo.gl/3sqLFE
Hãy like và chia sẻ cho bạn bè và những người bạn quen đang muốn học về Microsoft office, tin học văn phòng ( hay còn gọi là tin học cơ sở, tin học đại cương, tin học căn bản, tin học phổ thông, tin học cho người mới bắt đầu), ngôn ngữ lập trình C.
Mọi hình thức copy và sao chép đều vi phạm bản quyền của youtube nếu không được sự đồng ý của tác giả Bùi Thế Tâm
Đừng quên đăng ký kênh để học thêm các bài mới
Subscribe Youtube: http://goo.gl/3sqLFE

backtrack là gì-0
backtrack là gì-0
backtrack là gì-1
backtrack là gì-1
backtrack là gì-2
backtrack là gì-2
backtrack là gì-3
backtrack là gì-3
backtrack là gì-4
backtrack là gì-4
backtrack là gì-5
backtrack là gì-5
backtrack là gì-6
backtrack là gì-6
backtrack là gì-7
backtrack là gì-7
backtrack là gì-8
backtrack là gì-8
backtrack là gì-9
backtrack là gì-9

Cảm ơn mọi người đã theo dõi chủ đề (43) Back-tracking algorithm: Thuật toán quay lui. Phần 1 – Bùi Thế Tâm. Tất cả thông tin mà thuthuat.net cung cấp đều rất có ích. Đội ngũ của chúng tôi hi vọng sẽ cung cấp được nhiều giá trị hơn nữa. Nếu còn gì thắc mắc hãy comment xuống phía dưới, chúng tôi sẽ giúp đỡ bạn

Viết một bình luận