Heuristic là gì

     

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

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

Có nhiều việc cho đến ni vẫn chưa tìm ra một bí quyết giải theo kiểu thuật toán và cũng ko biết là bao gồm tồn tại thuật toán tuyệt không.

Bạn đang xem: Heuristic là gì

Có nhiều vấn đề đã bao gồm 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 vấn đề được giải theo những giải pháp 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 gồm những đổi mới đến khái niệm thuật toán. Người ta đã mở rộng nhì tiêu chuẩn của thuật toán : tính xác định với 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 những giải thuật đệ quy cùng 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à những cách giải gần đúng. Trong thực tiễn, bao gồm nhiều trường hợp người ta chấp nhận những cách giải thường cho kết quả tốt (nhưng ko phải thời gian nào cũng tốt) nhưng không nhiều phức tạp cùng hiệu quả. Chẳng hạn nếu giải một việc bằng thuật toán tối ưu đòi hỏi máy tính xách tay 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à lại chỉ cần máy tính chạy trong vài ngày hoặc vài giờ.

Các phương pháp giải chấp nhận được nhưng không trọn vẹn đáp ứng đầy đủ những 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 họ trong việc tìm kiếm phương pháp để giải quyết những 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 vào 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 phương pháp giải vấn đề với các đặc tính sau :

Thường tra cứu đượ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 giá cả 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ới hành động của nhỏ người.

bao gồm 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 tắc vét cạn hợp lý :

trong một vấn đề tìm kiếm làm sao đó, khi không khí tìm kiếm lớn, ta thường tìm biện pháp giới hạn lại không gian tìm kiếm hoặc thực hiện một kiểu dò tra cứu đặc biệt dựa vào đặc thù của bài toán để nhanh lẹ 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 câu hỏi để làm cho tiêu chuẩn chọn lựa hành động mang lại phạm vi cục bộ của từng bước (hay từng giai đoạn) trong quy 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 cạnh bên nhằm gấp rút đạ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 những hàm Heuristic. Ðó là các hàm đánh giá bán thô, giá chỉ trị của hàm phụ thuộc vào trạng thái hiện tại của vấn đề tại mỗi bước giải. Nhờ giá trị này, ta tất cả thể chọn được phương pháp hành động tương đối hợp lý trong từng bước của thuật giải.

bài xích toán hành trình dài ngắn nhất - ứng dụng nguyên tắc Greedy

Bài toán : họ trở lại với bài toán người phân phối hàng. Nhưng ở đây, yêu cầu việc hơi khác là làm thế nào tìm được hành trình ngắn nhất bao gồm thể được.

Tất nhiên ta gồm thể giải bài toán này bằng bí quyết liệt kê tất cả bé đường bao gồm thể đi, tính chiều nhiều năm của mỗi con đường đó rồi tìm con đường bao gồm chiều dài ngắn nhất. Tuy nhiên, cách giải này lại tất cả độ phức tạp O(n!) (tổng số hành trình dài có thể gồm là n!). Do đó, lúc số đại lý tăng thì số nhỏ đườ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 cùng thường mang lại kết quả tương đối tốt là sử 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 mang đến đến n đại lý rồi chọn đi theo bé đường ngắn nhất.

2. Lúc đã đ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 bé đường ngắn nhất. Lặp lại quá trình này đến đến lúc không hề đại lý nào để đi.

Bạn gồm thể quan gần kề hình 2.14 để thấy được quy trình chọn lựa.

Theo nguyên tắc Greedy, ta lấy tiêu chuẩn hành trình dài ngắn nhất của việc làm tiêu chuẩn chọn lựa cục bộ. Ta hy vọng rằng, khi đi bên trên n đoạn đường ngắn nhất thì cuối cùng ta sẽ gồm một hành trình dài ngắn nhất. Ðiều này không phải cơ hội nào cũng đúng. Với điều kiện vào hình 2.14 thì thuật giải cho bọn họ một hành trình dài có chiều lâu năm là 14 trong những khi hành trình tối ưu là 13. Kết quả của thuật giải Heuristic vào trường hợp này chỉ lệch 1 đơn vị so với kết quả tối ưu. Trong những 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 thời gian 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.

*

*

việc 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 tối ưu m đưa ra tiết sản phẩm công nghệ J1, J2,...,Jm. Công ty có n máy gia công lần lượt là P1, P2, ...Pn. Mọi bỏ ra tiết đều có thể được gia công trên bất kỳ vật dụng nào. Một lúc đã tối ưu một chi tiết bên trên một máy, công việc sẽ tiếp tục đến đế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 lắp thêm bất kỳ ta cần cần sử 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 thế nào gia công xong xuôi toàn bộ n chi tiết trong thời gian sớm nhất.

Chúng ta xét câu hỏi trong trường hợp bao gồm 3 đồ vật P1, P2, P3 với 6 công việc với thời gian là t1=2, t2=5, t3=8, t4=1, t5=5, t6=1. Ta bao gồm một phương án cắt cử (L) như hình sau :

*

Theo hình này, tại thời điểm t=0, ta tiến hành tối ưu chi tiết J2 trên lắp thêm P1, J5 bên 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 thứ P3 ta tối ưu tiếp chi tiết J4. Trong những khi đó, hai sản phẩm 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 như hình ở bên trên được gọi là lược đồ GANTT. Theo lược đồ này, ta thấy thời gian để chấm dứt toàn bộ 6 công việc là 12.

Xem thêm: Vitamin D Và Bệnh Vàng Da Ở Trẻ Bị Vàng Da Uống Vitamin D3 Được Không ?

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. Những máy P1 cùng P2 gồm quá nhiều thời gian rảnh.

Xây dựng một thuật toán để tìm kiếm một phương án tối ưu L0 cho việc này là một vấn đề khó, đòi hỏi các kỹ thuật phức tạp mà bọn họ sẽ ko đề cập ở đây. Bây giờ ta xét đến một thuật giải Heuristic rất đơn giản để giải vấ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 những việc theo thứ tự đó vào thứ 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 đó là phương án tối ưu của trường hợp này vì thời gian xong xuôi 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 cơ mà thuật giải Heuristic ko đưa ra được kết quả tối ưu.

*

Nếu gọi T* là thời gian để gia công dứt n đưa ra tiết máy bởi vì 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 bao gồm thể xác lập được không đúng số mà bọn họ phải gánh chịu nếu sử dụng Heuristic thay do tìm một lời giải tối ưu. Chẳng hạn với số máy = 2 (n=2) ta gồm

*

, và đó đó là sai số cực đại cơ mà trường hợp ở trên đã gánh chịu. Theo công thức này, số sản phẩm càng lớn thì sai số càng lớn.

Trong trường hợp n lớn thì 1/(3n) coi 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à không đúng số tối đa là 33%. Mặc dù nhiên, khó khăn tìm ra được những trường hợp mà lại 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 cụ thể đã cho họ những lời giải tương đối tốt.

việc 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 cơ hội người ta còn gọi đây là câu hỏi 9-puzzle. Trò chơi bao gồm một hình vuông vắn kích thước 3x3 ô. Tất cả 8 ô gồm 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à những ô được sắp lần lượt từ 1 đến 8 theo thứ tự từ trái lịch sự phải, từ bên trên xuống dưới, ô cuối sử dụng là ô trống.

*

Cho đến nay, người ta vẫn chưa search được một thuật toán bao gồm xác, tối ưu để giải vấn đề này. Mặc dù nhiên, giải pháp giải theo kiểu Heuristic lại hơi đơn giản. Nhận xét rằng : tại mỗi thời điểm ta chỉ bao gồm 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 cần di chuyển (1), (2), (6) tuyệt (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à nhỏ số nằm ở ô (i,j), với ô trống V(i,j)=0.

Xem thêm: Nhiệt Độ Ngăn Mát Tủ Lạnh Toshiba Inverter, Cách Điều Chỉnh Nhiệt Độ Tủ Lạnh Toshiba Inverter

*
*

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 lớn .

Hàm FK tại trạng thái TK bằng tổng của các d(i,j) làm thế nào 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ó mức giá trị là

FK = 2+1+3+1+0+1+2+2=12.

Một cách tổng quát, giá bán trị hàm FK tại trạng thái TK sẽ là

*

Từ trạng thái TK , ta tất cả tối đa 4 phương pháp di chuyển.Ta ký hiệu những trạng thái mới này lần lượt là TKT ,TKD , TKTr ,TKP ứng với nhỏ 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 bao gồm thể gồm 4 trạng thái mới như hình bên.

Ứng với những trạng thái mới, ta cũng sẽ có những 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 tất 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 vào số những đường đó. Với ví dụ, ta sẽ chọn di chuyển ô mang số (2) do FKD là nhỏ nhất. Sau khoản thời gian đã di chuyển một ô, việc chuyển về một trạng thái TK mới. Ta lại thực hiện quá trình trên mang đến đến lúc đạt được trạng thái đích.

*
*

Hàm FK trong ví dụ của họ là một dạng hàm Heuristic. Tất nhiên, để giải được vấn đề này vào những tình huống khó, hàm FK cần gồm nhiều sửa đổi.