thuật toán quay lui &Alogrithm &BackTracking &Thuat_toan_quay_lui

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

  1. Định nghĩa: là một kĩ thuật tìm kiếm lời giải dựa trên các điều kiện trên cơ sở quay lui
  2. Điều kiện áp dụng
    1. Xác định cấu hình đầu và cuối của bài toán -> Xác định mỗi thành phần nhỏ hơn Xi nhận ni khả năng
    2. Ứng với mỗi khả năng ni được chấp nhận cho Xi nếu i là thành phần cuối cùng (i=n) ta ghi nhận nghiệm của bài toán. Nếu i chưa phải cuối cùng ta xác định thành phần thứ i +1.
    3. Nếu không có khả năng ni nào được chấp thuận cho thành phần Xi thì ta quay lại bước trước đó (i-1) để thử lại các khả năng khác.
  3. Mô hình 
        Back-Track ( int i ) {
        For ( j =; j <=ni; j++ ){
            if () {
                X[i] = ;
                if ( i ==n) Result();
                else Back-Track(i+1);
            }
        }
    }
  4. Các bài toán điển hình - được cài với ngôn ngữ C/C++
    1. Sinh xâu nhị phân 
              Void Try ( int i ) {
            for (int j =0; j<=1; j++){
                X[i] = j;
                if ( i ==n) Result();
                else Try (i+1);
                }
        }
    2. Sinh tổ hợp chập k của n 
              Void Try ( int i ) {
            for (int j =X[i-1]+1; j<=N-K+ i; j++){
                X[i] = j;
                if ( i ==K) Result();
                else Try (i+1);
            }
        }
    3. Sinh hoán vị 
              Void Try ( int i ) {
            for (int j =1; j<=N; j++){
                if (chuaxet[j] ) {
                    X[i] = j;chuaxet[j] = False;
                    if ( i ==N) Result();
                    else Try (i+1);
                    Chuaxet[j] = True;
                }
            }
        }
    4. Bài toán đặt hậu 
              void Try (int i){
            for(int j=1; j<=n; j++){
                if( A[j] && Xuoi[ i – j + n ] && Nguoc[i + j -1]){
                    X[i] =j; A[j]=FALSE;
                    Xuoi[ i - j + n]=FALSE;
                    Nguoc[ i + j - 1]=FALSE;
                    if(i==n) Result();
                    else Try(i+1);
                    A[j] = TRUE;
                    Xuoi[ i - j + n] = TRUE;
                    Nguoc[ i + j - 1] = TRUE;
                }
            }
        }