Đại học Lê Quý Đôn - 236 Hoàng Quốc Việt - Hà Nội

Chia sẻ kiến thức mọi mặt của các lớp cao học CNTT, Học viện Kỹ thuật Quân sự




Chào mừng đã đến với forum khmt.123.st
  • Bạn chưa đăng kí (hoặc chưa đăng nhập) nên quyền lợi của bạn sẽ bị hạn chế. Việc đăng kí làm thành viên hoàn toàn miễn phí, sau khi đăngkí bạn có thể post bài, tham gia thảo luận , nhìn thấy link ở những box hạn chế ... và rất nhiều quyền lợi khác. Thủ tục đăng kí rất nhanh chóng và đơn giản, hãy Đăng kí làm thành viên !
  • Nếu bạn quên mật khẩu, xin nhấn vào đây !
  • Nếu bạn gặp trục trặc trong vấn đề đăng kí hoặc không thể đăng nhập, hãy liên hệ với chúng tôi.




  • Xem chủ đề cũ hơn Xem chủ đề mới hơn Go down  Thông điệp [Trang 1 trong tổng số 1 trang]

    1 Bài tập về giải thuật quay lui on Thu May 12, 2011 8:58 pm

    Admin


    Quản trị viên
    Quản trị viên
    Câu 2:
    Trình bày giải thuật quay lui. Sử dụng giải thuật quay lui để liệt kê các xâu nhị phân độ dài n.



    Được sửa bởi Admin ngày Fri May 20, 2011 12:55 pm; sửa lần 1.

    http://khmt.123.st

    2 Giải thuật quay lui on Thu May 19, 2011 11:43 am

    HaiYen


    Thành viên cao cấp
    Thành viên cao cấp
    Quay lui (backtracking) là một chiến lược tìm kiếm lời giải cho các bài toán thỏa mãn ràng buộc. Người đầu tiên đề ra thuật ngữ này (backtrack) là nhà toán học người Mỹ D. H. Lehmer vào những năm 1950.

    Các bài toán thỏa mãn ràng buộc là các bài toán có một lời giải đầy đủ, trong đó thứ tự của các phần tử không quan trọng. Các bài toán này bao gồm một tập các biến mà mỗi biến cần được gán một giá trị tùy theo các ràng buộc cụ thể của bài toán. Việc quay lui là để thử tất cả các tổ hợp để tìm được một lời giải. Thế mạnh của phương pháp này là nhiều cài đặt tránh được việc phải thử nhiều tổ hợp chưa hoàn chỉnh, và nhờ đó giảm thời gian chạy.

    Phương pháp quay lui có quan hệ chặt chẽ với tìm kiếm tổ hợp

    Cài đặt

    Về bản chất, tư tưởng của phương pháp là thử từng khả năng cho đến khi tìm thấy lời giải đúng. Đó là một quá trình tìm kiếm theo độ sâu trong một tập hợp các lời giải. Trong quá trình tìm kiếm, nếu ta gặp một hướng lựa chọn không thỏa mãn, ta quay lui về điểm lựa chọn nơi có các hướng khác và thử hướng lựa chọn tiếp theo. Khi đã thử hết các lựa chọn xuất phát từ điểm lựa chọn đó, ta quay lại điểm lựa chọn trước đó và thử hướng lựa chọn tiếp theo tại đó. Quá trình tìm kiếm thất bại khi không còn điểm lựa chọn nào nữa.
    Quy trình đó thường được cài đặt bằng một hàm đệ quy mà trong đó mỗi thể hiện của hàm lấy thêm một biến và lần lượt gán tất cả các giá trị có thể cho biến đó, với mỗi lần gán trị lại gọi chuỗi đệ quy tiếp theo để thử các biến tiếp theo. Chiến lược quay lui tương tự với tìm kiếm theo độ sâu nhưng sử dụng ít không gian bộ nhớ hơn, nó chỉ lưu giữ trạng thái của một lời giải hiện tại và cập nhật nó.
    Để tăng tốc quá trình tìm kiếm, khi một giá trị được chọn, trước khi thực hiện lời gọi đệ quy, thuật toán thường xóa bỏ giá trị đó khỏi miền xác định của các biến có mâu thuẫn chưa được gán (kiểm tra tiến - forward checking) và kiểm tra tất cả các hằng số để tìm các giá trị khác đã bị loại trừ bởi giá trị vừa được gán (lan truyền ràng buộc - constraint propagation).

    Người ta thường sử dụng một số phương pháp để tăng tốc cho quá trình quay lui. Do các biến có thể được xử lý theo thứ tự bất kỳ, việc thử các biến bị ràng buộc chặt nhất (nghĩa là các biến có ít lựa chọn về giá trị nhất) thường có hiệu quả do nó tỉa cây tìm kiếm từ sớm (cực đại hóa ảnh hưởng của lựa chọn sớm hiện hành).

    Các cài đặt quay lui phức tạp thường sử dụng một hàm biên, hàm này kiểm tra xem từ lời giản chưa đầy đủ hiện tại có thể thu được một lời giải hay không, nghĩa là nếu đi tiếp theo hướng hiện tại thì liệu có ích hay không. Nhờ đó, một kiểm tra biên phát hiện ra các lời giải dở dang chắc chắn thất bại có thể nâng cao hiệu quả của tìm kiếm. Do hàm này hay được chạy, có thể tại mỗi bước, nên chi phí tính toán các biên cần tối hiểu, nếu không, hiệu quả toàn cục của thuật toán sẽ không được cải tiến. Các hàm kiểm tra biên được tạo theo kiểu gần như các hàm heuristic khác: nới lỏng một số điều kiện của bài toán.

    Ví dụ

    Sử dụng chiến lược quay lui 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 cách xây dựng từng phần tử, mỗi phần tử được chọn bằng cách thử tất cả các khả năng.

    Phương pháp

    Giả thiết cấu hình cần liệt kê có dạng ([i]x1,x2,...,xn). Khi đó thuật toán quay lui được thực hiện qua các bước sau:

    1) Xét tất cả các giá trị x1 có thể nhận, thử cho x1 nhận lần lượt các giá trị đó. Với mỗi giá trị thử cho x1 ta sẽ:

    2) Xét tất cả các giá trị x2 có thể nhận, lại thử cho x2 nhận lần lượt các giá trị đó. Với mỗi giá trị thử gán cho x2 lại xét tiếp các khả năng chọn x3 ... cứ tiếp tục như vậy đến bước:

    n) Xét tất cả các giá trị xn có thể nhận, thử cho xn nhận lần lượt các giá trị đó, thông báo cấu hình tìm được (x1,x2,...,xn).
    Mô tả

    Thuật toán quay lui có thể được mô tả bằng đoạn mã giả (pseudocode) sau:
    Code:

    procedure Try(i: Integer);
    begin
      for (mọi giá trị có thể gán cho xi) do
        begin
          (Thử cho xi := V)
          if (xi là phần tử cuối cùng trong cấu hình) then
            (Thông báo cấu hình tìm được)
          else
            begin
              (Ghi nhận việc cho xi nhận giá trị V (Nếu cần));
              Try(i + 1); {Gọi đệ qui để chọn tiếp xi + 1}
              (Nếu cần, bỏ ghi nhận việc thử xi := V, để thử giá trị khác);
            end;
        end;
    end;
    a có thể trình bày quá trình tìm kiếm lời giải quả thuật toán quay lui bằng cây sau:
    [You must be registered and logged in to see this image.]

    Xem chủ đề cũ hơn Xem chủ đề mới hơn Về Đầu Trang  Thông điệp [Trang 1 trong tổng số 1 trang]

    Permissions in this forum:
    Bạn không có quyền trả lời bài viết

     

    Ghi rõ nguồn khi copy các bài viết từ Website này.
    Bản quyền thuộc Khoa học Máy tính. Số lượt truy cập tính đến hiện tại:Website counter
    Modified skin by Nguyễn Anh Cường. Developed by Members of http://khmt.123.st

    Create a forum on Forumotion | © PunBB | Free forum support | Liên hệ | Report an abuse | Have a free blog with Sosblogs