[Thuật Toán] Thuật Toán Quay Lui (Back Track) - Simple Code C Java

Có thể bạn quan tâm

Skip to content Simple Code C Java back track. Thuật toán [Thuật toán] Thuật toán quay lui (Back Track)

Saturday, October 24, 2015

Phương pháp sinh kế tiếp có thể giải quyết được các bài toán liệt kê khi ta nhận biết được cấu hình đầu tiên & cấu hình cuối cùng của bài toán. Tuy nhiên, không phải cấu hình sinh kế tiếp nào cũng được sinh một cách đơn giản từ cấu hình hiện tại, ngay kể cả việc phát hiện cấu hình ban đầu cũng không phải dễ tìm vì nhiều khi chúng ta phải chứng minh sự tồn tại của cấu hình. Do vậy, thuật toán sinh kế tiếp chỉ giải quyết được những bài toán liệt kê đơn giản. Để giải quyết những bài toán tổhợp phức tạp, người ta thường dùng thuật toán quay lui (Back Track) sẽ được trình bày dưới đây. Nội dung chính của thuật toán này là xây dựng dần các thành phần của cấu hình bằng cách thử tất cả các khả năng. Giả sử cần phải tìm một cấu hình của bài toán x = (x1, x2,.., xn) mà i-1 thành phần x1, x2,.., xi-1 đã được xác định, bây giờ ta xác định thành phần thứ i của cấu hình bằng cách duyệt tất cả các khả năng có thể có và đánh số các khả năng từ 1..ni. Với mỗi khả năng j, kiểm tra xem j có chấp nhận được hay không. Khi đó có thể xảy ra hai trường hợp:

Nếu chấp nhận j thì xác định xi theo j, nếu i=n thì ta được một cấu hình cần tìm, ngược lại xác định tiếp thành phần xi+1

Nếu thử tất cả các khả năng mà không có khả năng nào được chấp nhận thì quay lại bước trước đó để xác định lại xi-1

Điểm quan trọng nhất của thuật toán là phải ghi nhớ lại mỗi bước đã đi qua, những khả năng nào đã được thử để tránh sự trùng lặp. Để nhớ lại những bước duyệt trước đó, chương trình cần phải được tổ chức theo cơ chế ngăn xếp (Last in first out). Vì vậy, thuật toán quay lui rất phù hợp với những phép gọi đệ qui. Thuật toán quay lui xác định thành phần thứ i có thể được mô tả bằng thủ tục Try(i) như sau: void Try(int i) { int j; for (j = 1; j < ni; j++) { if (<Chấp nhận j >) { <Xác định xi theo j> if (i == n) < Ghi nhận cấu hình > ; else Try(i + 1); } } } Có thể mô tả quá trình tìm kiếm lời giải theo thuật toán quay lui bằng cây tìm kiếm lời giải sau:

Dưới đây là một số ví dụ sử dụng thuật toán quay lui.

Liệt kê các xâu nhị phân có độ dài n.
Liệt kê các tập con k của tập n phần tử.
Liệt kê các hoán vị của tập n phần tử.
Bài toán xếp hậu. Liệt kê tất cả các cách xếp n quân hậu trên bàn cờ n x n sao cho chúng không ăn được nhau.

Cám ơn bạn đã đọc bài viết này. Hãy chia sẻ bài viết và bình luận ý kiến của bạn ở bên dưới.

Chào mừng bạn đến với SimpleCodeCJava Blog - Mục đích của chúng tôi khi thành lập blog này là muốn chia sẻ những kiến thức và kinh nghiệm lập trình mà chúng tôi đã học được với mong muốn giúp đỡ mọi người, giúp bạn rút ngắn được thời gian tìm hiểu cũng như việc giải quyết những vấn đề trong lập trình C và Java.

Home

0 Comment to "[Thuật toán] Thuật toán quay lui (Back Track)"

Recent

Weekly

[Bài toán] Liệt kê tập con của tập n phần tử. Bài toán: Cho X = {1, 2,3,.., n}. Hãy liệt kê tất cả các tập con k phần tử của X (k<=n). Giải: Mỗi tập con của tập hợp X có thể biểu ...
[Thuật toán] Tìm đường đi và chu trình Hamilton. Để xem lý thuyết đồ thị với các định nghĩa về đường đi, chu trình, đồ thị liên thông bạn có thể xem ở đây . Với đồ thị Euler , chúng ta ...
[Thuật toán] Tìm kiếm theo chiều sâu DFS. Để xem lý thuyết đồ thị với các định nghĩa về đường đi, chu trình, đồ thị liên thông bạn có thể xem ở đây . Lý thuyết thuật toán tìm kiế...
[Thuật toán] Tìm đường đi và Chu trình Euler Để xem lý thuyết đồ thị với các định nghĩa về đường đi, chu trình, đồ thị liên thông bạn có thể xem ở đây . Định nghĩa : Chu trình đơn t...
[Thuật toán] Tìm đường đi giữa hai đỉnh của đồ thị. Bài toán: Cho đồ thị G=(V, E) . Trong đó V là tập đỉnh, E là tập cạnh của đồ thị. Hãy tìm đường đi từ đỉnh s ∈ V tới đỉnh t ∈ V . Thủ tục...
JSON Tutorial - Kiến thức căn bản về JSON. 1. JSON JSON là viết tắt của JavaScript Object Notation. JSON được sử dụng để truyền dữ liệu giữa Server và Client, XML cũng được sử dụng...
[Đồ thị] Lý thuyết đồ thị - Đường đi, Chu trình, Đồ thị liên thông Đồ thị : là một cấu trúc dữ liệu rời rạc bao gồm các đỉnh và các cạnh nối các cặp đỉnh này. Chúng ta phân biệt đồ thị thông qua kiểu và số...
[Thuật toán] Thuật toán quay lui (Back Track) Phương pháp sinh kế tiếp có thể giải quyết được các bài toán liệt kê khi ta nhận biết được cấu hình đầu tiên & cấu hình cuối cùn...
[Bài tập mẫu] Hàm trong C/C++ CÂU HỎI 1. Dòng đầu tiên của định nghĩa hàm gọi là gì, nó bao gồm các thông tin thế nào? 2. Hàm có thể trả về bao nhiêu gi...
[C/C++] Ép chữ thường thành chữ hoa trong C/C++ Chương trình sau dùng để chuyển đổi chữ thường thành chữ hoa. Logic của chương trình như sau: Tất cả các chữ cái thường (a đến z) có giá ...