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 (2 votes)
Ảnh của Tommy Tran

Tommy Tran 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
  • Phone/Zalo: (+84) 944 225 212
  • WhatsApp: (+84) 944 225 212
  • Line Messenger: (+84) 944 225 212
  • Email: asaleotestf@gmail.com
  • Telegram Messenger: https:/t.me/tommytran0401

Quảng cáo việc làm

 

Thích hợp các bạn nữ mảng thợ may làm việc tại nước NGA

Đơn hàng Tuyển dụng 100 Thợ may đi Nga(đợt 1 tháng 3.2021, đợt 2 tháng 5.2021). Lương thực lãnh 800 USD, bao ăn ở, vé máy bay và visa, phí xuất cảnh(1800 USD)trả khi đi làm có lương. Bạn có thể liên hệ CÔNG TY qua Phone/Zalo: (+84) 944 225 212. Công ty sẽ tư vấn cho bạn.

Xem chi tiết: >>> https://bit.ly/3o9NOfR

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

 
Gaming Becomes Exciting With 3D Bowling App for Android

Gaming Becomes Exciting With 3D Bowling App for Android

The Android market has so many games for users to choose from. The reality is not all these games are that great.

Watchguard, IronPort

Giải pháp Bảo mật với sản phẩm của Watchguard và IronPort

Theo Báo cáo Thương mại điện tử (TMĐT) Việt Nam 2011 vừa được Cục TMĐT và CNTT - Bộ Công Thương công bố, chỉ có 40% doanh nghiệp quan tâm tới việc bảo vệ thông tin cá nhân.

Seo

Bài 2: Keyword Research với Google Adsense

Trong bài viết này mình sẽ trình bày về phần quan trọng nhất trong chiến dịch kiếm tiền với Google Adsense, nghiên cứu từ khòa(Keyword Research). Như các bạn đã biết, bước đầu tiên là phải tìm một chủ đề thích hợp cho website, có keyword ít cạnh tranh để dễ dàng SEO lên vị trí 1 của Google. Có rất nhiều bài viết về để giúp ta suy nghĩ ra những ý tưởng cho trang web của mình rất hay trên internet, và mình sẽ trình bày cách chọn ý tưởng của Pat (smartpassiveincome.com). Sau này có thời gian, mình sẽ viết thêm những cách khác.