Thuật toán quay lui cơ bản
TIL
590
Male avatar

identify viết ngày 30/06/2016

Back TracKing

1. Tư Tưởng
Dùng để giải bài toán liệt kê các cấu hình. Mỗi cấu hình được xây dựng bằng từng phần tử. Mỗi phần tử lại được chọn bằng cách thử tất cả các khả năng.

Step of back tracking trong việc liệt kê dạng x[1...n] :

  1. Xét tất cả các giá trị X[1] có thể nhận, Thử X[1] nhận các giá trị đó. Với mỗi giá trị của X[1] ta sẽ:
  2. Xét tất cả giá trị X[2] có thể nhận, lại thử X[2] cho các giá trị đó. Với mỗi giá trị X[2] lại xét khả năng giá trị của X[3].........tiếp tục như vậy cho tới bước:
  3. ...
  4. ....
  5. Xét tất cả giá trị X[n] có thể nhận, thử cho X[n] nhận lần lượt giá trị đó. Thông báo cấu hình tìm được.

Mô hình thuật toán

procedure Try(int i)
begin
for (mọi giá trị V mà gán cho X[i]) // tương ứng B1
begin
thử X[i] = V
if x[i] là phần tử cuối cùng thì thông báo cấu hình tìm được
else
begin
Ghi nhận việc cho x[i] nhận giá trị V [nếu cần]
Try(i+1)
Bỏ ghi nhận việc thử X[i] = V để thử giá trị khác [nếu cần]
end
end
end

2. Ứng dụng bài toán cụ thể
1.Liệt kê dãy nhị phân độ dài N

Yêu cầu đề bài: Nhập vào N, in ra dãy nhị phân có độ dài N

void try(int i)
int j;
for(j=0 ;j < BINARY; j++){
Data[i]=j; // thử các giá trị của data[i] có thể nhận
if(i == N){
print(N);
return;
}
try(i+1); //thử tiếp giá trị x[i+1]
}

2. Bài toán xếp hậu
Yêu cầu: xếp 8 quân hậu trên bàn cờ.
ý tưởng: ta nhận thấy cần phải kiểm tra xem vị trí đặt quân hậu có thõa mãn hay không. để đưa ra tập V { các giá trị thỏa mãn của X}

cần 3 ma trận check cột, check chéo nhỏ, check đường chèo lớn.

  1. check côt: ma trận a, với mọi a[i] = 0
  2. check chéo nhỏ: ma trận B , với mọi B[i-j + N] = 0
  3. check chéo lớn. Ma trận C , với mọi C[i+j] = 0

function check(i){
check cột ok;
check chéo nhỏ ok;
check cheo lớn ok;
}

theo tư tưởng back track, thử từng giá trị mà có thể gán cho X

void try(int i) //thử dặt quân hậu thứ i vào hàng i
int j;
for(j = 1; j < n; j++) {
If check(i) thỏa mãn
gán X[i] = j;
đánh dấu là đặt X -----> gán giá trị a[i] ,b[i-j+N], C[i+j] = 1
đặt tiếp quân hậu tiếp theo ---> Try(i+1);
bỏ đánh dấu X
}

identify 22-06-2016

Bình luận


White
{{ comment.user.name }}
Bỏ hay Hay
{{comment.like_count}}
Male avatar
{{ comment_error }}
Hủy
   

Hiển thị thử

Chỉnh sửa

Male avatar

identify

2 bài viết.
0 người follow
Kipalog
{{userFollowed ? 'Following' : 'Follow'}}
Cùng một tác giả
Male avatar
2 2
Câu hỏi phỏng vấn C Program phần 1 1. Sự khác nhau của declaration and definition Declaration of a variable/function simply declares that the v...
identify viết 11 tháng trước
2 2
Bài viết liên quan
White
0 2
fCC: Technical Documentation Page note So I have finished the HTML part of this exercise and I want to come here to lament about the lengthy HTML ...
HungHayHo viết 28 ngày trước
0 2
White
19 1
Toán tử XOR có tính chất: + A XOR A = 0 + 0 XOR A = A Với tính chất này, có thể cài đặt bài toán sau với độ phức tạp O(N) về runtime, và với O(1)...
kiennt viết gần 2 năm trước
19 1
White
1 1
Chào mọi người, hôm nay mình viết một bài TIL nhỏ về cách lấy độ phân giải của màn hình hiện tại đang sử dụng. xdpyinfo | grep dimensions Kết quả...
namtx viết 12 tháng trước
1 1
{{like_count}}

kipalog

{{ comment_count }}

bình luận

{{liked ? "Đã kipalog" : "Kipalog"}}


Male avatar
{{userFollowed ? 'Following' : 'Follow'}}
2 bài viết.
0 người follow

 Đầu mục bài viết

Vẫn còn nữa! x

Kipalog vẫn còn rất nhiều bài viết hay và chủ đề thú vị chờ bạn khám phá!