Đề tài ứng dụng thuật toán quay lui vào giải bài toán liệt kê

Đề tài ứng dụng thuật toán quay lui vào giải bài toán liệt kê là đề tài của cô Trương Nguyễn Nha Trang – Trường THPT Chuyên Bảo Lộc

1.1 L‎ý do chọn đề tài:

Với mỗi bài toán trong Tin học thường có rất nhiều phương pháp giải, nhưng tìm được phương pháp giải tối ưu không phải là vấn đề đơn giản. Để giải một bài toán thường phải xác định được:

  • Bài toán thuộc lớp bài toán nào.
  • Sử dụng phương pháp tối ưu nào để giải nó.

Có những bài toán yêu cầu phải liệt kê nghiệm theo một điều kiện nào đó. Với lớp bài toán này sử dụng thuật toán quay lui để giải quyết sẽ dễ dàng và đơn giản hơn các phương pháp khác (phương pháp “sinh” cũng giải được một số bài toán liệt kê cấu hình). Vì vậy, tôi đề xuất sáng kiến “Ứng dụng thuật toán quay lui giải bài toán liệt kê”. Tuy “thuật toán quay lui” là không mới, không tối ưu trong việc giải quyết một số bài toán nào đó mà phương pháp khác cũng giải được, nhưng cũng có nhiều bài toán mà chỉ có thuật toán này mới giải quyết được nó một cách dễ dàng. Những bài toán dùng phương pháp quay lui để giải gặp rất nhiều trong các kỳ thi học sinh giỏi tỉnh, Tin học trẻ không chuyên cũng như học sinh giỏi quốc gia trong nhiều năm.

Ý tưởng cơ bản của “thuật toán quay lui” là liệt kê hết tất cả các khả năng có thể, hay còn gọi là phương pháp vét cạn, duyệt hết cấu hình.

1.2  Mục đích, nhiệm vụ của việc thực hiện đề tài nghiên cứu:

Nhằm giúp giáo viên và học sinh khi đứng trước một bài toán, xác định được là bài toán đó có thể áp dụng được thuật toán quay lui hay không? Và cách giải cụ thể như thế nào? Từ đó tôi đề ra mục đích, nhiệm vụ của việc thực hiện đề tài như sau:

– Giới thiệu khái niệm “thuật toán quay lui (Backtracking)”, những ưu điểm, hạn chế của thuật toán.

– Giới thiệu một số bài toán điển hình trong lớp bài toán.

Vì thế sáng kiến có các nội dung sau:

Mục 1. Phương pháp quay lui (backtracking).

Mục 2. Dạng 1: Tìm tất cả các nghiệm.

Mục 3. Dạng 2: Tìm một nghiệm.

Mục 4. Dạng 3: Tìm nghiệm tối ưu thoả mãn điều kiện.

Với mỗi dạng có các ví dụ điển hình, ý tưởng và chương trình tham khảo.

1.3 Đối tượng, thời gian và phương pháp nghiên cứu:

1.3.1 Đối tượng nghiên cứu:

Sáng kiến kinh nghiệm “Ứng dụng thuật toán quay lui giải bài toán liệt kê” có đối tượng nghiên cứu là các bài toán giải bằng thuật toán quay lui.

1.3.2 Thời gian nghiên cứu:

“Thuật toán quay lui” được nghiên cứu trong quá trình học tập và giảng dạy, bồi dưỡng các đội tuyển học sinh giỏi.

1.3.3 Phương pháp nghiên cứu:

Chủ yếu là nghiên cứu đề tài, tham khảo tài liệu, ý kiến đóng góp của đồng nghiệp và qua thực tiễn giảng dạy.

 PHẦN II NỘI DUNG

2.1 Phương pháp (thuật toán quay lui Backtracking)

Trong các kỹ thuật cơ bản để thiết kế thuật toán, quay lui là một trong những kỹ thuật quan trọng nhất vì nó cho phép giải một lớp các bài toán khá lớn có dạng tổng quát như sau:

Tìm một (hoặc tất cả) bộ nghiệm (x1, x2, …, xn) thỏa mãn điều kiện F nào đó, trong đó các thành phần xi được chọn từ một tập hữu hạn Di với mọi i = 1, 2, …, n.

Tư tưởng của phương pháp quay lui như sau :

–  Ta xây dựng bộ nghiệm từng bước, bắt đầu từ thành phần nghiệm x1 được chọn trong các giá trị có thể S1 = D1.

–  Giả sử đã chọn được các thành phần x1, x2, …, xi-1, từ các điều kiện của bài toán ta sẽ xác định được tập Si gồm các giá trị được chọn cho thành phần nghiệm xi. Tập Si là tập con của Di và phụ thuộc vào các thành phần x1, x2, …, xi-1 đã chọn. Chọn một phần tử xi thuộc Si như một thành phần của bộ nghiệm. Từ bộ (x1, x2, …, xi) lặp lại quá trình trên để tiếp tục mở rộng nghiệm cho thành phần xi+1. Nếu không chọn được thành phần nào của xi+1 (do Si+1 rỗng) thì ta quay lại chọn một phần tử khác của Si làm thành phần nghiệm xi (ý nghĩa của quay lui là ở bước này).

–   Trong quá trình mở rộng nghiệm ta luôn kiểm tra nghiệm thành phần có phải là nghiệm của bài toán hay không. Nếu chỉ cần một nghiệm thì ta dừng lại, nếu cần tìm tất cả các nghiệm thì quá trình tìm nghiệm chỉ dừng khi tất cả các khả năng chọn các thành phần nghiệm đã vét cạn.

Quay lui là một trong các phương pháp vét cạn trong đó các giá trị nghiệm được chọn không thực hiện được bằng cách duyệt tuyến tính. Điểm tốt của thuật toán quay lui so với vét cạn tuyến tính là hạn chế bớt các nhánh phải duyệt mà theo những nhánh đó không tìm được lời giải thể hiện ở việc xây dựng các tập giá trị có thể Si khi tìm thành phần nghiệm xi và quay lui khi không mở rộng thành phần nghiệm xi+1.

Tuy nhiên hạn chế của phương pháp này là phải duyệt qua nhiều khả năng nên độ phức tạp của chương trình thường ở mức giai thừa hay hàm mũ nên tốc độ tính toán khá lâu trong trường hợp kích thước của dữ liệu vào khá lớn. Để khắc phục hạn chế này người ta tìm cách hạn chế các khả năng không đưa đến kết quả bằng phương pháp nhánh cận, tuy nhiên lớp bài toán dùng được phương pháp này không nhiều.

Đa số các bài toán vét cạn sử dụng phương pháp duyệt đệ quy để xét hết mọi khả năng có thể có nghiệm theo nguyên tắc “thử sai” và quay lui. Về tư tưởng, các thuật toán vét cạn rất đơn giản nhưng ứng dụng vào việc giải các bài toán cần có những kỹ thuật nhất định.

Để giải bài toán bằng thuật toán quay lui cần thực hiện các công việc quan trọng sau:

* Tìm cách biểu diễn nghiệm của bài toán dưới dạng một dãy các đối tượng được chọn dần từng bước (x1, x2, …, xn).

* Xác định được tập Si các khả năng được chọn làm thành phần thứ i của nghiệm. Chọn cách thích hợp để biểu diễn Si.

* Tìm các điều kiện để các nghiệm đã chọn là các nghiệm của bài toán.

Một số lưu ý khi xây dựng thuật toán quay lui:

* Phải duyệt qua mọi phương án của bài toán có thể chứa nghiệm (vét cạn).

* Tránh trường hợp duyệt trùng lặp các khả năng đã duyệt.

Để giải các bài toán bằng thuật toán quay lui, thông thường ta thường dùng thủ tục đệ quy Try(i : Integer) để chọn thành phần nghiệm xi.

Có ba dạng cơ bản trong các thuật toán quay lui:

Dạng 1: Tìm tất cả các nghiệm.

Dạng 2: Tìm một nghiệm.

Dạng 3: Tìm nghiệm tối ưu thỏa mãn điều kiện.

Ta lần lượt xét cách giải các dạng trên bằng phương pháp quay lui:

2.2 Dạng 1: Tìm tất cả các nghiệm

Mô hình của thuật toán quay lui có thể mô tả như sau:

Procedure Try(i: Integer);    {Thủ tục này thử cho xi nhận lần lượt các giá trị mà nó có thể nhận}

Begin

for <mọi giá trị j có thể gán cho xi> do

Begin

  <Thử cho xi := j>;

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ị j (Nếu cần)>;

Try(i + 1);                {Gọi đệ quy để chọn tiếp xi+1}

                     <Nếu cần, bỏ ghi nhận việc thử xi := j, để thử giá trị khác>;

End;

End;

End;

Thuật toán quay lui thường bắt đầu bằng lời gọi Try(1)

Xem chi tiết tài liệu:

19 thoughts on “Đề tài ứng dụng thuật toán quay lui vào giải bài toán liệt kê

Add Comment