6.1. Mở rộng khái niệm thuật toán : thuật giải

Trong quá trình nghiên cứu giải quyết các vấn đề - bài toán, người ta đã đưa ra những nhận xét như sau :

 Có nhiều bài toán cho đến nay vẫn chưa tìm ra một cách giải theo kiểu thuật toán và cũng không biết là có tồn tại thuật toán hay không.

 Có nhiều bài toán đã có thuật toán để giải nhưng không chấp nhận được vì thời gian giải theo thuật toán đó quá lớn hoặc các điều kiện cho thuật toán khó đáp ứng.

 Có những bài toán được giải theo những cách giải vi phạm thuật toán nhưng vẫn chấp nhận được.

Từ những nhận định trên, người ta thấy rằng cần phải có những đổi mới cho khái niệm thuật toán. Người ta đã mở rộng hai tiêu chuẩn của thuật toán : tính xác định và tính đúng đắn. Việc mở rộng tính xác định đối với thuật toán đã được thể hiện qua các giải thuật đệ quy và ngẫu nhiên. Tính đúng của thuật toán bây giờ không còn bắt buộc đối với một số cách giải bài toán, nhất là các cách giải gần đúng. Trong thực tiễn, có nhiều trường hợp người ta chấp nhận các cách giải thường cho kết quả tốt (nhưng không phải lúc nào cũng tốt) nhưng ít phức tạp và hiệu quả. Chẳng hạn nếu giải một bài toán bằng thuật toán tối ưu đòi hỏi máy tính thực hiện nhiều năm thì chúng ta có thể sẵn lòng chấp nhận một giải pháp gần tối ưu mà chỉ cần máy tính chạy trong vài ngày hoặc vài giờ.

Các cách giải chấp nhận được nhưng không hoàn toàn đáp ứng đầy đủ các tiêu chuẩn của thuật toán thường được gọi là các thuật giải. Khái niệm mở rộng này của thuật toán đã mở rộng cửa cho chúng ta trong việc tìm kiếm phương pháp để giải quyết các bài toán được đặt ra.

Một trong những thuật giải thường được đề cập đến và sử dụng trong khoa học trí tuệ nhân tạo là các cách giải theo kiểu Heuristic.

 6.2. Thuật giải Heuristic

    Thuật giải Heuristic là một sự mở rộng khái niệm thuật toán. Nó thể hiện cách giải bài toán với các đặc tính sau :

  Thường tìm được lời giải tốt (nhưng không chắc là lời giải tốt nhất)

  Giải bài toán theo thuật giải Heuristic thường dễ dàng và nhanh chóng đưa ra kết quả hơn so với giải thuật tối ưu, vì vậy chi phí thấp hơn.

   Thuật giải Heuristic thường thể hiện khá tự nhiên, gần gũi với cách suy nghĩ và hành động của con người.

    Có nhiều phương pháp để xây dựng một thuật giải Heuristic, trong đó người ta thường dựa vào một số nguyên lý cơ sở như sau:

     Nguyên lý vét cạn thông minh :

Trong một bài toán tìm kiếm nào đó, khi không gian tìm kiếm lớn, ta thường tìm cách giới hạn lại không gian tìm kiếm hoặc thực hiện một kiểu dò tìm đặc biệt dựa vào đặc thù của bài toán để nhanh chóng tìm ra mục tiêu.

     Nguyên lý tham lam (Greedy):

Lấy tiêu chuẩn tối ưu (trên phạm vi toàn cục) của bài toán để làm tiêu chuẩn chọn lựa hành động cho phạm vi cục bộ của từng bước (hay từng giai đoạn) trong quá trình tìm kiếm lời giải.

     Nguyên lý thứ tự :

Thực hiện hành động dựa trên một cấu trúc thứ tự hợp lý của không gian khảo sát nhằm nhanh chóng đạt được một lời giải tốt.

     Hàm Heuristic:

 Trong việc xây dựng các thuật giải Heuristic, người ta thường dùng các hàm Heuristic. Ðó là các hàm đánh giá thô, giá trị của hàm phụ thuộc vào trạng thái hiện tại của bài toán tại mỗi bước giải. Nhờ giá trị này, ta có thể chọn được cách hành động tương đối hợp lý trong từng bước của thuật giải.

THUẬT TOÁN ĐỆ QUY

Thuật toán đệ quy là một trong những sự mở rộng cơ bản nhất của khái niệm thuật toán. Như đã biết, một thuật toán cần phải thỏa mãn 3 tính chất :

– Tính hữu hạn.

– Tính xác định

– Tính đúng đắn

    Tuy nhiên, có những bài toán mà việc xây dựng một thuật toán với đầy đủ ba tính chất trên rất khó khăn. Trong khi đó, nếu ta xây dựng một thuật toán vi phạm một vài tính chất trên thì cách giải lại trở nên đơn giản hơn nhiều và có thể chấp nhận được. Một trong những trường hợp đó là thuật toán đệ quy.

    Tư tưởng giải bài toán bằng thuật toán đệ quy là đưa bài toán hiện tại về một bài toán cùng loại, cùng tính chất (hay nói một cách nôm na là đồng dạng) nhưng ởcấp độ thấp hơn (chẳng hạn : độ lớn dữ liệu nhập nhỏ hơn, giá trị cần tính toán nhỏ hơn, ....), và quá trình này tiếp tục cho đến lúc bài toán được đưa về một cấp độ mà tại đó có thể giải được. Từ kết quả ở cấp độ này, ta sẽ lần ngược để giải được bài toán ở cấp độ cao hơn cho đến lúc giải được bài toán ở cấp độ ban đầu.

    Trong toán học ta cũng thường gặp những định nghĩa về những đối tượng, những khái niệm dựa trên chính những đối tượng, khái niệm đó.

     Ðịnh nghĩa giai thừa

Giai thừa của một số tự nhiên n, ký hiệu n! được định nghĩa là :

0! = 1

n! = (n-1)!n với mọi n>0

     Ðịnh nghĩa dãy số Fibonacci

f0 = 1

f1 = 1

fn = fn-1 + fn-2 với mọi n>1

Theo toán học, những khái niệm được định nghĩa như vậy gọi là định nghĩa theo kiểu quy nạp. Chính vì vậy, đệ quy có sự liên hệ rất chặt chẽ với quy nạp toán học.

Ðệ quy mạnh ở điểm nó có thể định nghĩa một tập vô hạn các đối tượng chỉ bằng một số hữu hạn các mệnh đề. Tuy nhiên, đặc tính này của đệ quy lại vi phạm tính xác định của thuật toán. Về nguyên tắc, một bước trong thuật toán phải được xác định ngay tại thời điểm bước đó được thi hành, nhưng với thuật toán đệ quy, bước thứ nkhông được xác định ngay trong ngữ cảnh của nó mà phải xác định thông qua một bước thấp hơn. Chẳng hạn, để tính được giá trị phần tử thứ 5 của dãy Fibonacci theo định nghĩa ở trên, ta phải tính f3+f4, nhưng ta chưa biết giá trị f3 và f4 tại thời điểm này. Ðến đây, ta phải lùi lại để tính f3 và f4. Ðể tính f3 ta lại phải lùi về để tính f2,...Tất nhiên, là quá trình tính lùi này phải dừng sau một số hữu hạn bước. Trong trường hợp này, điểm dừng chính là giá trị f1 và f0.

Ưu thế của thuật toán đệ quy là ta chỉ cần giải bài toán tại một số trường hợp đặc biệt nào đó, còn gọi là trường hợp dừng. Sau đó, các trường hợp khác của bài toán sẽ được xác định thông qua trường hợp đặc biệt này. Ðối với việc tính dãy Fibonacci, trường hợp dừng chính là giá trị của f0 và f1.

Nói một cách chính xác, mọi thuật toán đệ quy đều gồm hai phần:

 Phần cơ sở

Là các trường hợp không cần thực hiện lại thuật toán (hay không có yêu cầu gọi đệ quy). Nếu thuật toán đệ quy không có phần này thì sẽ dẫn đến bị lặp vô hạn và sinh lỗi khi thi hành. Vì lý do này mà người ta đôi lúc còn gọi phần cơ sở là trường hợp dừng.

 Phần đệ quy

Là phần trong thuật toán có yêu cầu gọi đệ quy, tức là yêu cầu thực hiện lại thuật toán nhưng với một cấp độ dữ liệu thấp hơn.