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

 
Yahoo, Microsoft, AOL hợp sức chống Google và Facebook

Yahoo, Microsoft, AOL hợp sức chống Google và Facebook

Yahoo, Microsoft và AOL tuyên bố liên kết các mạng quảng cáo từ đầu năm 2012. Bước đi này được huy động nhằm cạnh tranh lại Facebook và Google đang bứt lên.

Apple phát triển TV điều khiển bằng giọng nói

Apple phát triển TV điều khiển bằng giọng nói

Theo các kênh thông tin hành lang, Apple đang lặng lẽ thiết kế một mẫu TV không cần tới điều khiển từ xa.

Samsung đạt lợi nhuận kỉ lục 5,86 tỉ USD trong quý II-2012

Samsung đạt lợi nhuận kỉ lục 5,86 tỉ USD trong quý II-2012

Samsung vừa công bố kết quả tài chính quý II 2012 với các thông số hết sức lạc quan, cụ thể tổng lợi nhuận của hãng đạt 5,86 tỉ USD - tăng 79% so với cùng kỳ năm ngoái, trong đó mảng kinh doanh đem về cho họ 3,65 tỉ USD tiền lời.

Tomdesgin.vn

 

Drupal Services