HEURISTICS LÀ GÌ

     

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 việc cho đến ni vẫn chưa tìm ra một phương pháp giải theo kiểu thuật toán và cũng ko biết là gồm tồn tại thuật toán tốt không.

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

Có nhiều câu hỏi đã có thuật toán để giải nhưng ko chấp nhận được bởi thời gian giải theo thuật toán đó quá lớn hoặc các điều kiện đến thuật toán cực nhọc đáp ứng.

Có những câu hỏi được giải theo những bí quyết 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 tất 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 cùng 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 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ố phương pháp giải bài bác toán, nhất là các cách giải gần đúng. Trong thực tiễn, gồm nhiều trường hợp người ta chấp nhận các cách giải thường đến kết quả tốt (nhưng ko phải lúc nào cũng tốt) nhưng không nhiều phức tạp và 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 vi tính thực hiện nhiều năm thì họ có thể sẵn lòng chấp nhận một giải pháp gần tối ưu cơ mà chỉ cần máy tính xách tay chạy vào 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 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à những 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 những bài toán được đặt ra.

Một vào 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 việc với những đặc tính sau :

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

Giải việc theo thuật giải Heuristic thường dễ dàng và mau lẹ đưa ra kết quả hơn so với giải thuật tối ưu, do vậy chi tiêu thấp hơn.

Thuật giải Heuristic thường thể hiện tương đối tự nhiên, gần gũi với biện pháp suy nghĩ cùng hành động của nhỏ người.

gồm nhiều phương pháp để xây dựng một thuật giải Heuristic, vào đó 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 lý tưởng :

trong một bài toán tìm kiếm làm sao đó, khi không khí tìm kiếm lớn, ta thường tìm cách 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 việc để lập cập tìm ra mục tiêu.

nguyên tắc tham lam (Greedy):

Lấy tiêu chuẩn tối ưu (trên phạm vi toàn cục) của vấn đề để có tác dụng tiêu chuẩn chọn lựa hành động mang đến 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 tắc thứ tự :

Thực hiện hành động dựa bên trên một cấu trúc thứ tự hợp lý của không gian khảo giáp nhằm mau lẹ đạ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 dùng các hàm Heuristic. Ðó là những 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á chỉ trị này, ta tất cả thể chọn được biện pháp hành động tương đối hợp lý trong từng bước của thuật giải.

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

Bài toán : chúng ta trở lại với việc người chào bán 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 tất cả thể giải việc này bằng biện pháp liệt kê tất cả con đường bao gồm thể đi, tính chiều dài của mỗi nhỏ đường đó rồi tìm con đường gồm chiều lâu năm ngắn nhất. Tuy nhiên, cách giải này lại gồm độ phức tạp O(n!) (tổng số hành trình dài có thể bao gồm là n!). Do đó, lúc số đại lý tăng thì số con đường phải xét sẽ tăng lên rất nhanh.

Một bí quyết giải đơn giản hơn nhiều với thường đến 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 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ả nhỏ đường từ đại lý ta đang đứng đến những đại lý chưa đi đến. Chọn nhỏ đường ngắn nhất. Lặp lại quá trình này cho đến lúc không hề đại lý như thế nào để đi.

Bạn tất cả thể quan gần kề hình 2.14 để thấy được quá 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 việc 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 thuộc ta sẽ tất cả một hành trình dài 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 vào hình 2.14 thì thuật giải cho chúng ta một hành trình dài có chiều nhiều năm là 14 trong những lúc 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 lúc đó, độ 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 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 sản phẩm công nghệ J1, J2,...,Jm. Công ty có n máy tối ưu lần lượt là P1, P2, ...Pn. Mọi chi tiết đều tất cả thể được tối ưu trên bất kỳ sản phẩm công nghệ nào. Một lúc đã gia công một bỏ ra tiết bên trên một máy, công việc sẽ tiếp tục đến đến dịp hoàn thành, ko 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 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 hoàn thành toàn bộ n bỏ ra tiết vào thời gian sớm nhất.

Chúng ta xét bài toán trong trường hợp bao gồm 3 sản phẩm 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 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 sản phẩm P1, J5 trên P2 với J1 tại P3. Tại thời điểm t=2, công việc J1 được hoàn thành, trên vật dụng P3 ta gia công tiếp đưa ra tiết J4. Trong khi đó, hai lắp thê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 để xong xuôi toàn bộ 6 công việc là 12.

Xem thêm: Hướng Dẫn Cách Chèn Trang Bìa Trong Word 2010, 2013, 2016, Cách Tạo Trang Bìa Tùy Chỉnh Trong Microsoft Word

Nhận xét một phương pháp 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 với P2 bao gồm 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 việc khó, đòi hỏi những kỹ thuật phức tạp mà bọn 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 việc 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 đồ vật còn dư nhiều thời gian nhất.

Với tư tưởng như vậy, ta sẽ tất 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 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 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 vày thuật giải Heuristic đưa ra cùng 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 nên số mà họ phải gánh chịu nếu sử dụng Heuristic thay vì tìm một lời giải tối ưu. Chẳng hạn với số đồ vật = 2 (n=2) ta gồm

*

, và đó đó là sai số cực đại nhưng trường hợp ở bên trên đã gánh chịu. Theo công thức này, số vật dụng càng lớn thì không đúng số càng lớn.

Trong trường hợp n lớn thì 1/(3n) xem như bằng 0. Như vậy, không đúng 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%. Tuy nhiên, khó tìm ra được những trường hợp mà lại sai số đúng bằng giá chỉ 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.

vấ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 tương đối phổ biến, đôi thời điểm 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 vắn kích thước 3x3 ô. Gồm 8 ô gồm số, mỗi ô bao gồm 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 thanh lịch 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 search được một thuật toán thiết yếu xác, tối ưu để giải vấn đề này. Mặc dù nhiên, cách 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ỉ gồm tối đa 4 ô tất 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 yêu cầu di chuyển (1), (2), (6) hay (7)?

Gọi T0 là trạng thái đích của việc 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: Cài Đặt Định Vị Số Điện Thoại Người Khác Qua Gps, Google Map

*
*

Ta đặt d(i,j) là số ô cần di chuyển để đưa nhỏ 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 những 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 phương pháp 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 cam kết 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 tất 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ẽ có các hàm FK tương ứng là FKT ,FKD ,FKTr ,FKP.

Dựa vào 4 nhỏ 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ố các đường đó. Với ví dụ, ta sẽ chọn di chuyển ô mang số (2) bởi vì 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 cho đến dịp đạt được trạng thái đích.

*
*

Hàm FK trong ví dụ của bọn 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.