HEURISTIC LÀ GÌ

  -  

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

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

Có nhiều bài tân oán mang lại đến nay vẫn chưa đưa ra một phương pháp giải theo kiểu thuật toán thù cùng cũng không biết là tất cả tồn tại thuật toán hay là không.

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

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

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

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

Một trong những thuật giải thường được đề cập đến cùng sử dụng trong khoa học trí tuệ nhân tạo là các biện pháp 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 tân oán. Nó thể hiện bí quyết giải bài xích toán với những đặc tính sau :

Thường tìm kiế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 bác toán theo thuật giải Heuristic thường dễ dàng và nhanh lẹ đưa ra kết quả hơn so với giải thuật tối ưu, bởi vì vậy ngân sách thấp hơn.

Thuật giải Heuristic thường thể hiện hơi 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 tắc cơ sở như sau:

Nguyên lý vét cạn xuất sắc :

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

Nguyên lý ttê mê 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 để có tác dụng tiêu chuẩn chọn lựa hành động đến phạm vi cục bộ của từng bước (hay từng giai đoạn) vào quy trình tìm kiế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 những thuật giải Heuristic, người ta thường sử dụng những hàm Heuristic. Ðó là các hàm đánh giá chỉ thô, giá bán trị của hàm phụ thuộc vào trạng thái hiện tại của bài toán thù tại mỗi bước giải. Nhờ giá bán trị này, ta tất cả thể chọn được bí quyết hành động tương đối hợp lý vào từng bước của thuật giải.

Bài toán thù 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 xích tân oán người bán sản phẩm. Nhưng ở đây, yêu thương cầu bài xích toán thù hơi khác là làm sao tìm kiếm được hành trình ngắn nhất bao gồm thể được.

Tất nhiên ta tất cả thể giải bài bác toán này bằng biện pháp liệt kê tất cả nhỏ đường bao gồm thể đi, tính chiều nhiều năm của mỗi con đường đó rồi tìm bé đường có chiều nhiều năm ngắn nhất. Tuy nhiên, giải pháp giải này lại gồm độ phức tạp O(n!) (tổng số hành trình tất cả thể tất cả là n!). Do đó, Khi số đại lý tăng thì số nhỏ đường phải xét sẽ tăng lên rất nhanh hao.

Một biện pháp giải đơn giản hơn nhiều với thường cho kết quả tương đối tốt là cần sử dụng một thuật giải Heuristic ứng dụng nguyên tắc 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 bé đườ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 nguim tắc trên. Nghĩa là liệt kê tất cả bé đườ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 mang đến đến lúc không thể đại lý nào để đi.

Bạn gồm thể quan lại cạnh bên 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 ngắn nhất của bài bác toán có tác dụng 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ẽ gồm một hành trình ngắn nhất. Ðiều này không phải thời điểm làm sao cũng đúng. Với điều kiện trong hình 2.14 thì thuật giải đến họ một hành trình dài bao gồm chiều lâu năm là 14 trong những lúc hành trình dài 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 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ả ko tốt, thậm chí rất tệ như trường hợp ở hình 2.15.

*

*

Bài tân oán phân việc – ứng dụng của nguyên tắc thứ tự

Một chủ thể nhận được hợp đồng gia công m chi tiết thiết bị 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 gồm thể được gia công bên trên bất kỳ lắp thêm như thế nào. Một khi đã gia công một đưa ra tiết bên trên một đồ vật, công việc sẽ tiếp tục đến đến dịp dứt, ko thể bị ngắt ngang. Ðể gia công một công việc Ji bên trên một lắp thêm bất kỳ ta cần dùng một thời gian tương ứng là ti. Nhiệm vụ của cửa hàng là phải làm thế nào gia công xong toàn bộ n chi tiết vào thời gian sớm nhất.

Chúng ta xét bài bác toán thù vào trường hợp bao gồm 3 trang bị 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 tất 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 sản phẩm công nghệ P1, J5 bên trên P2 cùng J1 tại P3. Tại thời điểm t=2, công việc J1 được ngừng, trên đồ vật P3 ta gia công tiếp chi tiết J4. Trong thời điểm đó, nhì sản phẩm P1 cùng 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 ở 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: Ở Đâu Bán Vật Tư Tiêu Hao Là Gì ? Đặc Điểm Và Phân Loại Nó Như Thế Nào?

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 vật dụng P1 và P2 bao gồm thừa nhiều thời gian rảnh.

Xây dựng một thuật toán để kiếm tìm một phương án tối ưu L0 cho bài tân oán này là một bài bác tân oán nặng nề, đòi hỏi các kỹ thuật phức tạp nhưng họ 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 xích tân oá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 do 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 cố kỉnh, ta dễ dàng đưa ra được một trường hợp nhưng 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 chấm dứt n bỏ ra tiết sản phẩm vì chưng thuật giải Heuristic đưa ra và To là thời gian tối ưu thì người ta đã chứng minch được rằng

*

Với kết quả này, ta có thể xác lập được không nên số nhưng mà chúng ta phải gánh chịu nếu sử dụng Heuristic cụ vày 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ó

*

, cùng đó chính là sai số cực đại cơ mà trường hợp ở bên trên đã gánh chịu. Theo công thức này, số máy càng lớn thì không nên 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 nhưng ta phải chịu là T* ? 4/3To, nghĩa là không đúng số tối đa là 33%. Tuy nhiên, khó khăn đưa ra được những trường hợp mà sai số đúng bằng giá chỉ trị cực đại, mặc dù vào trường hợp xấu nhất. Thuật giải Heuristic vào trường hợp này rõ ràng đã mang đến chúng ta những lời giải tương đối tốt.

Bài toán thù 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 dịp người ta còn gọi đây là bài toán thù 9-puzzle. Trò chơi bao gồm một hình vuông vắn kích thước 3x3 ô. Có 8 ô có số, mỗi ô tất 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 sang trọng phải, từ bên 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 thù chính xác, tối ưu để giải bài xích toán thù này. Tuy 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 bắt buộc di chuyển (1), (2), (6) xuất xắc (7)?

Gọi T0 là trạng thái đích của bài bác toán cùng 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: Quy Trình Lập Kế Hoạch Và Triển Khai Sản Xuất, Các Bước Lập Kế Hoạch Sản Xuất Mang Lại Hiệu Quả

*
*

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ó 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 bao gồm tối đa 4 biện pháp 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 bé 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ể tất cả 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ẽ gồm những hàm FK tương ứng là FKT ,FKD ,FKTr ,FKP.

Dựa vào 4 bé số này, ta sẽ chọn hướng đi tất cả hàm FK tương ứng là nhỏ nhất, vào trường hợp bằng nhau ta chọn ngẫu nhiên một trong số những đường đó. Với ví dụ, ta sẽ chọn di chuyển ô có số (2) vị FKD là nhỏ nhất. Sau lúc đã di chuyển một ô, bài toán thù chuyển về một trạng thái TK mới. Ta lại thực hiện quá trình bên trên đến đến thời điểm đạt được trạng thái đích.

*
*

Hàm FK vào ví dụ của chúng ta là một dạng hàm Heuristic. Tất nhiên, để giải được bài xích toán này trong những tình huống nặng nề, hàm FK cần tất cả nhiều sửa đổi.