Lý thuyết về thuật toán quay lui Back Track

Lý thuyết về 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ù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.

Thuật toán quay lui (Back Track)

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:

Thuật toán quay lui (Back Track)

Bạn thấy bài viết này như thế nào?: 
Average: 10 (3 votes)
Ảnh của Tommy Tran

Tommy owner Express Magazine

Drupal Developer having 9+ year experience, implementation and having strong knowledge of technical specifications, workflow development. Ability to perform effectively and efficiently in team and individually. Always enthusiastic and interseted to study new technologies

  • Skype ID: tthanhthuy

Advertisement

 

jobsora

Dich vu khu trung tphcm

Dich vu diet chuot tphcm

Dich vu diet con trung

Quảng Cáo Bài Viết

 
Buổi hội thảo Managing Multiple Drupal Sites diễn ra tại Zurich tháng 6.2019

Buổi hội thảo Managing Multiple Drupal Sites diễn ra tại Zurich tháng 6.2019

In this webinar, amazee.io CTO, Michael Schmid (@Schnitzel) will walk us through the setup and workflow forward-thinking organizations rely on to efficiently run their multitude of business-critical websites.

A Roadmap for Success: The Design Brief

Lộ trình thành công: The Design Brief

Described succinctly by Tad Crawford in AIGA Professional Practices in Graphic Design, the design brief “digs deep into a project and identifies the main factors that drive the entire creative strategy.”

Ngành công nghệ thông tin không còn tính hấp dẫn?

Ngành công nghệ thông tin không còn tính hấp dẫn?

Tuyển sinh CNTT gần đây gặp nhiều khó khăn, cho thấy ngành CNTT giờ không còn hấp dẫn thí sinh như trước nữa…

Công ty diệt chuột T&C

 

Diet con trung