Bài viết sưu tầm

MỘt sỐ phương pháp khác

3.8.1 Phương pháp sinh và thử.

Chiến lược này đơn giản, gồm ba bước:

-               Trước hết tạo ra một giải pháp. Trong vài bài toán cụ thể đó là việc chọn một lời giải trong không gian các lời giải hay tạo ra một đường đi.

-               Thứ hai, thử xem lời giải đó có thích hợp không bằng cách so sánh phương án khác hay so sanh với điểm cuối cần suy diễn.

-               Tiếp theo, nếu lời giải đạt được thì dừng, ngước lại, lặp lại từ bước đầu với nút khác.

Với phương pháp này nếu bài toán có llời giải thì sẽ đưa đến đích. Tuy nhiên kích thước bài toán lớn sẽ tăng khối lượng tính toán. Việc tạo lời giải ban đầu có thể thực hiện ngẫu nhiên, và cũng hy vọng ngẫu nhiên mà đạt được lời giải, bởi vậy, không thể không tính đến chỉ một vài hướng đi được cảm nhận là tốt, và loại trừ trước các hướng không dẫn đến lời giải.

Ví dụ1.Tìm số có 6 chữ số mà tổng bình phương các chữ số chia hết cho 3.

Giai đoạn sinh: tạo ra số có 6 chữ số và ta gọi các chữ số từ trái qua phải lần lượt là a, b, c, d, e, f thì  0 < a <= 9 ,  0 <= b, c, d, e, f <= 9.

     Giai đoạn thử: nểu a*a + b*b + c*c + d*d + e*e + f*f chia hết cho 3 thì chon, ngược lại, tạo ra số khác.

Ví dụ 2. Một xâu nhị phân được gọi là thưa nếu trong xâu không có hai chữ số 1 đứng kề nhau. Tìm xâu nhị phân thưa có chiều dài n.            

     Giai đoạn sinh: Tạo ra một xâu nhị phân S có chiều dài n.

     Giai đoạn thử: Kiểm tra có phải xâu thưa không? (Pos(‘11’,S) = 0).

Trong hai ví dụ trên, sinh viên có thể lập trình để tìm tất cả các lời giải của bài toán, chẳng hain tìm tất cả các xâu nhị phân thưa có chiều dài n cho trước.