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.
Bạn đang xem: Heuristic là gì
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.
Bài toán hành trình ngắn nhất – ứng dụng nguyên lý Greedy
Bài toán : Chúng ta trở lại với bài toán người bán hàng. Nhưng ở đây, yêu cầu bài toán hơi khác là làm sao tìm được hành trình ngắn nhất có thể được.
Tất nhiên ta có thể giải bài toán này bằng cách liệt kê tất cả con đường có thể đi, tí;nh chiều dài của mỗi con đường đó rồi tìm con đường có chiều dài ngắn nhất. Tuy nhiên, cách giải này lại có độ phức tạp O(n!) (tổng số hành trình có thể có là n!). Do đó, khi số đại lý tăng thì số con đường phải xét sẽ tăng lên rất nhanh.
Một cách giải đơn giản hơn nhiều và thường cho kết quả tương đối tốt là dùng một thuật giải Heuristic ứng dụng nguyên lý Greedy. Tư tưởng của thuật giải như sau :
1. Từ điểm khởi đầu, ta liệt kê tất cả quãng đường từ điểm xuất phát cho đến n đại lý rồi chọn đi theo con đường ngắn nhất.
2. Khi đã đi đến một đại lý, chọn đi đến đại lý kế tiếp cũng theo nguyên tắc trên. Nghĩa là liệt kê tất cả con đường từ đại lý ta đang đứng đến những đại lý chưa đi đến. Chọn con đường ngắn nhất. Lặp lại quá trình này cho đến lúc không còn đại lý nào để đi.
Bạn có thể quan sát hình 2.14 để thấy được quá trình chọn lựa.
Theo nguyên lý Greedy, ta lấy tiêu chuẩn hành trình ngắn nhất của bài toán làm tiêu chuẩn chọn lựa cục bộ. Ta hy vọng rằng, khi đi trên n đoạn đường ngắn nhất thì cuối cùng ta sẽ có một hành trình ngắn nhất. Ðiều này không phải lúc nào cũng đúng. Với điều kiện trong hình 2.14 thì thuật giải cho chúng ta một hành trình có chiều dài là 14 trong khi hành trình tối ưu là 13. Kết quả của thuật giải Heuristic trong trường hợp này chỉ lệch 1 đơn vị so với kết quả tối ưu. Trong khi đó, độ phức tạp của thuật giải Heuristic này chỉ là O(n2). Tất nhiên, thuật giải theo kiểu Heuristic đôi lúc lại đưa ra kết quả không tốt, thậm chí; rất tệ như trường hợp ở hình 2.15.
Bài toán phân việc ứng dụng của nguyên lý thứ tự
Một công ty nhận được hợp đồng gia công m chi tiết máy J1, J2,…,Jm. Công ty có n máy gia công lần lượt là P1, P2, …Pn. Mọi chi tiết đều có thể được gia công trên bất kỳ máy nào. Một khi đã gia công một chi tiết trên một máy, công việc sẽ tiếp tục cho đến lúc hoàn thành, không thể bị ngắt ngang. Ðể gia công một công việc Ji trên một máy bất kỳ ta cần dùng một thời gian tương ứng là ti. Nhiệm vụ của công ty là phải làm sao gia công xong toàn bộ n chi tiết trong thời gian sớm nhất.
Chúng ta xét bài toán trong trường hợp có 3 máy P1, P2, P3 và 6 công việc với thời gian là t1=2, t2=5, t3=8, t4=1, t5=5, t6=1. Ta có một phương án phân công (L) như hình sau :
Theo hình này, tại thời điểm t=0, ta tiến hành gia công chi tiết J2 trên máy P1, J5 trên P2 và J1 tại P3. Tại thời điểm t=2, công việc J1 được hoàn thành, trên máy P3 ta gia công tiếp chi tiết J4. Trong lúc đó, hai máy P1 và P2 vẫn đang thực hiện công việc đầu tiên mình…Sơ đồ phân việc theo hình ở trên được gọi là lược đồ GANTT. Theo lược đồ này, ta thấy thời gian để hoàn thành toàn bộ 6 công việc là 12.
Xem thêm: Direct Là Gì
Nhận xét một cách cảm tí;nh ta thấy rằng phương án (L) vừa thực hiện là một phương án không tốt. Các máy P1 và P2 có quá nhiều thời gian rảnh.
Xây dựng một thuật toán để tìm một phương án tối ưu L0 cho bài toán này là một bài toán khó, đòi hỏi các kỹ thuật phức tạp mà chúng ta sẽ không đề cập ở đây. Bây giờ ta xét đến một thuật giải Heuristic rất đơn giản để giải bài toán này.
1. Sắp xếp các công việc theo thứ tự giảm dần về thời gian gia công.
2. Lần lượt sắp xếp các việc theo thứ tự đó vào máy còn dư nhiều thời gian nhất.
Với tư tưởng như vậy, ta sẽ có một phương án L* như sau :
Rõ ràng phương án L* vừa thực hiện cũng chí;nh là phương án tối ưu của trường hợp này vì thời gian hoàn thành là 8, đúng bằng thời gian của công việc J3. Ta hy vọng rằng một thuật giải Heuristic đơn giản như vậy sẽ là một thuật giải tối ưu. Nhưng tiếc thay, ta dễ dàng đưa ra được một trường hợp mà thuật giải Heuristic không đưa ra được kết quả tối ưu.
Nếu gọi T* là thời gian để gia công xong n chi tiết máy do thuật giải Heuristic đưa ra và To là thời gian tối ưu thì người ta đã chứng minh được rằng
Với kết quả này, ta có thể xác lập được sai số mà chúng ta phải gánh chịu nếu dùng Heuristic thay vì tìm một lời giải tối ưu. Chẳng hạn với số máy = 2 (n=2) ta có
, và đó chí;nh là sai số cực đại mà trường hợp ở trên đã gánh chịu. Theo công thức này, số máy càng lớn thì sai số càng lớn.
Trong trường hợp n lớn thì 1/(3n) xem như bằng 0. Như vậy, sai số tối đa mà ta phải chịu là T* ? 4/3To, nghĩa là sai số tối đa là 33%. Tuy nhiên, khó tìm ra được những trường hợp mà sai số đúng bằng giá trị cực đại, dù trong trường hợp xấu nhất. Thuật giải Heuristic trong trường hợp này rõ ràng đã cho chúng ta những lời giải tương đối tốt.
Bài toán Ta-canh – ứng dụng của hàm Heuristic
Bài toán Ta-canh đã từng là một trò chơi khá phổ biến, đôi lúc người ta còn gọi đây là bài toán 9-puzzle. Trò chơi bao gồm một hình vuông kí;ch thước 3×3 ô. Có 8 ô có số, mỗi ô có một số từ 1 đến 8. Một ô còn trống. Mỗi lần di chuyển chỉ được di chuyển một ô nằm cạnh ô trống về phí;a ô trống. Vấn đề là từ một trạng thái ban đầu bất kỳ, làm sao đưa được về trạng thái cuối là trạng thái mà các ô được sắp lần lượt từ 1 đến 8 theo thứ tự từ trái sang phải, từ trên xuống dưới, ô cuối dùng là ô trống.
Cho đến nay, người ta vẫn chưa tìm được một thuật toán chí;nh xác, tối ưu để giải bài toán này. Tuy nhiên, cách giải theo kiểu Heuristic lại khá đơn giản. Nhận xét rằng : tại mỗi thời điểm ta chỉ có tối đa 4 ô có thể di chuyển. Vấn đề là tại thời điểm đó, ta sẽ chọn lựa di chuyển ô nào? Chẳng hạn ở hình trên, ta nên di chuyển (1), (2), (6) hay (7)?
Gọi T0 là trạng thái đí;ch của bài toán và TK là trạng thái hiện tại. Ta gọi V(i,j) là con số nằm ở ô (i,j), với ô trống V(i,j)=0.
Xem thêm: Psu Là Gì – Nguồn Máy Tính
Ta đặt d(i,j) là số ô cần di chuyển để đưa con số ở ô (i,j) về đúng vị trí; của nó ở trạng thái TO .
Hàm FK tại trạng thái TK bằng tổng của các d(i,j) sao cho vị trí; (i,j) không phải là ô trống.
Như vậy đối với trạng thái ở hình ban đầu, hàm FK sẽ có giá trị là
FK = 2+1+3+1+0+1+2+2=12.
Một cách tổng quát, giá trị hàm FK tại trạng thái TK sẽ là
Từ trạng thái TK , ta có tối đa 4 cách di chuyển.Ta ký hiệu các trạng thái mới này lần lượt là TKT ,TKD , TKTr ,TKP ứng với con số ở trên, dưới, trái, phải ô trống hiện tại bị di chuyển. Chẳng hạn, ứng với hình ban đầu, ta có thể có 4 trạng thái mới như hình bên.
Ứng với các trạng thái mới, ta cũng sẽ có các hàm FK tương ứng là FKT ,FKD ,FKTr ,FKP.
Dựa vào 4 con số này, ta sẽ chọn hướng đi có hàm FK tương ứng là nhỏ nhất, trong trường hợp bằng nhau ta chọn ngẫu nhiên một trong số các đường đó. Với ví; dụ, ta sẽ chọn di chuyển ô mang số (2) vì FKD là nhỏ nhất. Sau khi đã di chuyển một ô, bài toán chuyển về một trạng thái TK mới. Ta lại thực hiện quá trình trên cho đến lúc đạt được trạng thái đí;ch.
Hàm FK trong ví; dụ của chúng ta là một dạng hàm Heuristic. Tất nhiên, để giải được bài toán này trong những tình huống khó, hàm FK cần có nhiều sửa đổi.
Chuyên mục: Hỏi Đáp
