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.
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ở 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.
Phát biểu hình thức có thể khó hình dung.
Để cụ thể hợn, ta hãy cùng nhau quan sát một ví dụ cụ. Nhiệm vụ của
chúng ta trong ví dụ này là xây dựng các quy luật để có thể kết luận một
người như thế nào khi đi tắm biển thì bị cháy nắng. Ta gọi tính chất cháy nắng hay không cháy nắng là thuộc tính quan tâm (thuộc tính mục tiêu).
Như vậy, trong trường hợp này, tập R của chúng ta chỉ gồm có hai phần
tử {"cháy nắng", "bình thường"}. Còn tập P là tất cả những người được
liệt kê trong bảng dưới (8 người) Chúng ta quan sát hiện tượng cháy nắng
dựa trên 4 thuộc tính sau : chiều cao (cao, trung bình, thấp), màu tóc (vàng, nâu, đỏ) cân nặng (nhẹ, TB, nặng), dùng kem (có, không),. Ta gọi các thuộc tính này gọi là thuộc tính dẫn xuất.
Dĩ nhiên là trong thực tế để có thể đưa
ra được một kết luận như vậy, chúng ta cần nhiều dữ liệu hơn và đồng
thời cũng cần nhiều thuộc tính dẫn xuất trên. Ví dụ đơn giản này chỉ
nhằm để minh họa ý tưởng của thuật toán máy học mà chúng ta sắp trình
bày.
Ý tưởng đầu tiên của phương pháp này là tìm cách phân hoạch tập P ban đầu thành các tập Pi sao cho tất cả các phần tử trong tất cả các tập Pi đều có chung thuộc tính mục tiêu.
Sau khi đã phân hoạch xong tập P thành tập các phân hoạch Pi được đặc trưng bởi thuộc tính đích ri (ri∈R), bước tiếp theo là ứng với mỗi phân hoạch Pita xây dựng luật Li : GTi → ri trong đó các GTi là mệnh đề được hình thành bằng cách kết hợp các thuộc tính dẫn xuất.
Một lần nữa, vấn đề hình thức có thể làm bạn cảm thấy khó khăn. Chúng ta hãy thử ý tưởng trên với bảng số liệu mà ta đã có.
Có hai cách phân hoạch hiển nhiên nhất mà ai cũng có thể nghĩ ra. Cách đầu tiên là cho mỗi người vào một phân hoạch riêng (P1 = {Sarah}, P2
= {Dana}, … tổng cộng sẽ có 8 phân hoạch cho 8 người). Cách thứ hai là
phân hoạch thành hai tập, một tập gồm tất cả những người cháy nắng và tập còn lại bao gồm tất cả những người không cháy nắng. Tuy đơn giản nhưng phân hoạch theo kiểu này thì chúng ta chẳng giải quyết được gì !!
Đâm chồi
Chúng ta hãy thử một phương pháp khác.
Bây giờ bạn hãy quan sát thuộc tính đầu tiên – màu tóc. Nếu dựa theo màu
tóc để phân chia ta sẽ có được 3 phân hoạch khác nhau ứng với mỗi giá
trị của thuộc tính màu tóc. Cụ thể là :
Pvàng = { Sarah, Dana, Annie, Kartie }
Pnâu= { Alex, Peter, John }
Pđỏ= { Emmile }
* Các người bị cháy nắng được gạch dưới và in đậm.
Thay vì liệt kê ra như trên, ta dùng sơ đồ cây để tiện mô tả cho các bước phân hoạch sau :
Quan sát hình trên ta thấy rằng phân hoạch Pnâu và Pđỏthỏa mãn được điều kiện "có chung thuộc tính mục tiêu" (Pnâuchứa toàn người không cháy nắng, Pđỏchứa toàn người cháy nắng).
Còn lại tập Pvàng là còn lẫn lộn người
cháy năng và không cháy nắng. Ta sẽ tiếp tục phân hoạch tập này thành
các tập con. Bây giờ ta hãy quan sát thuộc tính chiều cao. Thuộc tính
này giúp phân hoạch tập Pvàng thành 3 tập con : PVàng, Thấp = {Annie, Kartie}, PVàng, T.Bình= {Sarah} và PVàng,Cao= { Dana }
Nếu nối tiếp vào cây ở hình trước ta sẽ có hình ảnh cây phân hoạch như sau :
Quá trình này cứ thế tiếp tục cho đến khi
tất cả các nút lá của cây không còn lẫn lộn giữa cháy nắng và không
cháy nắng nữa. Bạn cũng thấy rằng, qua mỗi bước phân hoạch cây phân
hoạch ngày càng "phình" ra. Chính vì vậy mà quá trình này được gọi là
quá trình "đâm chồi". Cây mà chúng ta đang xây dựng được gọi là cây định
danh.
Đến đây, chúng ta lại gặp một vấn đề mới.
Nếu như ban đầu ta không chọn thuộc tính màu tóc để phân hoạch mà chọn
thuộc tính khác như chiều cao chẳng hạn để phân hoạch thì sao? Cuối cùng
thì cách phân hoạch nào sẽ tốt hơn?
Phương án chọn thuộc tính phân hoạch
Vấn đề mà chúng ta gặp phải cũng tương tự
như bài toán tìm kiếm : "Đứng trước một ngã rẽ, ta cần phải đi vào
hướng nào?". Hai phương pháp đánh giá dưới đây sẽ giúp ta chọn được
thuộc tính phân hoạch tại mỗi bước xây dựng cây định danh.
Quinlan
Quinlan quyết định thuộc tính phân hoạch bằng cách xây dựng các vector đặc trưng cho mỗi giá trị của từng thuộc tính dẫn xuất và thuộc tính mục tiêu. Cách tính cụ thể như sau :
Với mỗi thuộc tính dẫn xuất A còn có thể sử dụng để phân hoạch, tính :
VA(j) = ( T(j, r1), T(j, r2) , …, T(j, rn) )
T(j, ri) = (tổng số phần tử trong phân
hoạch có giá trị thuộc tính dẫn xuất A là j và có giá trị thuộc tính mục
tiêu là ri ) / ( tổng số phần tử trong phân hoạch có giá trị thuộc tính
dẫn xuất A là j )
* trong đó r 1 , r 2 , … , rn
là các giá trị của thuộc tính mục tiêu
*
Như vậy nếu một thuộc tính A có thể nhận một trong 5 giá trị khác nhau thì nó sẽ có 5 vector đặc trưng.
Một vector V(Aj) được gọi là vector đơn vị nếu nó chỉ có duy nhất một thành phần có giá trị 1 và những thành phần khác có giá trị 0.
Thuộc tính được chọn để phân hoạch là thuộc tính có nhiều vector đơn vị nhất.
Trở lại ví dụ của chúng ta, ở trạng thái
ban đầu (chưa phân hoạch) chúng ta sẽ tính vector đặc trưng cho từng
thuộc tính dẫn xuất để tìm ra thuộc tính dùng để phân hoạch. Đầu tiên là
thuộc tính màu tóc. Thuộc tính màu tóc có 3 giá trị khác nhau (vàng, đỏ, nâu) nên sẽ có 3 vector đặc trưng tương ứng là :
Tổng số vector đơn vị của thuộc tính tóc vàng là 2
Các thuộc tính khác được tính tương tự, kết quả như sau :
VC.Cao(Cao) = (0/2,2/2) = (0,1)
VC.Cao(T.B) = (2/3,1/3)
VC.Cao(Thấp) = (1/3,2/3)
VC.Nặng (Nhẹ) = (1/2,1/2)
VC.Nặng (T.B) = (1/3,2/3)
VC.Nặng (Nặng) = (1/3,2/3)
VKem (Có) = (3/3,0/3) = (1,0)
VKem(Không) = (3/5,2/5)
Như vậy thuộc tính màu tóc có số vector đơn vị nhiều nhất nên sẽ được chọn để phân hoạch.
Sau khi phân hoạch theo màu tóc xong, chỉ
có phân hoạch theo tóc vàng (Pvàng) là còn chứa những người cháy nắng
và không cháy nắng nên ta sẽ tiếp tục phân hoạch tập này. Ta sẽ thực
hiện thao tác tính vector đặc trưng tương tự đối với các thuộc tính còn
lại (chiều cao, cân nặng, dùng kem). Trong phân hoạch Pvàng, tập dữ liệu của chúng ta còn lại là :
VC.Cao(Cao) = (0/1,1/1) = (0,1)
VC.Cao(T.B) = (1/1,0/1) = (1,0)
VC.Cao(Thấp) = (1/2,1/2)
VC.Nặng (Nhẹ) = (1/2,1/2)
VC.Nặng (T.B) = (1/2,1/2)
VC.Nặng (Nặng) = (0,0)
VKem (Có) = (0/2,2/2) = (0,1)
VKem(Không) = (2/2,0/2) = (1,0)
2 thuộc tính dùmg kem và chiều cao đều có
2 vector đơn vị. Tuy nhiên, số phân hoạch của thuộc tính dùng kem là ít
hơn nên ta chọn phân hoạch theo thuộc tính dùng kem. Cây định danh cuối
cùng của chúng ta sẽ như sau :
Độ đo hỗn loạn
Thay vì phải xây dựng các vector đặc
trưng như phương pháp của Quinlan, ứng với mỗi thuộc tính dẫn xuất ta
chỉ cần tính ra độ đo hỗn loạn và lựa chọn thuộc tính nào có độ đo hỗn
loại là thấp nhất. Công thức tính như sau :
TA =
trong đó :
bt là tổng số phần tử có trong phân hoạch
bj là tổng số phần tử có thuộc tính dẫn xuất A có giá trị j.
bri : tổng số phần tử có thuộc tính dẫn xuất A có giá trị j và thuộc tính mục tiêu có giá trị i.
Phát sinh tập luật
Nguyên tắc phát sinh tập luật từ cây định
danh khá đơn giản. Ứng với mỗi nút lá, ta chỉ việc đi từ đỉnh cho đến
nút lá đó và phát sinh ra luật tương ứng. Cụ thể là từ cây định danh kết
quả ở cuối phần II.2 ta có các luật sau (xét các nút lá từ trái sang
phải)
(Màu tóc vàng) và (có dùng kem) → không cháy nắng
(Màu tóc vàng) và (không dùng kem) → cháy nắng
(Màu tóc nâu) → không cháy nắng
(Màu tóc đỏ) → cháy nắng
Khá đơn giản phải không? Có lẽ không có gì phải nói gì thêm. Chúng ta hãy thực hiện bước cuối cùng là tối ưu tập luật.
Tối ưu tập luật
Loại bỏ mệnh đề thừa
Khác so với các phương pháp loại bỏ mệnh
đề thừa đã được trình bày trong phần biểu diễn tri thức (chỉ quan tâm
đến logic hình thức), phương pháp loại bỏ mệnh đề thừa ở đây dựa vào dữ
liệu. Với ví dụ và tập luật đã có ở phần trước, bạn hãy quan sát luật
sau :
(Màu tóc vàng) và (có dùng kem) → không cháy nắng
Bây giờ ta hãy lập một bảng (gọi là bảng Contigency), bảng thống kê những người có dùng kem tương ứng với tóc màu vàng và bị cháy nắng hay không. Trong dữ liệu đã cho, có 3 người không dùng kem.
Theo bảng thống kê này thì rõ ràng là
thuộc tính tóc vàng (trong luật trên) không đóng góp gì trong việc đưa
ra kết luận cháy nắng hay không (cả 3 người dùng kem đều không cháy
nắng) nên ta có thể loại bỏ thuộc tính tóc vàng ra khỏi tập luật.
Sau khi loại bỏ mệnh đề thừa, tập mệnh đề của chúng ta trong ví dụ trên sẽ còn :
(có dùng kem) → không cháy nắng
(Màu tóc vàng) và (không dùng kem) → cháy nắng
(Màu tóc nâu) → không cháy nắng
(Màu tóc đỏ) → cháy nắng
Như vậy quy tắc chung để có thể loại bỏ một mệnh đề là như thế nào? Rất đơn giản, giả sử luật của chúng ta có n mệnh đề :
A1 và A2 và … và An → R
Để kiểm tra xem có thể loại bỏ mệnh đề Ai hay không, bạn hãy lập ra một tập hợp P bao gồm các phần tử thỏa tất cả mệnh đề A1 , A2 , … Ai-, Ai+1, …, An (lưu ý : không cần xét là có thỏa Ai hay không, chỉ cần thỏa các mệnh đề còn lại là được)
Sau đó, bạn hãy lập bảng Contigency như sau :
Trong đó
E là số phần tử trong P thỏa cả Ai và R.
F là số phần tử trong P thỏa Ai và không thỏa R
G là số phần tử trong P không thỏa Ai và thỏa R
H là số phần tử trong P không thỏa Ai và không thỏa R
Nếu tổng F+H = 0 thì có thể loại bỏ mệnh đề Ai ra khỏi luật.
Xây dựng mệnh đề mặc định
Có một vấn đề đặt ra là khi gặp phải một
trường hợp mà tất cả các luật đều không thỏa thì phải làm như thế nào?
Một cách hành động là đặt ra một luật mặc định đại loại như :
Nếu không có luật nào thỏa → cháy nắng (1)
Hoặc
Nếu không có luật nào thỏa → không cháy nắng. (2)
(chỉ có hai luật vì thuộc tính mục tiêu chỉ có thể nhận một trong hai giá trị là cháy nắng hay không cháy nắng)
Giả sử ta đã chọn luật mặc định là (2) thì tập luật của chúng ta sẽ trở thành :
(Màu tóc vàng) và (không dùng kem) → cháy nắng
(Màu tóc đỏ) → cháy nắng
Nếu không có luật nào thỏa → không cháy nắng. (2)
Lưu ý rằng là chúng ta đã loại bỏ đi tất
cả các luật dẫn đến kết luận không cháy nắng và thay nó bằng luật mặc
định. Tại sao vậy? Bởi vì các luật này có cùng kết luận với luật mặc định. Rõ ràng là chỉ có thể có một trong hai khả năng là cháy nắng hay không.
Vấn đề là chọn luật nào? Sau đây là một số quy tắc.
1) Chọn luật mặc định sao cho nó có thể
thay thế cho nhiều luật nhất. (trong ví dụ của ta thì nguyên tắc này
không áp dụng được vì có 2 luật dẫn đến cháy nắng và 2 luật dẫn đến
không cháy nắng)
2) Chọn luật mặc định có kết luận phổ
biến nhất. Trong ví dụ của chúng ta thì nên chọn luật (2) vì số trường
hợp không cháy nắng là 5 còn không cháy nắng là 3.
3) Chọn luật mặc định sao cho tổng số
mệnh đề của các luật mà nó thay thế là nhiều nhất. Trong ví dụ của chúng
ta thì luật được chọn sẽ là luật (1) vì tổng số mệnh đề của luật dẫn
đến cháy nắng là 3 trong khi tổng số mệnh đề của luật dẫn đến không cháy
nắng chỉ là 2.
Script là một cách biểu diễn tri thức tương tự như frame nhưng thay vì đặc tả một đối tượng, nó mô tả một chuỗi các sự kiện. Để mô tả chuỗi sự kiện, script sử dụng một dãy các slot chứa thông tin về các con người, đối tượng và hành động liên quan đến sự kiện đó.
Tuy cấu trúc của các script là rất khác nhau tùy theo bài toán, nhưng nhìn chung một script thường bao gồm các thành phần sau :
Điều kiện vào(entry condition): mô tả những tình huống hoặc điều kiện cần được thỏa mãn trước khi các sự kiện trong script có thể diễn ra.
Role (diễn viên): là những con người có liên quan trong script.
Prop (tác tố): là tất cả những đối tượng được sử dụng trong các chuỗi sự kiện sẽ diễn ra.
Scene(Tình huống) : là chuỗi sự kiện thực sự diễn ra.
Result (Kết quả) : trạng thái của các Role sau khi script đã thi hành xong.
Track (phiên bản) : mô tả một biến thể (hoặc trường hợp đặc biệt) có thể xảy ra trong đoạn script.
Sau đây là một ví dụ tiêu biểu cho
script. Ví dụ này là một biến thể của ví dụ nổi tiếng về nhà hàng bán
thức ăn nhanh (các nhà hàng bán gà rán mà ta thường gặp trong các siêu
thị!) thường được sử dụng để minh họa cách biểu diễn tri thức bằng
script trong cách sách nói về trí tuệ nhân tạo. Đi ăn trong một nhà hàng
là một tình huống thường gặp trong cuộc sống với những điều kiện vào, diễn viên, tác tố, hoàn cảnh, kết quả khá
"chuẩn". Và qua script ở ví dụ, bạn sẽ thấy phương pháp này có thể được
dùng để mô tả chính xác những tình huống diễn ra hàng ngày của những
nhà hàng bán thức ăn nhanh. Các tình huống là
những đoạn script con trong đoạn script chính để mô tả những tình huống
nhỏ trong toàn bộ quá trình. Lưu ý rằng trong đoạn script này có tình
huống tùy chọn trong đó mô tả việc khách hàng mua thức ăn về thay vì vào
nhà hàng ăn.
Script "nhà hàng"
Phiên bản : Nhà hàng bán thức ăn nhanh.
Diễn viên : Khách hàng
Người phục vụ.
Tác tố : Bàn phục vụ.
Chỗ ngồi.
Khay đựng thức ăn
Thức ăn
Tiền
Các loại gia vị như muối, tương, ớt, tiêu, ...
Điều kiện vào :
Khách hàng đói
Khách hàng có đủ tiền để trả.
Tình huống 1 : Vào nhà hàng
Khách hàng đậu xe vào bãi đậu xe.
Khách hàng bước vào nhà hàng.
Khách hàng xếp hàng trước bàn phục vụ.
Khách hàng đọc thực đơn trên tường và quyết định sẽ kêu món ăn gì.
Tình huống 2: Kêu món ăn.
Khách hàng kêu món ăn với người phục vụ (đang đứng ở quầy phục vụ)
Người phục vụ đặt thức ăn lên khay và đưa hóa đơn tính tiền cho khách.
Khách hàng trả tiền cho người phục vụ.
Tình huống 3: Khách hàng dùng món ăn
Khách hàng lấy thêm các gia vị
Khách hàng cầm khay đến một bàn còn trống.
Khách hàng ăn thức ăn.
Tình huống 3A (tùy chọn) : Khách hàng mua thức ăn đem về
Khách hàng mang thức ăn về nhà.
Tình huống 4 : Ra về
Khách hàng thu dọn bàn
Khách hàng bỏ rác (thức ăn thừa, xương, mảng vụn, ...) vào thùng rác.
Khách hàng ra khỏi nhà hàng.
Khách hàng lái xe đi.
Kết quả :
Khách hàng không còn đói.
Khách hàng còn ít tiền hơn ban đầu.
Khách hàng vui vẻ *
Khách hàng bực mình *
Khách hàng quá no.
* Tùy chọn.
Script rất hữu dụng trong việc dự đoán
điều gì sẽ xảy đến trong những tình huống xác định. Thậm chí trong những
tình huống chưa diễn ra, script còn cho phép máy tính dự đoán được
việc gì sẽ xảy ra và xảy ra đối với ai và vào thời điểm nào. Nếu máy
tính kích hoạt một script, người dùng có thể đặt câu hỏi và hệ thống có
thể suy ra được những câu trả lời chính xác mà không cần người dùng cung
cấp thêm nhiều thông tin (trong một số trường hợp có thể không cần thêm
thông tin). Do đó, cũng giống như frame, script là một dạng biểu diễn
tri thức tương đối hữu dụng vì nó cho phép ta mô tả chính xác những tình
huống "chuẩn" mà con người vẫn thực hiện mỗi ngày hoặc đã nắm bắt chính
xác.
Để cài đặt script trong máy tính, bạn
phải tìm cách lưu trữ các tri thức dưới dạng hình thức. LISP là ngôn ngữ
lập trình phù hợp nhất để làm điều này. Sau khi đã cài đặt xong script,
bạn (người dùng) có thể đặt câu hỏi về những con người hoặc điều kiện
có liên quan trong script. Hệ thống sau đó sẽ tiến hành thao tác tìm
kiếm hoặc thao tác so mẫu để tìm câu trả lời. Chẳng hạn bạn có thể đặt
câu hỏi "Khách hàng làm gì trước tiên?". Hệ thống sẽ tìm thấy câu trả
lời trong scene 1 và đưa ra đáp án "Đậu xe và bước vào nhà hàng".
A* là một phiên
bản đặc biệt của AKT áp dụng cho trường hợp đồ thị. Thuật giải A* có sử
dụng thêm tập hợp CLOSE để lưu trữ những trường hợp đã được xét đến. A* mở rộng AKTbằng
cách bổ sung cách giải quyết trường hợp khi "mở" một nút mà nút này đã
có sẵn trong OPEN hoặc CLOSE. Khi xét đến một trạng thái Ti bên cạnh
việc lưu trữ 3 giá trị cơ bản g,h’, f’ để phản ánh độ tốt của trạng thái
đó, A* còn lưu trữ thêm hai thông số sau :
1. Trạng thái cha của trạng thái Ti (ký hiệu là Cha(Ti) : cho biết trạng thái dẫn đến trạng thái Ti. Trong trường hợp có nhiều trạng thái dẫn đến Tithì chọn Cha(Ti) sao cho chi phí đi từ trạng thái khởi đầu đến Ti là thấp nhất, nghĩa là :
g(Ti) = g(Tcha) + cost(Tcha, Ti) là thấp nhất.
2. Danh sách các trạng thái kế tiếp của Ti: danh
sách này lưu trữ các trạng thái kế tiếp Tk của Ti sao cho chi phí đến
Tk thông qua Ti từ trạng thái ban đầu là thấp nhất. Thực chất thì danh
sách này có thể được tính ra từ thuộc tính Cha của các trạng thái được
lưu trữ. Tuy nhiên, việc tính toán này có thể mất nhiều thời gian (khi
tập OPEN, CLOSE được mở rộng) nên người ta thường lưu trữ ra một danh
sách riêng. Trong thuật toán sau đây, chúng ta sẽ không đề cập đến việc
lưu trữ danh sách này. Sau khi hiểu rõ thuật toán, bạn đọc có thể dễ
dàng điều chỉnh lại thuật toán để lưu trữ thêm thuộc tính này.
1. Đặt OPEN chỉ chứa T0. Đặt g(T0) = 0, h’(T0) = 0 và f’(T0) = 0. Đặt CLOSE là tập hợp rỗng.
2. Lặp lại các bước sau cho đến khi gặp điều kiện dừng.
2.a. Nếu OPEN rỗng : bài toán vô nghiệm, thoát.
2.b. Ngược lại, chọn Tmax trong OPEN sao cho f’(Tmax) là nhỏ nhất
2.b.1. Lấy Tmax ra khỏi OPEN và đưa Tmax vào CLOSE.
2.b.2. Nếu Tmaxchính là TGthì thoát và thông báo lời giải là Tmax.
2.b.3. Nếu Tmax không phải là TG. Tạo ra danh sách tất cả các trạng thái kế tiếp của Tmax. Gọi một trạng thái này là Tk. Với mỗi Tk, làm các bước sau :
2.b.3.1. Tính g(Tk) = g(Tmax) + cost(Tmax, Tk).
2.b.3.2. Nếu tồn tại Tk’ trong OPEN trùng với Tk.
Nếu g(Tk) < g(Tk’) thì
Đặt g(Tk’) = g(Tk)
Tính lại f’(Tk’)
Đặt Cha(Tk’) = Tmax
2.b.3.3. Nếu tồn tại Tk’ trong CLOSE trùng với Tk.
Nếu g(Tk) < g(Tk’) thì
Đặt g(Tk’) = g(Tk)
Tính lại f’(Tk’)
Đặt Cha(Tk’) = Tmax
Lan truyền sự thay đổi giá trị g, f’ cho tất cả các trạng thái kế tiếp của Ti (ở tất cả các cấp) đã được lưu trữ trong CLOSE và OPEN.
2.b.3.4. Nếu Tkchưa xuất hiện trong cả OPEN lẫn CLOSE thì :
Thêm Tk vào OPEN
Tính : f' (Tk) = g(Tk)+h’(Tk).
Có một số điểm cần giải thích trong thuật
giải này. Đầu tiên là việc sau khi đã tìm thấy trạng thái đích TG, làm
sao để xây dựng lại được "con đường" từ T0 đến
TG. Rất đơn giản, bạn chỉ cần lần ngược theo thuộc tính Cha của các
trạng thái đã được lưu trữ trong CLOSE cho đến khi đạt đến T0. Đó chính là "con đường" tối ưu đi từ TG đến T0 (hay nói cách khác là từ T0 đến TG).
Điểm thứ hai là thao tác cập nhật lại
g(Tk’) , f’(Tk’) và Cha(Tk’) trong bước 2.b.3.2 và 2.b.3.3. Các thao tác
này thể hiện tư tưởng : "luôn chọn con đường tối ưu nhất". Như chúng ta
đã biết, giá trị g(Tk’) nhằm lưu trữ chi phí tối ưu thực sự tính từ T0
đến Tk’. Do đó, nếu chúng ta phát hiện thấy một "con đường" khác tốt
hơn thông qua Tk (có chi phí nhỏ hơn) con đường hiện tại được lưu trữ
thì ta phải chọn "con đường" mới tốt hơn này. Trường hợp 2.b.3.3 phức
tạp hơn. Vì từ Tk’ nằm trong tập CLOSE nên từ Tk’ ta đã lưu trữ các
trạng thái con kế tiếp xuất phát từ Tk’. Nhưng g(Tk’) thay đổi dẫn đến
giá trị g của các trạng thái con này cũng phải thay đổi theo. Và đến
lượt các trạng thái con này lại có thể có các các trạng thái con tiếp
theo của chúng và cứ thế cho đến khi mỗi nhánh kết thúc với một trạng
thái trong OPEN (nghĩa là không có trạng thái con nào nữa). Để thực hiện
quá trình cập nhật này, ta hãy thực hiện quá trình duyệt theo chiều sâu
với điểm khởi đầu là Tk’. Duyệt đến đâu, ta cập nhật lại g của các
trạng thái đến đó ( dùng công thức g(T) = g(Cha(T)) +cost(Cha(T), T) ) và vì thế giá trị f’ của các trạng thái này cũng thay đổi theo.
Một lần nữa, xin nhắc lại rằng, bạn có
thể cho rằng tập OPEN lưu trữ các trạng thái "sẽ được xem xét đến sau"
còn tập CLOSE lưu trữ các trạng thái "đã được xét đến rồi".
Có thể bạn sẽ cảm thấy khá lúng túng
trước một thuật giải dài như thế. Vấn đề có lẽ sẻ trở nên sáng sủa hơn
khi bạn quan sát các bước giải bài toán tìm đường đi ngắn nhất trên đồ
thị bằng thuật giải A* sau đây.
Ví dụ minh họa hoạt động của thuật giải A*
Chúng ta sẽ minh họa hoạt động của thuật giải A* trong việc tìm kiếm đường đi ngắn nhất từ thành phố Arad đến thành phố Bucharest
của Romania. Bản đồ các thành phố của Romania được cho trong đồ thị
sau. Trong đó mỗi đỉnh của đồ thị của là một thành phố, giữa hai đỉnh có
cung nối nghĩa là có đường đi giữa hai thành phố tương ứng. Trọng số
của cung chính là chiều dài (tính bằng km) của đường đi nối hai thành
phố tương ứng, chiều dài theo đường chim bay một thành phố đến Bucharest
được cho trong bảng kèm theo.
Hình : Bảng đồ của Romania với khoảng cách đường tính theo km
Bảng : Khoảng cách đường chim bay từ một thành phố đến Bucharest.
Chúng ta sẽ chọn hàm h’ chính là khoảng cách đường chim bay cho trong bảng trên và hàm chi phí cost(Ti, Ti+1) chính là chiều dài con đường nối từ thành phố Ti và Ti+1.
Sau đây là từng bước hoạt động của thuật toán A* trong việc tìm đường đi ngắn nhất từ Arad đến Bucharest.
Ban đầu :
OPEN = {(Arad,g= 0,h’= 0,f’= 0)}
CLOSE = {}
Do trong OPEN chỉ chứa một thành phố duy
nhất nên thành phố này sẽ là thành phố tốt nhất. Nghĩa là Tmax = Arad.Ta
lấy Arad ra khỏi OPEN và đưa vào CLOSE.
OPEN = {}
CLOSE = {(Arad,g= 0,h’= 0,f’= 0)}
Từ Arad có thể đi đến được 3 thành phố là
Sibiu, Timisoara và Zerind. Ta lần lượt tính giá trị f’, g và h’ của 3
thành phố này. Do cả 3 nút mới tạo ra này chưa có nút cha nên ban đầu
nút cha của chúng đều là Arad.
h’(Sibiu) = 253
g(Sibiu) = g(Arad)+cost(Arad,Sibiu)
= 0+140= 140
f’(Sibiu) = g(Sibiu)+h’(Sibiu)
= 140+253 = 393
Cha(Sibiu) = Arad
h’(Timisoara) = 329
g(Timisoara) = g(Arad)+cost(Arad, Timisoara)
= 0+118= 118
f’(Timisoara) = g(Timisoara)+ h’(Timisoara)
= 118+329 = 447
Cha(Timisoara) = Arad
h’(Zerind) = 374
g(Zerind) = g(Arad)+cost(Arad, Zerind)
= 0+75= 75
f’(Zerind) = g(Zerind)+h’(Zerind)
= 75+374 = 449
Cha(Zerind) = Arad
Do cả 3 nút Sibiu, Timisoara, Zerind đều không có trong cả OPEN và CLOSE nên ta bổ sung 3 nút này vào OPEN.
OPEN = {(Sibiu,g= 140,h’= 253,f’= 393,Cha= Arad)
(Timisoara,g= 118,h’= 329,f’= 447,Cha= Arad)
(Zerind,g= 75,h’= 374,f’= 449,Cha= Arad)}
CLOSE = {(Arad,g= 0,h’= 0,f’= 0)}
Hình : Bước 1, nút được đóng ngoặc vuông (như [Arad]) là nút trong tập CLOSE, ngược lại là trong tập OPEN.
Trong tập OPEN, nút Sibiu là nút có giá
trị f’ nhỏ nhất nên ta sẽ chọn Tmax = Sibiu. Ta lấy Sibiu ra khỏi OPEN
và đưa vào CLOSE.
OPEN = {(Timisoara,g= 118,h’= 329,f’= 447,Cha= Arad)
(Zerind,g= 75,h’= 374,f’= 449,Cha= Arad)}
CLOSE = {(Arad,g= 0,h’= 0,f’= 0)
(Sibiu,g= 140,h’= 253,f’= 393,Cha= Arad)}
Từ Sibiu có thể đi đến được 4 thành phố
là : Arad, Fagaras, Oradea, Rimnicu. Ta lần lượt tính các giá trị g, h’,
f’ cho các nút này.
Nút Arad đã có trong CLOSE. Tuy nhiên, do
g(Arad) mới được tạo ra (có giá trị 280) lớn hơn g(Arad) lưu trong
CLOSE (có giá trị 0) nên ta sẽ không cập nhật lại giá trị g và f’ của
Arad lưu trong CLOSE. 3 nút còn lại : Fagaras, Oradea, Rimnicu đều không
có trong cả OPEN và CLOSE nên ta sẽ đưa 3 nút này vào OPEN, đặt cha của
chúng là Sibiu. Như vậy, đến bước này OPEN đã chứa tổng cộng 5 thành
phố.
OPEN = {(Timisoara,g= 118,h’= 329,f’= 447,Cha= Arad)
(Zerind,g= 75,h’= 374,f’= 449,Cha= Arad)
(Fagaras,g= 239,h’= 178,f’= 417,Cha= Sibiu)
(Oradea,g= 291,h’= 380,f’= 617,Cha= Sibiu)
(R.Vilcea,g= 220,h’= 193,f’= 413,Cha= Sibiu)}
CLOSE = {(Arad,g= 0,h’= 0,f’= 0)
(Sibiu,g= 140,h’= 253,f’= 393,Cha= Arad)}
Trong tập OPEN, nút R.Vilcea là nút có
giá trị f’ nhỏ nhất. Ta chọn Tmax = R.Vilcea. Chuyển R.Vilcea từ OPEN
sang CLOSE. Từ R.Vilcea có thể đi đến được 3 thành phố là Craiova,
Pitesti và Sibiu. Ta lần lượt tính giá trị f’, g và h’ của 3 thành phố
này.
h’(Sibiu) = 253
g(Sibiu) = g(R.Vilcea)+ cost(R.Vilcea,Sibiu)
= 220+80= 300
f’(Sibiu) = g(Sibiu)+h’(Sibiu)
= 300+253 = 553
h’(Craiova) = 160
g(Craiova) = g(R.Vilcea)+ cost(R.Vilcea, Craiova)
= 220+146= 366
f’(Craiova) = g(Fagaras)+h’(Fagaras)
= 366+160= 526
h’(Pitesti) = 98
g(Pitesti) = g(R.Vilcea)+ cost(R.Vilcea, Pitesti)
= 220+97 = 317
f’(Pitesti) = g(Oradea)+h’(Oradea)
= 317+98 = 415
Sibiu đã có trong tập CLOSE. Tuy nhiên,
do g’(Sibiu) mới (có giá trị là 553) lớn hơn g’(Sibiu) (có giá trị là
393) nên ta sẽ không cập nhật lại các giá trị của Sibiu được lưu trong
CLOSE. Còn lại 2 thành phố là Pitesti và Craiova đều không có trong cả
OPEN và CLOSE nên ta sẽ đưa nó vào OPEN và đặt cha của chúng là
R.Vilcea.
OPEN = {(Timisoara,g= 118,h’= 329,f’= 447,Cha= Arad)
Đến đây, trong tập OPEN, nút tốt nhất là
Pitesti, từ Pitesti ta có thể đi đến được R.Vilcea, Bucharest và
Craiova. Lấy Pitesti ra khỏi OPEN và đặt nó vào CLOSE. Thực hiện tiếp
theo tương tự như trên, ta sẽ không cập nhật giá trị f’, g của R.Vilcea
và Craiova lưu trong CLOSE. Sau khi tính toán f’, g của Bucharest, ta sẽ
đưa Bucharest vào tập OPEN, đặt Cha(Bucharest) = Pitesti.
Ở bước kế tiếp, ta sẽ chọn được Tmax =
Bucharest. Và như vậy thuật toán kết thúc (thực ra thì tại bước này, có
hai ứng cử viên là Bucharest và Fagaras vì đều cùng có f’= 417 , nhưng
vì Bucharest là đích nên ta sẽ ưu tiên chọn hơn).
Để xây dựng lại con đường đi từ Arad đến
Bucharest ta lần theo giá trị Cha được lưu trữ kèm với f’, g và h’ cho
đến lúc đến Arad.
Cha(Bucharest) = Pitesti
Cha(R.Vilcea) = Sibiu
Cha(Sibiu) = Arad
Vậy con đường đi ngắn nhất từ Arad đến Bucharest là Arad, Sibiu, R.Vilcea, Pitesti, Bucharest.
Trong ví dụ minh họa này, hàm h’ có chất
lượng khá tốt và cấu trúc đồ thị khá đơn giản nên ta gần như đi thẳng
đến đích mà ít phải khảo sát các con đường khác. Đây là một trường hợp
đơn giản, trong trường hợp này, thuật giải có dáng dấp của tìm kiếm
chiều sâu.
Đến đây, để minh họa một trường hợp phức
tạp hơn của thuật giải. Ta thử sửa đổi lại cấu trúc đồ thị và quan sát
hoạt động của thuật giải. Giả sử ta có thêm một thành phố tạm gọi là TP
và con đường giữa Sibiu và TP có chiều dài 100, con đường giữa TP và
Pitesti có chiều dài 60. Và khoảng cách đường chim bay từ TP đến
Bucharest là 174. Như vậy rõ ràng, con đường tối ưu đến Bucharest không
còn là Arad, Sibiu, R.Vilcea, Pitesti, Bucharest nữa mà là Arad, Sibiu,
TP, Pitesti, Bucharest.
Trong trường hợp này, chúng ta vẫn tiến
hành bước 1 như ở trên. Sau khi thực hiện hiện bước 2 (mở rộng Sibiu),
chúng ta có cây tìm kiếm như hình sau. Lưu ý là có thêm nhánh TP.
R.Vilcea vẫn có giá trị f’ thấp nhất. Nên ta mở rộng R.Vilcea như trường hợp đầu tiên.
Bước kế tiếp của trường hợp đơn giản là
mở rộng Pitesti để có được kết quả. Tuy nhiên, trong trường hợp này, TP
có giá trị f’ thấp hơn. Do đó, ta chọn mở rộng TP. Từ TP ta chỉ có 2
hướng đi, một quay lại Sibiu và một đến Pitesti. Để nhanh chóng, ta sẽ
không tính toán giá trị của Sibiu vì biết chắc nó sẽ lớn hơn giá trị
được lưu trữ trong CLOSE (vì đi ngược lại).
h’(Pitesti) = 98
g(Pitesti) = g(TP)+cost(TP, Pitesti)
= 240+75= 315
f’(Pitesti) = g(TP)+h’(Pitesti) = 315+98= 413
Pistestti đã xuất hiện trong tập OPEN và
g’(Pitesti) mới (có giá trị là 315) thấp hơn g’(Pitesti) cũ (có giá trị
317) nên ta phải cập nhật lại giá trị của f’,g, Cha của Pitesti lưu
trong OPEN. Sau khi cập nhật xong, tập OPEN và CLOSE sẽ như sau :
OPEN = {(Timisoara,g= 118,h’= 329,f’= 447,Cha= Arad)
(Zerind,g= 75,h’= 374,f’= 449,Cha= Arad)
(Fagaras,g= 239,h’= 178,f’= 417,Cha= Sibiu)
(Oradea,g= 291,h’= 380,f’= 617,Cha= Sibiu)
(Craiova,g= 366,h’= 160,f’= 526,Cha= R.Vilcea)
(Pitesti,g= 315,h’= 98,f’=413,Cha=TP) }
CLOSE = {(Arad,g= 0,h’= 0,f’= 0)
(Sibiu,g= 140,h’= 253,f’= 393,Cha= Arad)
(R.Vilcea,g= 220,h’= 193,f’= 413,Cha= Sibiu)
}
Đến đây ta thấy rằng, ban đầu thuật giải
chọn đường đi đến Pitesti qua R.Vilcea. Tuy nhiên, sau đó, thuật giải
phát hiện ra con đường đến Pitesti qua TP là tốt hơn nên nó sẽ sử dụng
con đường này. Đây chính là trường hợp 2.b.iii.2 trong thuật giải.
Bước sau, chúng ta sẽ chọn mở rộng
Pitesti như bình thường. Khi lần ngược theo thuộc tính Cha, ta sẽ có con
đường tối ưu là Arad, Sibiu, TP, Pitesti, Bucharest.
Bàn luận về A*
Đến đây, có lẽ bạn đã hiểu được thuật
giải này. Ta có một vài nhận xét khá thú vị về A*. Đầu tiên là vai trò
của g trong việc giúp chúng ta lựa chọn đường đi. Nó cho chúng ta khả
năng lựa chọn trạng thái nào để mở rộng tiếp theo, không chỉ dựa trên
việc trạng thái đó tốt như thế nào (thể hiện bởi giá trị h’) mà còn trên
cơ sở con đường từ trạng thái khởi đầu đến trạng thái hiện tại đó tốt
ra sao. Điều này sẽ rất hữu ích nếu ta không chỉ quan tâm việc tìm ra
lời giải hay không mà còn quan tâm đến hiệu quả của con đường dẫn đến
lời giải. Chẳng hạn như trong bài toán tìm đường đi ngắn nhất giữa hai
điểm. Bên cạnh việc tìm ra đường đi giữa hai điểm, ta còn phải tìm ra
một con đường ngắn nhất. Tuy nhiên, nếu ta chỉ quan tâm đến việc tìm
được lời giải (mà không quan tâm đến hiệu quả của con đường đến lời
giải), chúng ta có thể đặt g=0 ở mọi trạng thái. Điều này sẽ giúp ta
luôn chọn đi theo trạng thái có vẻ gần nhất với trạng thái kết thúc (vì
lúc này f’ chỉ phụ thuộc vào h’ là hàm ước lượng "khoảng cách" gần nhất
để tới đích). Lúc này thuật giải có dáng dấp của tìm kiếm chiều sâu theo
nguyên lý hướng đích kết hợp với lần ngược.
Ngược lại, nếu ta muốn tìm ra kết quả với
số bước ít nhất (đạt được trạng thái đích với số trạng thái trung gian
ít nhất), thì ta đặt giá trị để đi từ một trạng thái đến các trạng thái
con kế tiếp của nó luôn là hằng số, thường là 1 Nghĩa đặt cost(Ti-1,
Ti) = 1 (và vẫn dùng một hàm ước lượng h’ như bình thường). Còn ngược
lại, nếu muốn tìm chi phí rẻ nhất thì ta phải đặt giá trị hàm cost chính
xác (phản ánh đúng ghi phí thực sự).
Đến đây, chắc bạn đọc đã có thể bắt đầu
cảm nhận được rằng thuật giải A* không hoàn toàn là một thuật giải tối
ưu tuyệt đối. Nói đúng hơn, A* chỉ là một thuật giải linh động và cho
chúng ta khá nhiều tùy chọn. Tùy theo bài toán mà ta sẽ có một bộ thông
số thích hợp cho A* để thuật giải hoạt động hiệu quả nhất.
Điểm quan tâm thứ hai là về giá trị h’ –
sự ước lượng khoảng cách (chi phí) từ một trạng thái đến trạng thái
đích. Nếu h’ chính là h (đánh giá tuyệt đối chính xác) thì A* sẽ đi một
mạch từ trạng thái đầu đến trạng thái kết thúc mà không cần phải thực
hiện bất kỳ một thao tác đổi hướng nào!. Dĩ nhiên, trên thực tế, hầu như
chẳng bao giờ ta tìm thấy một đánh giá tuyệt đối chính xác. Tuy nhiên,
điều đáng quan tâm ở đây là h’ được ước lượng càng gần với h, quá trình
tìm kiếm càng ít bị sai sót, ít bị rẽ vào những nhánh cụt hơn. Hay nói
ngắn gọn là càng nhanh chóng tìm thấy lời giải hơn.
Nếu h’ luôn bằng 0 ở mọi trạng thái (trở
về thuật giải AT) thì quá trình tìm kiếm sẽ được điều khiển hoàn toàn
bởi giá trị g. Nghĩa là thuật giải sẽ chọn đi theo những hướng mà sẽ tốn
ít chi phí/bước đi nhất (chi phí tính từ trạng thái đầu tiên đến trạng
thái hiện đang xét) bất chấp việc đi theo hướng đó có khả năng dẫn đến
lời giải hay không. Đây chính là hình ảnh của nguyên lý tham lam
(Greedy).
Nếu chi phí từ trạng thái sang trạng thái
khác luôn là hằng số (dĩ nhiên lúc này h’ luôn bằng 0) thì thuật giải
A* trở thành thuật giải tìm kiếm theo chiều rộng! Lý do là vì tất cả
những trạng thái cách trạng thái khởi đầu n bước đều có cùng giá trị g
và vì thế đều có cùng f’ và giá trị này sẽ nhỏ hơn tất cả các trạng thái
cách trạng thái khởi đầu n+1 bước. Và nếu g luôn bằng 0 và h’ cũng luôn
bằng 0, mọi trạng thái đang xét đều tương đương nhau. Ta chỉ có thể
chọn bằng trạng thái kế tiếp bằng ngẫu nhiên !
Còn nếu như h’ không thể tuyệt đối chính
xác (nghĩa là không bằng đúng h) và cũng không luôn bằng 0 thì sao? Có
điều gì thú vị về cách xử lý của quá trình tìm kiếm hay không? Câu trả
lời là có. Nếu như bằng một cách nào đó, ta có thể chắc chắn rằng, ước
lượng h’ luôn nhỏ hơn h (đối với mọi trạng thái) thì thuật giải A* sẽ
thường tìm ra con đường tối ưu (xác định bởi g) để đi đến đích, nếu
đường dẫn đó tồn tại và quá trình tìm kiếm sẽ ít khi bị sa lầy vào những
con đường quá dở. Còn nếu vì một lý do nào đó, ước lượng h’ lại lớn hơn
h thì thuật giải sẽ dễ dàng bị vướng vào những hướng tìm kiếm vô ích.
Thậm chí nó lại có khuynh hướng tìm kiếm ở những hướng đi vô ích trước!
Điều này có thể thấy một cách dễ dàng từ vài ví dụ.
Xét trường hợp được trình bày trong hình
sau. Giả sử rằng tất cả các cung đều có giá trị 1. G là trạng thái đích.
Khởi đầu, OPEN chỉ chứa A, sau đó A được mở rộng nên B, C, D sẽ được
đưa vào OPEN (hình vẽ mô tả trạng thái 2 bước sau đó, khi B và E đã được
mở rộng). Đối với mỗi nút, con số đầu tiên là giá trị h’, con số kế
tiếp là g. Trong ví dụ này, nút B có f’ thấp nhất là 4 = h’+g = 3 + 1 ,
vì thế nó được mở rộng trước tiên. Giả sử nó chỉ có một nút con tiếp
theo là E và h’(E) = 3, do E các A hai cung nên g(E) = 2 suy ra f’(E) =
5, giống như f’(C). Ta chọn mở rộng E kế tiếp. Giả sử nó cũng chỉ có duy
nhất một con kế tiếp là F và h’(F) cũng bằng 3. Rõ ràng là chúng ta
đang di chuyển xuống và không phát triển rộng. Nhưng f’(F) = 6 lớn hơn
f’(D). Do đó, chúng ta sẽ mở rộng C tiếp theo và đạt đến trạng thái
đích. Như vậy, ta thấy rằng do đánh giá thấp h(B) nên ta đã lãng phí một
số bước (E,F), nhưng cuối cùng ta cùng phát hiện ra B khác xa với điều
ta mong đợi và quay lại để thử một đường dẫn khác.
Hình : h’ đánh giá thấp h
Bây giờ hãy xét trường hợp ở hình tiếp
theo. Chúng ta cũng mở rộng B ở bước đầu tiên và E ở bước thứ hai. Kế
tiếp là F và cuối cùng G, cho đường dẫn kết thúc có độ dài là 4. Nhưng
giả sử có đường dẫn trực tiếp từ D đến một lời giải có độ dài h thực sự là 2 thì chúng ta sẽ không bao giờ
tìm được đường dẫn này (tuy rằng ta có thể tìm thấy lời giải). Bởi vì
việc đánh giá quá cao h’(D), chúng ta sẽ làm cho D trông dở đến nỗi mà
ta phải tìm một đường đi khác – đến một lời giải tệ hơn - mà không bao
giờ nghĩ đến việc mở rộng D. Nói chung, nếu h’ đánh giá cao h thì A* sẽ
có thể không thể tìm ra đường dẫn tối ưu đến lời giải (nếu như có nhiều
đường dẫn đến lời giải). Một câu hỏi thú vị là "Liệu có một nguyên tắc chung nào giúp chúng ta đưa ra một cách ước lượng h’ không bao giờ đánh giá cao h hay không?".
Câu trả lời là "hầu như không", bởi vì đối với hầu hết các vấn đề thực
ta đều không biết h. Tuy nhiên, cách duy nhất để bảo đảm h’ không bao
giờ đánh giá cao h là đặt h’ bằng 0 !
Hình : h’ đánh giá cao h
Đến đây chúng ta đã kết thúc việc bàn
luận về thuật giải A*, một thuật giải linh động, tổng quát, trong đó hàm
chứa cả tìm kiếm chiều sâu, tìm kiếm chiều rộng và những nguyên lý
Heuristic khác. Chính vì thế mà người ta thường nói, A* chính là thuật
giải tiêu biểu cho Heuristic.
A* rất linh động nhưng vẫn gặp một khuyết
điểm cơ bản – giống như chiến lược tìm kiếm chiều rộng – đó là tốn khá
nhiều bộ nhớ để lưu lại những trạng thái đã đi qua – nếu chúng ta muốn
nó chắc chắn tìm thấy lời giải tối ưu. Với những không gian tìm kiếm lớn
nhỏ thì đây không phải là một điểm đáng quan tâm. Tuy nhiên, với những
không gian tìm kiếm khổng lồ (chẳng hạn tìm đường đi trên một ma trận
kích thước cỡ 106 x 106)
thì không gian lưu trữ là cả một vấn đề hóc búa. Các nhà nghiên cứu đã
đưa ra khá nhiều các hướng tiếp cận lai để giải quyết vấn đề này. Chúng
ta sẽ tìm hiểu một số phương án nhưng quan trọng nhất, ta cần phải nắm
rõ vị trí của A* so với những thuật giải khác.
Một trong những vấn đề khá quan trọng của
logic mệnh đề là chứng minh tính đúng đắn của phép suy diễn (a → b).
Đây cũng chính là bài toán chứng minh thường gặp trong toán học.
Rõ ràng rằng với hai phép suy luận cơ bản
của logic mệnh đề (Modus Ponens, Modus Tollens) cộng với các phép biến
đổi hình thức, ta cũng có thể chứng minh được phép suy diễn. Tuy nhiên,
thao tác biến đối hình thức là rất khó cài đặt được trên máy tính. Thậm
chí điều này còn khó khăn với cả con người!
Với công cụ máy tính, bạn có thể cho rằng
ta sẽ dễ dàng chứng minh được mọi bài toán bằng một phương pháp "thô
bạo" là lập bảng chân trị . Tuy về lý thuyết, phương pháp lập bảng chân
trị luôn cho được kết quả cuối cùng nhưng độ phức tạp của phương pháp
này là quá lớn, O(2n) với n là số biến mệnh đề. Sau đây chúng ta sẽ nghiên cứu hai phương pháp chứng minh mệnh đề với độ phức tạp chỉ có O(n).
Thuật giải Vương Hạo
Thuật giải Robinson
Thuật giải này hoạt động dựa trên phương pháp chứng minh phản chứng.
Phương pháp chứng minh phản chứng
Chứng minh phép suy luận (a → b) là đúng (với a là giả thiết, b là kết luận).
Phản chứng : giả sử b sai suy ra b là đúng.
Bài toán được chứng minh nếu a đúng và b đúng sinh ra một mâu thuẫn.
Ví dụ : Chứng minh rằng
B4 : Có tất cả 6 mệnh đề nhưng chưa có mệnh đề nào đối ngẫu nhau.
B5 : ⇒tuyển một cặp mệnh đề (chọn hai mệnh đề có biến đối ngẫu). Chọn hai mệnh đề đầu :
Qua các phần trước chúng ta tìm hiểu tổng
quan về ý tưởng của thuật giải Heuristic (nguyên lý Greedy và sắp thứ
tự). Trong mục này, chúng ta sẽ đi sâu vào tìm hiểu một số kỹ thuật tìm
kiếm Heuristic – một lớp bài toán rất quan trọng và có nhiều ứng dụng
trong thực tế.
Cấu trúc chung của bài toán tìm kiếm
Để tiện lợi cho việc trình bày, ta hãy
dành chút thời gian để làm rõ hơn "đối tượng" quan tâm của chúng ta
trong mục này. Một cách chung nhất, nhiều vấn đề-bài toán phức tạp đều
có dạng "tìm đường đi trong đồ thị" hay nói một cách hình thức hơn là
"xuất phát từ một đỉnh của một đồ thị, tìm đường đi hiệu quả nhất đến
một đỉnh nào đó". Một phát biểu khác thường gặp của dạng bài toán này là
:
Cho trước hai trạng thái T0 và TG hãy xây dựng chuỗi trạng thái T0, T1, T2, ..., Tn-1, Tn = TG sao cho :
thỏa mãn một điều kiện cho trước (thường là nhỏ nhất).
Trong đó, Ti thuộc tập hợp S (gọi là
không gian trạng thái – state space) bao gồm tất cả các trạng thái có
thể có của bài toán và cost(Ti-1, Ti) là chi phí để biến đổi từ trạng thái Ti-1 sang trạng thái Ti. Dĩ nhiên, từ một trạng thái Ti ta có nhiều cách để biến đổi sang trạng thái Ti+1. Khi nói đến một biến đổi cụ thể từ Ti-1 sang Ti ta sẽ dùng thuật ngữ hướng đi (với ngụ ý nói về sự lựa chọn).
Hình : Mô hình chung của các vấn đề-bài
toán phải giải quyết bằng phương pháp tìm kiếm lời giải. Không gian tìm
kiếm là một tập hợp trạng thái - tập các nút của đồ thị. Chi phí cần
thiết để chuyển từ trạng thái T này sang trạng thái Tkđược biểu diễn dưới dạng các con số nằm trên cung nối giữa hai nút tượng trưng cho hai trạng thái.
Đa số các bài toán thuộc dạng mà chúng ta
đang mô tả đều có thể được biểu diễn dưới dạng đồ thị. Trong đó, một
trạng thái là một đỉnh của đồ thị. Tập hợp S bao gồm tất cả các trạng
thái chính là tập hợp bao gồm tất cả đỉnh của đồ thị. Việc biến đổi từ
trạng thái Ti-1 sang trạng thái Ti là việc đi từ đỉnh đại diện cho Ti-1 sang đỉnh đại diện cho Titheo cung nối giữa hai đỉnh này.
Tìm kiếm chiều sâu và tìm kiếm chiều rộng
Để bạn đọc có thể hình dung một cách cụ
thể bản chất của thuật giải Heuristic, chúng ta nhất thiết phải nắm vững
hai chiến lược tìm kiếm cơ bản là tìm kiếm theo chiều sâu (Depth First
Search) và tìm kiếm theo chiều rộng (Breath First Search). Sở dĩ chúng
ta dùng từ chiến lược mà không phải là phương pháp là bởi vì trong thực
tế, người ta hầu như chẳng bao giờ vận dụng một trong hai kiểm tìm kiếm
này một cách trực tiếp mà không phải sửa đổi gì.
Tìm kiếm chiều sâu (Depth-First Search)
Trong tìm kiếm theo chiều sâu, tại trạng
thái (đỉnh) hiện hành, ta chọn một trạng thái kế tiếp (trong tập các
trạng thái có thể biến đổi thành từ trạng thái hiện tại) làm trạng thái
hiện hành cho đến lúc trạng thái hiện hành là trạng thái đích. Trong
trường hợp tại trạng thái hiện hành, ta không thể biến đổi thành trạng
thái kế tiếp thì ta sẽ quay lui (back-tracking) lại trạng thái trước
trạng thái hiện hành (trạng thái biến đổi thành trạng thái hiện hành) để
chọn đường khác. Nếu ở trạng thái trước này mà cũng không thể biến đổi
được nữa thì ta quay lui lại trạng thái trước nữa và cứ thế. Nếu đã quay
lui đến trạng thái khởi đầu mà vẫn thất bại thì kết luận là không có
lời giải. Hình ảnh sau minh họa hoạt động của tìm kiếm theo chiều sâu.
Hình : Hình ảnh của tìm kiếm chiều sâu.
Nó chỉ lưu ý "mở rộng" trạng thái được chọn mà không "mở rộng" các trạng
thái khác (nút màu trắng trong hình vẽ).
Tìm kiếm chiều rộng (Breath-First Search)
Ngược lại với tìm kiếm theo kiểu chiều
sâu, tìm kiếm chiều rộng mang hình ảnh của vết dầu loang. Từ trạng thái
ban đầu, ta xây dựng tập hợp S bao gồm các trạng thái kế tiếp (mà từ
trạng thái ban đầu có thể biến đổi thành). Sau đó, ứng với mỗi trạng
thái Tk trong tập S, ta xây dựng tập Sk bao gồm các trạng thái kế tiếp
của Tkrồi lần lượt bổ sung các Sk vào S. Quá
trình này cứ lặp lại cho đến lúc S có chứa trạng thái kết thúc hoặc S
không thay đổi sau khi đã bổ sung tất cả Sk.
Hình : Hình ảnh của tìm kiếm chiều rộng. Tại một bước, mọi trạng thái đều được mở rộng, không bỏ sót trạng thái nào.
Chiều sâu
Chiều rộng
Tính hiệu quả
Hiệu quả khi lời giải nằm sâu trong cây tìm kiếm và có một phương án
chọn hướng đi chính xác. Hiệu quả của chiến lược phụ thuộc vào phương
án chọn hướng đi. Phương án càng kém hiệu quả thì hiệu quả của chiến
lược càng giảm. Thuận lợi khi muốn tìm chỉ một lời giải.
Hiệu quả khi lời giải nằm gần gốc của cây tìm kiếm. Hiệu quả của
chiến lược phụ thuộc vào độ sâu của lời giải. Lời giải càng xa gốc thì
hiệu quả của chiến lược càng giảm. Thuận lợi khi muốn tìm nhiều lời
giải.
Lượng bộ nhớ sử dụng để lưu trữ các trạng thái
Chỉ lưu lại các trạng thái chưa xét đến.
Phải lưu toàn bộ các trạng thái.
Trường hợp xấu nhất
Vét cạn toàn bộ
Vét cạn toàn bộ.
Trường hợp tốt nhất
Phương án chọn hướng đi tuyệt đối chính xác. Lời giải được xác định một cách trực tiếp.
Vét cạn toàn bộ.
Tìm kiếm chiều sâu
và tìm kiếm chiều rộng đều là các phương pháp tìm kiếm có hệ thống và
chắc chắn tìm ra lời giải. Tuy nhiên, do bản chất là vét cạn nên với
những bài toán có không gian lớn thì ta không thể dùng hai chiến lược
này được. Hơn nữa, hai chiến lược này đều có tính chất "mù quáng" vì
chúng không chú ý đến những thông tin (tri thức) ở trạng thái hiện thời
và thông tin về đích cần đạt tới cùng mối quan hệ giữa chúng. Các tri
thức này vô cùng quan trọng và rất có ý nghĩa để thiết kế các thuật giải
hiệu quả hơn mà ta sắp sửa bàn đến.
Tìm kiếm leo đồi
Leo đồi đơn giản
Tìm kiếm leo đồi theo đúng nghĩa, nói
chung, thực chất chỉ là một trường hợp đặc biệt của tìm kiếm theo chiều
sâu nhưng không thể quay lui. Trong tìm kiếm leo đồi, việc lựa chọn
trạng thái tiếp theo được quyết định dựa trên một hàm Heuristic.
Hàm Heuristic là gì ?
Thuật ngữ "hàm Heuristic" muốn nói lên
điều gì? Chẳng có gì ghê gớm. Bạn đã quen với nó rồi! Đó đơn giản chỉ là
một ước lượng về khả năng dẫn đến lời giải tính từ trạng thái đó
(khoảng cách giữa trạng thái hiện tại và trạng thái đích). Ta sẽ quy ước
gọi hàm này là h trong suốt giáo trình này. Đôi lúc ta cũng đề cập đến
chi phí tối ưu thực sự từ một trạng thái dẫn đến lời giải. Thông thường,
giá trị này là không thể tính toán được (vì tính được đồng nghĩa là đã
biết con đường đến lời giải !) mà ta chỉ dùng nó như một cơ sở để suy
luận về mặt lý thuyết mà thôi ! Hàm h, ta quy ước rằng, luôn trả ra kết
quả là một số không âm. Để bạn đọc thực sự nắm được ý nghĩa của hai hàm
này, hãy quan sát hình sau trong đó minh họa chi phí tối ưu thực sự và
chi phí ước lượng.
Hình Chi phí ước lượng h’ = 6 và chi phí tối ưu thực sự h = 4+5 = 9 (đi theo đường 1-3-7)
Bạn đang ở trong một thành phố xa lạ mà
không có bản đồ trong tay và ta muốn đi vào khu trung tâm? Một cách suy
nghĩ đơn giản, chúng ta sẽ nhắm vào hướng những tòa cao ốc của khu trung
tâm!
Tư tưởng
1) Nếu trạng thái bắt đầu cũng là trạng
thái đích thì thoát và báo là đã tìm được lời giải. Ngược lại, đặt trạng
thái hiện hành (Ti) là trạng thái khởi đầu (T0)
2) Lặp lại cho đến khi đạt đến trạng thái
kết thúc hoặc cho đến khi không tồn tại một trạng thái tiếp theo hợp lệ
(Tk) của trạng thái hiện hành :
a. Đặt Tk là một trạng thái tiếp theo hợp lệ của trạng thái hiện hành Ti.
b. Đánh giá trạng thái Tk mới :
b.1. Nếu là trạng thái kết thúc thì trả về trị này và thoát.
b.2. Nếu không phải là trạng thái kết thúc nhưng tốt hơn trạng thái hiện hành thì cập nhật nó thành trạng thái hiện hành.
b.3. Nếu nó không tốt hơn trạng thái hiện hành thì tiếp tục vòng lặp.
Mã giả
Ti:= T0; Stop :=FALSE;
WHILE Stop=FALSE DO BEGIN
IF Ti TG THEN BEGIN
<tìm được kết quả >; Stop:=TRUE;
END;
ELSE BEGIN
Better:=FALSE;
WHILE (Better=FALSE) AND (STOP=FALSE) DO BEGIN
IF <không tồn tại trạng thái kế tiếp hợp lệ của Ti> THEN BEGIN
<không tìm được kết quả >; Stop:=TRUE; END;
ELSE BEGIN
Tk := <một trạng thái kế tiếp hợp lệ của Ti>;
IF <h(Tk) tốt hơn h(Ti)> THEN BEGIN
Ti :=Tk; Better:=TRUE;
END;
END;
END; {WHILE}
END; {ELSE}
END;{WHILE}
Mệnh đề "h’(Tk) tốt hơn h’(Ti)" nghĩa là
gì? Đây là một khái niệm chung chung. Khi cài đặt thuật giải, ta phải
cung cấp một định nghĩa tường minh về tốt hơn. Trong một số trường hợp,
tốt hơn là nhỏ hơn : h’(Tk) < h’(Ti); một số trường hợp khác tốt hơn
là lớn hơn h’(Tk) > h’(Ti)...Chẳng hạn, đối với bài toán tìm đường đi
ngắn nhất giữa hai điểm. Nếu dùng hàm h’ là hàm cho ra khoảng cách theo
đường chim bay giữa vị trí hiện tại (trạng thái hiện tại) và đích đến
(trạng thái đích) thì tốt hơn nghĩa là nhỏ hơn.
Vấn đề cần làm rõ kế tiếp là thế nào là
<một trạng thái kế tiếp hợp lệ của Ti>? Một trạng thái kế tiếp hợp
lệ là trạng thái chưa được xét đến. Giả sử h của trạng thái hiện tại Ti
có giá trị là h(Ti) = 1.23 và từ Ti ta có thể biến đổi sang một trong 3
trạng thái kế tiếp lần lượt là Tk1, Tk2, Tk3 với giá trị các hàm h tương ứng là h(Tk1) = 1.67, h(Tk2) = 2.52, h’(Tk3) = 1.04. Đầu tiên, Tk sẽ được gán bằng Tk1, nhưng vì h’(Tk) = h’(Tk1) > h’(Ti) nên Tk không được chọn. Kế tiếp là Tk sẽ được gán bằng Tk2 và cũng không được chọn. Cuối cùng thì Tk3 được chọn. Nhưng giả sử h’(Tk3) = 1.3 thì cả Tk3
cũng không được chọn và mệnh đề <không thể sinh ra trạng thái kế
tiếp của Ti> sẽ có giá trị TRUE. Giải thích này có vẻ hiển nhiên
nhưng có lẽ cần thiết để tránh nhầm lẫn cho bạn đọc.
Để thấy rõ hoạt động của thuật giải leo
đồi. Ta hãy xét một bài toán minh họa sau. Cho 4 khối lập phương giống
nhau A, B, C, D. Trong đó các mặt (M1), (M2), (M3), (M4), (M5), (M6) có
thể được tô bằng 1 trong 6 màu (1), (2), (3), (4), (5), (6). Ban đầu các
khối lập phương được xếp vào một hàng. Mỗi một bước, ta chỉ được xoay
một khối lập phương quanh một trục (X,Y,Z) 900
theo chiều bất kỳ (nghĩa là ngược chiều hay thuận chiều kim đồng hồ cũng
được). Hãy xác định số bước quay ít nhất sao cho tất cả các mặt của
khối lập phương trên 4 mặt của hàng là có cùng màu như hình vẽ.
Hình : Bài toán 4 khối lập phương
Để giải quyết vấn đề, trước hết ta cần
định nghĩa một hàm G dùng để đánh giá một tình trạng cụ thể có phải là
lời giải hay không? Bạn đọc có thể dễ dàng đưa ra một cài đặt của hàm G
như sau :
IF (Gtrái + Gphải + Gtrên + Gdưới + Gtrước + Gsau) = 16 THEN
G:=TRUE
ELSE
G:=FALSE;
Trong đó, Gphảilà
số lượng các mặt có cùng màu của mặt bên phải của hàng. Tương tự cho
Gtrái, Gtrên, Ggiữa, Gtrước, Gsau. Tuy nhiên, do các khối lập phương
A,B,C,D là hoàn toàn tương tự nhau nên tương quan giữa các mặt của mỗi
khối là giống nhau. Do đó, nếu có 2 mặt không đối nhau trên hàng đồng
màu thì 4 mặt còn lại của hàng cũng đồng màu. Từ đó ta chỉ cần hàm G
được định nghĩa như sau là đủ :
IF Gphải + Gdưới = 8 THEN
G:=TRUE
ELSE
G:=FALSE;
Hàm h (ước lượng khả năng dẫn đến lời giải của một trạng thái) sẽ được định nghĩa như sau :
h = Gtrái+ Gphải+ Gtrên+ Gdưới
Bài toán này đủ đơn giản để thuật giải leo đồi có thể hoạt động tốt. Tuy nhiên, không phải lúc nào ta cũng may mắn như thế!
Đến đây, có thể chúng ta sẽ nảy sinh một ý
tưởng. Nếu đã chọn trạng thái tốt hơn làm trạng thái hiện tại thì tại
sao không chọn trạng thái tốt nhất ? Như vậy, có lẽ ta sẽ nhanh chóng
dẫn đến lời giải hơn! Ta sẽ bàn luận về vấn đề: "liệu cải tiến này có
thực sự giúp chúng ta dẫn đến lời giải nhanh hơn hay không?" ngay sau
khi trình bày xong thuật giải leo đồi dốc đứng.
Leo đồi dốc đứng
Về cơ bản, leo đồi dốc đứng cũng giống
như leo đồi, chỉ khác ở điểm là leo đồi dốc đứng sẽ duyệt tất cả các
hướng đi có thể và chọn đi theo trạng thái tốt nhất trong số các trạng
thái kế tiếp có thể có (trong khi đó leo đồi chỉ chọn đi theo trạng thái
kế tiếp đầu tiên tốt hơn trạng thái hiện hành mà nó tìm thấy).
Tư tưởng
1) Nếu trạng thái bắt đầu cũng là trạng
thái đích thì thoát và báo là đã tìm được lời giải. Ngược lại, đặt trạng
thái hiện hành (Ti) là trạng thái khởi đầu (T0)
2) Lặp lại cho đến khi đạt đến trạng thái
kết thúc hoặc cho đến khi (Ti) không tồn tại một trạng thái kế tiếp
(Tk) nào tốt hơn trạng thái hiện tại (Ti)
a) Đặt S bằng tập tất cả trạng thái kế tiếp có thể có của Ti và tốt hơn Ti.
b) Xác định Tkmax là trạng thái tốt nhất trong tập S
Đặt Ti = Tkmax
Mã giả
Ti:= T0;
Stop :=FALSE;
WHILE Stop=FALSE DO BEGIN
IF Ti TG THEN BEGIN
<tìm được kết quả >;
STOP :=TRUE;
END;
ELSE BEGIN
Best:=h’(Ti);
Tmax:= Ti;
WHILE <tồn tại trạng thái kế tiếp hợp lệ của Ti> DO BEGIN
Tk := <một trạng thái kế tiếp hợp lệ của Ti>;
IF <h’(Tk) tốt hơn Best> THEN BEGIN
Best :=h’(Tk);
Tmax:= Tk;
END;
END;
IF (Best>Ti) THEN
Ti:= Tmax;
ELSE BEGIN
<không tìm được kết quả >;
STOP:=TRUE;
END;
END; {ELSE IF}
END;{WHILE STOP}
Đánh giá
So với leo đồi đơn giản, leo đồi dốc đứng
có ưu điểm là luôn luôn chọn hướng có triển vọng nhất để đi. Liệu điều
này có đảm bảo leo đồi dốc đứng luôn tốt hơn leo đồi đơn giản không? Câu
trả lời là không. Leo đồi dốc đứng chỉ tốt hơn leo đồi đơn giản trong
một số trường hợp mà thôi. Để chọn ra được hướng đi tốt nhất, leo đồi
dốc đứng phải duyệt qua tất cả các hướng đi có thể có tại trạng thái
hiện hành. Trong khi đó, leo đồi đơn giản chỉ chọn đi theo trạng thái
đầu tiên tốt hơn (so với trạng thái hiện hành) mà nó tìm ra được. Do đó,
thời gian cần thiết để leo đồi dốc đứng chọn được một hướng đi sẽ lớn
hơn so với leo đồi đơn giản. Tuy vậy, do lúc nào cũng chọn hướng đi tốt
nhất nên leo đồi dốc đứng thường sẽ tìm đến lời giải sau một số bước ít
hơn so với leo đồi đơn giản. Nói một cách ngắn gọn, leo đồi dốc đứng sẽ
tốn nhiều thời gian hơn cho một bước nhưng lại đi ít bước hơn; còn leo
đồi đơn giản tốn ít thời gian hơn cho một bước đi nhưng lại phải đi
nhiều bước hơn. Đây chính là yếu tố được và mất giữa hai thuật giải nên
ta phải cân nhắc kỹ lưỡng khi lựa chọn thuật giải.
Cả hai phương pháp leo núi đơn giản và
leo núi dốc đứng đều có khả năng thất bại trong việc tìm lời giải của
bài toán mặc dù lời giải đó thực sự hiện hữu. Cả hai giải thuật đều có
thể kết thúc khi đạt được một trạng thái mà không còn trạng thái nào tốt
hơn nữa có thể phát sinh nhưng trạng thái này không phải là trạng thái
đích. Điều này sẽ xảy ra nếu chương trình đạt đến một điểm cực đại địa
phương, một đoạn đơn điệu ngang.
Điểm cực đại địa phương (a local maximum)
: là một trạng thái tốt hơn tất cả lân cận của nó nhưng không tốt hơn
một số trạng thái khác ở xa hơn. Nghĩa là tại một điểm cực đại địa
phương, mọi trạng thái trong một lân cận của trạng thái hiện tại đều xấu
hơn trạng thái hiện tại. Tuy có dáng vẻ của lời giải nhưng các cực đại
địa phương không phải là lời giải thực sự. Trong trường hợp này, chúng
được gọi là những ngọn đồi thấp.
Đoạn đơn điệu ngang (a plateau) : là một
vùng bằng phẳng của không gian tìm kiếm, trong đó, toàn bộ các trạng
thái lân cận đều có cùng giá trị.
Hình : Các tình huống khó khăn cho tìm kiếm leo đèo.
Để đối phó với các các điểm này, người ta
đã đưa ra một số giải pháp. Ta sẽ tìm hiểu 2 trong số các giải pháp
này. Những giải này, không thực sự giải quyết trọn vẹn vấn đề mà chỉ là
một phương án cứu nguy tạm thời mà thôi.
Phương án đầu tiên là kết hợp leo đồi và
quay lui. Ta sẽ quay lui lại các trạng thái trước đó và thử đi theo
hướng khác. Thao tác này hợp lý nếu tại các trạng thái trước đó có một
hướng đi tốt mà ta đã bỏ qua trước đó. Đây là một cách khá hay để đối
phó với các điểm cực đại địa phương. Tuy nhiên, do đặc điểm của leo đồi
là "bước sau cao hơn bước trước" nên phương án này sẽ thất bại khi ta
xuất phát từ một điểm quá cao hoặc xuất phát từ một đỉnh đồi mà để đến
được lời giải cần phải đi qua một "thung lũng" thật sâu như trong hình
sau.
Hình : Một trường hợp thất bại của leo đèo kết hợp quay lui.
Cách thứ hai là thực hiện một bước nhảy
vọt theo hướng nào đó để thử đến một vùng mới của không gian tìm kiếm.
Nôm na là "bước" liên tục nhiều "bước" (chẳng hạn 5,7,10, …) mà tạm thời
"quên" đi việc kiểm tra "bước sau cao hơn bước trước". Tiếp cận có vẻ
hiệu quả khi ta gặp phải một đoạn đơn điệu ngang. Tuy nhiên, nhảy vọt
cũng có nghĩa là ta đã bỏ qua cơ hội để tiến đến lời giải thực sự. Trong
trường hợp chúng ta đang đứng khá gần lời giải, việc nhảy vọt sẽ đưa
chúng ta sang một vị trí hoàn toàn xa lạ, mà từ đó, có thể sẽ dẫn chúng
ta đến một rắc rối kiểu khác. Hơn nữa, số bước nhảy là bao nhiêu và nhảy
theo hướng nào là một vấn đề phụ thuộc rất nhiều vào đặc điểm không
gian tìm kiếm của bài toán.
Hình Một trường hợp khó khăn cho phương án "nhảy vọt".
Leo núi là một phương pháp cục bộ bởi vì
nó quyết định sẽ làm gì tiếp theo dựa vào một đánh giá về trạng thái
hiện tại và các trạng thái kế tiếp có thể có (tốt hơn trạng thái hiện
tại, trạng thái tốt nhất tốt hơn trạng thái hiện tại) thay vì phải xem
xét một cách toàn diện trên tất cả các trạng thái đã đi qua. Thuận lợi
của leo núi là ít gặp sự bùng nổ tổ hợp hơn so với các phương pháp toàn
cục. Nhưng nó cũng giống như các phương pháp cục bộ khác ở chỗ là không
chắc chắn tìm ra lời giải trong trường hợp xấu nhất.
Một lần nữa, ta khẳng định lại vai trò
quyết định của hàm Heuristic trong quá trình tìm kiếm lời giải. Với cùng
một thuật giải (như leo đồi chẳng hạn), nếu ta có một hàm Heuristic tốt
hơn thì kết quả sẽ được tìm thấy nhanh hơn. Ta hãy xét bài toán về các
khối được trình bày ở hình sau. Ta có hai thao tác biến đổi là:
+ Lấy một khối ở đỉnh một cột bất kỳ và
đặt nó lên một chỗ trống tạo thành một cột mới. Lưu ý là chỉ có thể tạo
ra tối đa 2 cột mới.
+ Lấy một khối ở đỉnh một cột và đặt nó lên đỉnh một cột khác
Hãy xác định số thao tác ít nhất để biến đổi cột đã cho thành cột kết quả.
Hình : Trạng thái khởi đầu và trạng thái kết thúc
Giả sử ban đầu ta dùng một hàm Heuristic đơn giản như sau :
H1 : Cộng 1 điểm
cho mỗi khối ở vị trí đúng so với trạng thái đích. Trừ 1 điểm cho mỗi
khối đặt ở vị trí sai so với trạng thái đích.
Dùng hàm này, trạng thái kết thúc sẽ có
giá trị là 8 vì cả 8 khối đều được đặt ở vị trí đúng. Trạng thái khởi
đầu có giá trị là 4 (vì nó có 1 điểm cộng cho các khối C, D, E, F, G, H
và 1 điểm trừ cho các khối A và B). Chỉ có thể có một di chuyển từ trạng
thái khởi đầu, đó là dịch chuyển khối A xuống tạo thành một cột mới (T1).
Điều đó sinh ra một trạng thái với số
điểm là 6 (vì vị trí của khối A bây giờ sinh ra 1 điểm cộng hơn là một
điểm trừ). Thủ tục leo núi sẽ chấp nhận sự dịch chuyển đó. Từ trạng thái
mới T1, có ba di chuyển có thể thực hiện dẫn đến
ba trạng thái Ta, Tb, Tc được minh họa trong hình dưới. Những trạng
thái này có số điểm là : h’(Ta)= 4; h’(Tb) = 4 và h’(Tc) = 4
T1 TA TB TC
Hình Các trạng thái có thể đạt được từ T1
Thủ tục leo núi sẽ tạm dừng bởi vì tất
cả các trạng thái này có số điểm thấp hơn trạng thái hiện hành. Quá
trình tìm kiếm chỉ dừng lại ở một trạng thái cực đại địa phương mà không
phải là cực đại toàn cục.
Chúng ta có thể đổ lỗi cho chính giải
thuật leo đồi vì đã thất bại do không đủ tầm nhìn tổng quát để tìm ra
lời giải. Nhưng chúng ta cũng có thể đổ lỗi cho hàm Heuristic và cố gắng
sửa đổi nó. Giả sử ta thay hàm ban đầu bằng hàm Heuristic sau đây :
H2 : Đối với mỗi khối phụ trợ đúng (khối phụ trợ là khối nằm bên dưới khối hiện tại), cộng 1 điểm, ngược lại trừ 1 điểm.
Dùng hàm này, trạng thái kết thúc có số
điểm là 28 vì B nằm đúng vị trí và không có khối phụ trợ nào, C đúng vị
trí được 1 điểm cộng với 1 điểm do khối phụ trợ B nằm đúng vị trí nên C
được 2 điểm, D được 3 điểm, ....Trạng thái khởi đầu có số điểm là –28.
Việc di chuyển A xuống tạo thành một cột mới làm sinh ra một trạng thái
với số điểm là h’(T1) = –21 vì A không còn 7 khối
sai phía dưới nó nữa. Ba trạng thái có thể phát sinh tiếp theo bây giờ
có các điểm số là : h’(Ta)=–28; h’(Tb)=–16 và h’(Tc) = –15. Lúc này thủ
tục leo núi dốc đứng sẽ chọn di chuyến đến trạng thái Tc, ở đó có một
khối đúng. Qua hàm H2 này ta rút ra một nguyên
tắc : tốt hơn không chỉ có nghĩa là có nhiều ưu điểm hơn mà còn phải ít
khuyết điểm hơn. Hơn nữa, khuyết điểm không có nghĩa chỉ là sự sai biệt
ngay tại một vị trí mà còn là sự khác biệt trong tương quan giữa các vị
trí. Rõ ràng là đứng về mặt kết quả, cùng một thủ tục leo đồi nhưng hàm H1 bị thất bại (do chỉ biết đánh giá ưu điểm) còn hàm H2 mới này lại hoạt động một cách hoàn hảo (do biết đánh giá cả ưu điểm và khuyết điểm).
Đáng tiếc, không phải lúc nào chúng ta
cũng thiết kế được một hàm Heuristic hoàn hảo như thế. Vì việc đánh giá
ưu điểm đã khó, việc đánh giá khuyết điểm càng khó và tinh tế hơn. Chẳng
hạn, xét lại vấn đề muốn đi vào khu trung tâm của một thành phố xa lạ.
Để hàm Heuristic hiệu quả, ta cần phải đưa các thông tin về các đường
một chiều và các ngõ cụt, mà trong trường hợp một thành phố hoàn toàn xa
lạ thì ta khó hoặc không thể biết được những thông tin này.
Đến đây, chúng ta hiểu rõ bản chất của
hai thuật giải tiếp cận theo chiến lược tìm kiếm chiều sâu. Hiệu quả của
cả hai thuật giải leo đồi đơn giản và leo đồi dốc đứng phụ thuộc vào :
+ Chất lượng của hàm Heuristic.
+ Đặc điểm của không gian trạng thái.
+ Trạng thái khởi đầu.
Sau đây, chúng ta sẽ tìm hiểu một tiếp
cận theo mới, kết hợp được sức mạnh của cả tìm kiếm chiều sâu và tìm
kiếm chiều rộng. Một thuật giải rất linh động và có thể nói là một thuật
giải kinh điển của Heuristic.
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.
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ở 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.
Frame là
một cấu trúc dữ liệu chứa đựng tất cả những tri thức liên quan đến một
đối tượng cụ thể nào đó. Frames có liên hệ chặt chẽ đến khái niệm hướng
đối tượng (thực ra frame là nguồn gốc của lập trình hướng đối tượng).
Ngược lại với các phương pháp biểu diễn tri thức đã được đề cập đến,
frame "đóng gói" toàn bộ một đối tượng, tình huống hoặc cả một vấn đề
phức tạp thành một thực thể duy nhất có cấu trúc. Một frame bao hàm
trong nó một khối lượng tương đối lớn tri thức về một đối tượng, sự
kiện, vị trí, tình huống hoặc những yếu tố khác. Do đó, frame có thể
giúp ta mô tả khá chi tiết một đối tượng.
Dưới một khía cạnh nào đó, người ta có
thể xem phương pháp biểu diễn tri thức bằng frame chính là nguồn gốc của
ngôn ngữ lập trình hướng đối tượng. Ý tưởng của phương pháp này là "thay
vì bắt người dùng sử dụng các công cụ phụ như dao mở để đồ hộp, ngày
nay các hãng sản xuất đồ hộp thường gắn kèm các nắp mở đồ hộp ngay bên
trên vỏ lon. Như vậy, người dùng sẽ không bao giờ phải lo lắng đến việc
tìm một thiết bị để mở đồ hộp nữa!". Cũng vậy, ý tưởng chính của
frame (hay của phương pháp lập trình hướng đối tượng) là khi biểu diễn
một tri thức, ta sẽ "gắn kèm" những thao tác thường gặp trên tri thức
này. Chẳng hạn như khi mô tả khái niệm về hình chữ nhật, ta sẽ gắn kèm cách tính chu vi, diện tích.
Frame thường được dùng để biểu diễn những
tri thức "chuẩn" hoặc những tri thức được xây dựng dựa trên những kinh
nghiệm hoặc các đặc điểm đã được hiểu biết cặn kẽ. Bộ não của con người
chúng ta vẫn luôn "lưu trữ" rất nhiều các tri thức chung mà khi cần,
chúng ta có thể "lấy ra" để vận dụng nó trong những vấn đề cần phải giải
quyết. Frame là một công cụ thích hợp để biểu diễn những kiểu tri thức
này.
Cấu trúc của frame
Mỗi một frame mô tả một đối tượng (object). Một frame bao gồm 2 thành phần cơ bản là slot và facet. Một slot là một thuộc tính đặc tả đối tượng được biểu diễn bởi frame. Ví dụ : trong frame mô tả xe hơi, có hai slot là trọng lượng và loại máy.
Mỗi slot có thể chứa một hoặc nhiều facet. Các
facet (đôi lúc được gọi là slot "con") đặc tả một số thông tin hoặc thủ
tục liên quan đến thuộc tính được mô tả bởi slot. Facet có nhiều loại
khác nhau, sau đây là một số facet thường gặp.
Value (giá trị) : cho biết giá trị của thuộc tính đó (như xanh, đỏ, tím vàng nếu slot là màu xe).
Default (giá trị mặc định)
: hệ thống sẽ tự động sử dụng giá trị trong facet này nếu slot là rỗng
(nghĩa là chẳng có đặc tả nào!). Chẳng hạn trong frame về xe, xét slot
về số lượng bánh. Slot này sẽ có giá trị 4. Nghĩa là, mặc định một chiếc xe hơi sẽ có 4 bánh!
Range (miền giá trị) : (tương tự như kiểu biến), cho biết giá trị slot có thể nhận những loại giá trị gì (như số nguyên, số thực, chữ cái, ...)
If added:
mô tả một hành động sẽ được thi hành khi một giá trị trong slot được
thêm vào (hoặc được hiệu chỉnh). Thủ tục thường được viết dưới dạng một
script.
If needed : được sử dụng khi slot không có giá trị nào. Facet mô tả một hàm để tính ra giá trị của slot.
Tính kế thừa
Trong thực tế, một hệ thống trí tuệ nhân
tạo thường sử dụng nhiều frame được liên kết với nhau theo một cách nào
đó. Một trong những điểm thú vị của frame là tính phân cấp. Đặc tính này
cho phép kế thừa các tính chất giữa các frame.
Hình sau đây cho thấy cấu trúc phân cấp
của các loại hình hình học cơ bản. Gốc của cây ở trên cùng tương ứng với
mức độ trừu tượng cao nhất. Các frame nằm ở dưới cùng (không có frame
con nào) gọi là lá. Những frame nằm ở mức thấp hơn có thể thừa kế tất cả
những tính chất của những frame cao hơn.
Các frame cha sẽ cung cấp những mô tả
tổng quát về thực thể. Frame có cấp càng cao thì mức độ tổng quát càng
cao. Thông thường, frame cha sẽ bao gồm các định nghĩa của các thuộc tính. Còn các frame con sẽ chứa đựng giá trị thực sự của các thuộc tính này.
Một ví dụ biểu diễn các đối tượng hình học bằng frame
Các kiểu dữ liệu cơ bản :
Area : numeric; // diện tích
Height : numeric; //chiều cao
Perimeter : numberic; //chu vi
Side : numeric; //cạnh
Diagonal : numeric; //đường chéo
Radius : numeric; //bán kính
Angle : numeric; //góc
Diameter : numeric; //đường kính
pi : (val:numeric = 3.14159)
Frame : CIRCLE (hình tròn)
r : radius;
s : area;
p : perimeter;
d : diameter;
d = 2 × r;
s = pi × r2;
p = 2 × pi × r;
Frame RECTANGLE (hình chữ nhật)
b1 : side;
b2 : side;
s : area;
p : perimeter;
s = b1 × b2;
p = 2 × (b1+b2);
d2 = b12 + b22;
Frame SQUARE (hình vuông)
Là : RECTANGLE
b1 = b2;
Frame RHOMBUS (hình thoi)
b : side;
d1 : diagonal;
d2 : diagonal;
s : area;
p : perimeter;
alpha1 : angle;
alpha2 : angle;
h : height;
cos (alpha2/2) × d1 = h;
s = d1 × d2 / 2;
p = 4 × b;
s = b × h;
cos (alpha2/2)/(2× b) = d2;
Chúng ta có thể dễ dàng khai báo các đối
tượng hình học khác theo cách này. Sau khi đã biểu diễn các tri thức về
các hình hình học cơ bản xong, ta có thể vận dụng nó để giải các bài
toán hình học, chẳng hạn bài toán tính diện tích. Ví dụ, cho hình vuông k và vòng tròn nội tiếp c, biết cạnh hình vuông có chiều dài là x, hãy viết chương trình để tính diện tích phần tô đen.
Dễ thấy rằng, diện tích phần tô đen chính
là hiệu giữa diện tích hình vuông và diện tích hình tròn nội tiếp. Dĩ
nhiên là bạn cũng có thể viết một chương trình bình thường để tính toán,
nhưng khi đã "tích hợp" các tri thức về tính diện tích bên trong biểu
diễn, chương trình của chúng ta trở nên rất gọn nhẹ. Bạn hãy lưu ý 3
lệnh được in đậm trong ví dụ dưới. Lệnh đầu tiên sẽ "đặc tả" lại giả
thiết "hình vuông có cạnh với chiều dài x", lệnh kế tiếp đặc tả giả thiết "hình tròn nội tiếp", còn lệnh thứ 3 mô tả việc tính diện tích bằng cách lấy diện tích hình vuông trừ cho diện tích hình tròn.
VAR x, s : numeric; k : square; c : circle;
BEGIN
<Nhập x>;
k.b 1 := x;
c.d := x;
s := k.s – c.s;
END.
Như vậy, chương trình máy tính của chúng
ta đã hoạt động khá giống như việc "mô tả" các giải bài toán bằng ngôn
ngữ tự nhiên. Hãy nghĩ xa hơn một tí. Các bài toán hình học thường được
mô tả bằng các ngôn từ khá chính xác (chẳng hạn như : cho một tam giác với chiều cao xuất phát từ đỉnh A là 5, chiều dài cạnh đáy
là 6, ....). Do đó, về mặt nguyên tác, chúng ta vẫn có thể xây dựng một
chương trình để "hiểu" những đề bài này (theo như cách mà chúng ta vừa
làm). Sau đó, người dùng có thể hoàn toàn nhờ máy tính giải giúp bài
toán cho mình bằng cách mô tả lời giải
cho máy tính (chứ không cần phải lập trình). Bạn có cảm giác điều này
thật thú vị không? Đây chính là bước đi đầu tiên trong việc tạo ra một
chương trình trợ giúp cho việc giải các bài toán hình học trên máy tính với giao tiếp bằng ngôn ngữ tự nhiên!
Để tăng thêm sức mạnh cho hệ thống này,
người ta thường cài đặt một mạng ngữ nghĩa ngay bên trong mỗi frame.
Chẳng hạn, ta có thể có một frame TRIANGLE,
trong đó cài đặt một mạng ngữ nghĩa (giống như ở ví dụ trong phần mạng
ngữ nghĩa) để đặc tả mối liên hệ giữa các yếu tố tam giác (thay vì sử
dụng các công thức liên hệ đơn giản như ví dụ trên).
