THUẬT GIẢI HEURISTIC

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ơ bản 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: Hãy tìm một hành trình cho một người giao hàng đi qua n điểm khác nhau, mỗi điểm đi qua một lần và trở về điểm xuất phát sao cho tổng chiều dài đoạn đường cần đi là ngắn nhất. Giả sử rằng có con đường nối trực tiếp từ giữa hai điểm bất kỳ.
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 0(n!) (một hành trình là một hoán vị của n điểm, do đó, tổng số hành trình là số lượng hoán vị của một tập n phần tử 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:
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.
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 sau để 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 cho 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 tiếp theo 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à 0(n2).










Hình : Giải bài toán sử dụng nguyên lý Greedy
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 sau.


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ệ sẽ tiếp tục cho đến lúc hoàn thành, không thể bị cắt ngang. Để gia công một việc J1 trên một máy bất kỳ ta cần dùng một thời gian tương ứng là t1. 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. 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.
Thuật toán tìm phương án tối ưu Lo cho bài toán này theo kiểu vét cạn có độ phức tạp cỡ O(mn) (với m là số máy và n là số công việc). Bây giờ ta xét đến một thuật giải Heuristic rất đơn giản (độ phức tạp O(n)) để giải bài toán này.
  • Sắp xếp các công việc theo thứ tự giảm dần về thời gian gia công.
  • 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 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à T0 là thời gian tối ưu thì người ta đã chứng minh được rằng
, M là số máy
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 là 2 (M=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 M lớn thì tỷ số 1/M xem như bằng 0 . Như vậy, sai số tối đa mà ta phải chịu là T* ≤ 4/3 T0, 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.



The Salty Coffee

He met her on a party, she was so outstanding, many guys chasing after her, while he was so normal, nobody paid attention to him. At the end of the party, he invited her to have coffee with him. She was surprised, but as he was polite, she promised. They sat in a nice coffee shop, he was too nervous to say anything, She felt uncomfortable, she thought, "please, let me back home".
Suddenly he asked the waiter: would you please give me some salt? I"d like to put it in my coffee. Everybody stared at him, so strange! His face turned red, but still, he put the salt in his coffee and drank it*** e asked him curiously: why you have this hobby? He replied: when I was a little boy, I was living near the sea, I liked playing in the sea, I could feel the taste of the sea, salty and bite, just like the taste of the salty coffee. Now every time I have the salty coffee, I always think of my childhood, think of my hometown, I miss my hometown so much, I miss my parents who are still living there. While saying that, tears filled his eyes. She was deeply touched. That"s his true feeling, from the bottom of his heart.A man who can tell out his homesick, he must be a man who loves home, cares about home, has responsibility of home. Then she also started to speak, spoke about her faraway hometown, her childhood, her family.
That was a really nice talk, also a beautiful beginning of their story.
They continued to date. She found actually he was a man who meets all her demands: he had tolerance, was kind hearted, warm, careful...he was such a good person but she almost missed him! Thanks to his salty coffee! Then the story was just like every beautiful love story: the princess married to the prince, then they were living the happy life... And, every time she made coffee for him, she put some salt in the coffee as she knew that"s the way he liked it.
After 40 years, he passed away, left her a letter which said: "My dearest, please forgive me, forgive my whole life lie. This was the only lie I said to you----the salty coffee. Remember the first time we dated? I was so nervous at that time, actually I wanted some sugar, but I said salt. It was hard for me to change so I just went ahead. I never thought that could be the start of our communication! I tried to tell you the truth many times in my life, but I was too afraid to do that, as I have promised not to lie to you for anything. Now I"m dying, I afraid of nothing so I tell you the truth: I don"t like the salty coffee, what a strange bad taste. But I have the salty coffee for my whole life since I knew you, I never feel sorry for anything I do for you. Having you with me is my biggest happiness for my whole life. If I can live for the second time, I still want to know you and have you for my whole life, even though I have to drink the salty coffee again." Her tears made the letter totally wet. Someday, someone asked her: what"s the taste of salty coffee? It"s sweet. She replied.

Nails In The Fence

There was a little boy with a bad temper. His father gave him a bag of nails and told him that every time he lost his temper, to hammer a nail in the back fence. The first day the boy had driven 37 nails into the fence. Then it gradually dwindled down. He discovered it was easier to hold his temper than to drive those nails into the fence.
Finally the day came when the boy didn"t lose his temper at all. He told his father about it and the father suggested that the boy now pull out one nail for each day that he was able to hold his temper. The days passed and the young boy was finally able to tell his father that all the nails were gone.
The father took his son by the hand and led him to the fence. He said, "You have done well, my son, but look at the holes in the fence. The fence will never be the same. When you say things in anger, they leave a scar just like this one. You can put a knife in a man and draw it out. It won"t matter how many times you say I"m sorry, the wound is still there. A verbal wound is as bad as a physical one.

The donkey in a well

One day a farmer's donkey fell down into a well. The animal cried piteously for hours as the farmer tried to figure out what to do. Finally, he decided the animal was old and the well needed to be covered up any way, it just wasnt worth it to retrieve the donkey.
He invited all his neighbors to come over and help him. They all grabbed a shovel and began to shovel dirt into the well. At first, the donkey realized what was happening and cried horribly. Then, to everyone"s amazement, he quieted down. A few shovel loads later, the farmer finally looked down the ell and was astonished at what he saw. With every shovel of dirt that hit his back, the donkey was doing something amazing. He would shake it off and take a step up.
As the farmer"s neighbors continued to shovel dirt on top of the animal, he would shake it off and take a step up. Pretty soon, everyone was amazed as the donkey stepped up over the edge of the well and trotted off!
Life is going to shovel dirt on you, all kinds of dirt. The trick to getting out of the well is to shake it off and take a step up. Each of our challenges is a stepping stone. We can get out of the deepest wells by not stopping, never giving up! Shake it off and take a step up!
Cool Blue Outer Glow Pointer