Bài giảng Trí tuệ nhân tạo - Chương 2: Biểu diễn bài toán và tìm kiếm lời giải

ông Tin - Đại Học Bách Khoa Tp. HCM
Bài Giảng Môn: Trí tuệ nhân tạo
Side 24
Các đặc trưng của bài toán.

 Hàm heuristic: ví dụ
– Chess: Ưu thế trên đối thủ.
– TSP: Tổng khoảng cách hiện tại.
– 8 puzzle: Tổng khoảng cách các miếng sai vị trí.

 Các đặc trưng của bài toán.
– Một số khía cạnh cần phân tích khi chọn kỹ thuật giải BT:

 Khả năng phân rã bài toán.

 Khả năng lờ đi và quay lui.

 Khả năng dự đoán toàn cục.

 Đích là trạng thái hay con đường.

 Lượng tri thức cần để giải bài toán.

 Có cần sự can thiệp của con người trong quá trình giải không?
13
Khoa Công Nghệ Thông Tin - Đại Học Bách Khoa Tp. HCM
Bài Giảng Môn: Trí tuệ nhân tạo
Side 25
Các đặc trưng của bài toán (tt.)

 Khả năng phân rã bài toán:
– Phân rã được: như BT tính tích phân ký hiệu.

 Giải bằng cách:
– Chia nhỏ BT lớn thành các BT con độc lập.
– Giải từng BT nhỏ.
– Kết hợp thành BT lớn.
– Không phân rã được: BT thế giới các khối.

 Chương 13 sẽ khảo sát.

 Các bước giải có thể lờ đi hay quay lui:
– Có thể lờ đi : như BT chứng minh định lý.

 Vì: định lý vẫn đúng sau một vài bước áp dụng các luật.
– Có thể quay lui: như BT 8-puzzle.

 Vì: có thể di chuyển theo hướng ngược lại để về TT trước.
– Không thể quay lui: như BT chơi cờ.

 Vì: game over!
Khoa Công Nghệ Thông Tin - Đại Học Bách Khoa Tp. HCM
Bài Giảng Môn: Trí tuệ nhân tạo
Side 26
Các đặc trưng của bài toán (tt.)

 Các bước giải có thể lờ đi hay quay lui:
– Có thể lờ đi : 

 Có thể áp dụng chiến lược điều khiển đơn giản không cần quay lui.

 Dể dàng hiện thực.
– Có thể quay lui: 

 Chiến lược phức tạp hơn để quay lui được tại những bước lỗi.

 Có thể dùng Push-Down Stack.
– Không thể quay lui: 

 Dùng các chiến lược phức tạp hơn vì mổi khi ra quyết định thì đó là
quyết định cuối cùng.

 Có thể dùng giải pháp Planning.

 Sẽ được xem xét trong các chương sau.
14
Khoa Công Nghệ Thông Tin - Đại Học Bách Khoa Tp. HCM
Bài Giảng Môn: Trí tuệ nhân tạo
Side 27
Các đặc trưng của bài toán (tt.)

 Khả năng dự đoán của bài toán:
– Có thể dự đoán được: như BT 8 puzzle.

  có thể đề ra 1 chuổi nước đi và tự tin vào kết qua sẽ xãy ra.

 Có thể quay lui được.
– Không thể dự đoán được: như các game có đối kháng.

 Cần theo đuổi nhiều kế hoạch.

 Có chiến lược/đánh giá để chọn kế hoạch tốt.

 Lời giải là tuyệt đối hay tương đối:
– Tuyệt đối (best-path) : như bài toán TSP.

 Tính toán khó hơn (tổng quát).

 Cần GT tìm toàn diện hơn.
– Tương đối (any-path): như bài toán suy luận đời thường (xem 
sau).

 Có thể dùng heuristic để giải trong thời gian hợp lý.
Khoa Công Nghệ Thông Tin - Đại Học Bách Khoa Tp. HCM
Bài Giảng Môn: Trí tuệ nhân tạo
Side 28
Các đặc trưng của bài toán (tt.)
– Bài toán suy luận như sau:
1. Marcus was a man
2. Marcus was a Pompeian
3. Marcus was born in 40 A.D
4. All men are mortal.
5. All Pompeians died when the volcano erupted in 79 A.D
6. No mortal lives longer than 150 years.
7. It is now 2004 A.D
Hỏi: Is Marcus alive?
----------------------------
8. Marcus is mortal (1,4)
9. Marcus’age is 1964 years. (3,7)
10. Marcus is dead. (6,8,9)
-----------OR----------------
11. All Pompeians are died in 79 AD
12. Marcus id dead.
15
Khoa Công Nghệ Thông Tin - Đại Học Bách Khoa Tp. HCM
Bài Giảng Môn: Trí tuệ nhân tạo
Side 29
Các đặc trưng của bài toán (tt.)

 Lời giải là trạng thái hay con đường:
– Trạng thái: như bài toán tìm ra cách hiểu phù hợp cho câu. Ví
dụ:
“The bank president ate a dish of pasta salad with the fork.”

 Từng từ như: bank, president, … có thể được hiểu theo nhiều cách.

 Một kiểu tìm kiếm nào đó được thực hiện để tìm ra cách hiểu toàn 
bộ cho câu.

  Chỉ cần xuất ra kết quả cuối (Trạng Thái), không cần các bước 
trung gian.
– Con đường: như BT đong nước.

 Không chỉ xuất ra trạng thái cuối như : (2,0) mà càng con đường 
dẫn ra trạng thái cuối.
– Song, điều này cũng tương đối. Vì có thể biểu diễn trạng thái để
nó có thể bao gồm thông tin về một phần hay toàn bộ con 
đường.
Khoa Công Nghệ Thông Tin - Đại Học Bách Khoa Tp. HCM
Bài Giảng Môn: Trí tuệ nhân tạo
Side 30
Các đặc trưng của bài toán (tt.)

 Vai trò của tri thức là gì?
– Cần ít tri thức:

 Như bài toán: “chơi cờ”.

 Tri thức = luật để di chuyển hợp lệ, cơ chế điều khiển, chiến lược 
điều khiển để tăng tốc tìm kiếm.
– Cần nhiều tri thức:

 Như bài toán: Hiểu câu chuyện trên tạp chí.

 Tri thức: nhiều, cả những cái đã ghi tường minh và cả những cái 
không được ghi trong chính câu chuyện.
16
Khoa Công Nghệ Thông Tin - Đại Học Bách Khoa Tp. HCM
Bài Giảng Môn: Trí tuệ nhân tạo
Side 31
Các đặc trưng của bài toán (tt.)

 Công việc có cần tương tác với con người?
– Không cần tương tác: CT nhận mô tả bài toán, sinh ra lời giải 
mà không cần sự tương tác với con người trong quá trình giải 
để nhận thêm thông tin hay để giải thích các bước.

 Như BT: chứng minh định lý (với yêu cầu đơn giản là vào đlý – ra là
lời giải).
– Cần tương tác: CT cần tương tác với con người để nhận thêm 
thông tin, để giải thích, để nhận được hướng dẫn cần thiết.

 Như BT: xây dựng các hệ chuẩn đoán bệnh.
– Sự phân biệt này cũng có tính tương đối. Như việc chứng minh 
đlý nói trên, đôi lúc CT cũng được yêu cầu để giải thích từng 
bước chứng minh hay đôi cũng cần phải nhận hướng dẫn để bắt 
đầu từ điềm nào.
– Xác định được CT có cần tương tác hay không sẽ giúp chọn ra 
phương pháp giải thích hợp.
Khoa Công Nghệ Thông Tin - Đại Học Bách Khoa Tp. HCM
Bài Giảng Môn: Trí tuệ nhân tạo
Side 32
Các đặc trưng của bài toán (tt.)

 Nguyên tắc giải bài toán:
– Không có một kỹ thuật đơn nào có thể giải mọi bài toán.
– Phân tích kỹ các bài toán mẫu và các kỹ thuật giải toán. Xem 
xét xem kỹ thuật nào phù hợp với loại bài toán nào.
– Khi gặp một vấn đề mới thay vì xem xét lại từ đầu chọn lựa kỹ
thuật phù hợp- đã được phân tích kỹ. 
17
Khoa Công Nghệ Thông Tin - Đại Học Bách Khoa Tp. HCM
Bài Giảng Môn: Trí tuệ nhân tạo
Side 33
Các vấn đề trong thiết kế các CT tìm kiếm

 Sự tìm kiếm:
– Tìm kiếm ~ duyệt cây, từ TT bắt đầu  TT đích.
– Cả cây tìm kiếm thường không được xây dựng sẵn, thay vào đó
là được sinh ra dần dần trong quá trình tìm.
– Cấu trúc đồ thị thường thay thế cho cây trong biểu diễn KGTT.

 Các vấn đề:
– Xác định hướng tìm (forward hay backward reasoning).
– Cách lựa chọn luật để áp dụng (matching)
– Cách biểu diễn NODE của quá trình tìm (knowledge 
representation problem, frame problem).
– Các NODE trong đồ thị có thể được phát sinh nhiều lần, và có
thể đã được xem xét trước đó trong quá trình duyệt  cần loại 
bỏ những NODE lặp lại.  cần lưu lại các NODE đã xét.
Khoa Công Nghệ Thông Tin - Đại Học Bách Khoa Tp. HCM
Bài Giảng Môn: Trí tuệ nhân tạo
Side 34
Các vấn đề trong thiết kế các CT tìm kiếm(tt.) 

 Giải thuật kiểm tra NODE lặp lại (DFS):
1. Xem xét tập NODE đã tạo ra, để xem NODE mới đã có chưa.
2. Nếu chưa thì thêm NODE mới vào đồ thị.
3. Nếu đã có:
1. Thiết lập điểm mở rộng kế tiếp là con của NODE đang tồn tại , 
NODE có thể bỏ đi.
2. Nếu GT có lưu giữ con đường tốt nhất hiện có thì cần xem xét xem 
nó đạt đến NODE mới trên con đường tốt hơn không, nếu vậy thì
cập nhật lại con đường tốt nhất.
18
Khoa Công Nghệ Thông Tin - Đại Học Bách Khoa Tp. HCM
Bài Giảng Môn: Trí tuệ nhân tạo
Side 35
Các đặc trưng của hệ luật sinh

 Hai vấn đề:
– Có tập đặc trưng nào giúp cho việc xây dựng hệ luật sinh dễ
dàng?
– Có tồn tại quan hệ giữa loại bài toán và loại hệ luật sinh dùng 
để giải bài toán đó.

 Các loại hệ luật sinh:
– Monotonic: hệ luật sinh mà khi áp dụng một luật nào đó nó 
không ngăn cản việc áp dụng một luật khác mà nó có thể cũng 
đã được áp dụng tại thời điểm mà luật đầu tiên được lựa chọn.
– Nonmonotonic: ngược lại với monotonic.
– Partially commutative: hệ luật sinh có thuộc tính. Nếu áp dụng 
một chuổi luật để biến từ trạng thái X sang Y thì bất kỳ hoán vị
nào của chuổi luật này nếu được phép (so trùng được) cũng 
biến đổi từ X sang Y. 
– Commutative: vừa partially commutative và monotonic.
Khoa Công Nghệ Thông Tin - Đại Học Bách Khoa Tp. HCM
Bài Giảng Môn: Trí tuệ nhân tạo
Side 36
Các đặc trưng của hệ luật sinh
BridgeChemical 
synthesis
Not Partially 
commutative
Robot navigationTheorem provingPartially 
commutative
NonmonotonicMonotonic
19
Khoa Công Nghệ Thông Tin - Đại Học Bách Khoa Tp. HCM
Bài Giảng Môn: Trí tuệ nhân tạo
Side 37
Bài toán

 Bài toán chơi cờ, để viết CT cần chỉ rõ:
– Bàn cờ bắt đầu.
– Luật của mỗi nước đi.
– Bàn cờ cho biết sự thắng cuộc.
… và mục tiêu:
Chẳng những chơi được mà còn phải cố gắng thắng.

 Cụ thể với cờ vua:
– Bắt đầu: bàn cờ 8x8 ô, các quân cờ đứng ở vị trí xuất phát 
truyền thống.
– Đích: bàn cờ mà trong đó đối thủ không đi được hay tướng của 
họ bị tấn công.
– Luật: 

 vế trái: mẩu bàn cờ dùng để so trùng. vế phải: mẫu bàn cờ có thể
chuyển đến từ mẫu bên trái  rất nhiều luật  không tốt.

 Dạng khác như ví dụ sau:
Khoa Công Nghệ Thông Tin - Đại Học Bách Khoa Tp. HCM
Bài Giảng Môn: Trí tuệ nhân tạo
Side 38
Bài toán
– Ví dụ về luật cờ vua:
– Sử dụng quá nhiều luật (luật không tổng quát) dẫn đến:

 Con người kho đề nghị tập luật đúng, đầy đủ.

 CT khó xử lý tốt.
– Định nghĩa bài toán chơi cờ đầy:

 Chơi cờ = Di chuyển trong không gian trạng thái.

 Mỗi trạng thái = Bàn cờ hợp lệ.

 Chơi cờ = Bắt đầu từ bàn cờ đầu, dùng các luật để di chuyển và cố
gắng gặp trạng thái đích.
IF:
Tốt trắng ở ô (e,2).
Ô (e,3) trống.
Ô (e,4) trống.
THEN:
Chuyển tốt trắng đến ô (e,4).
20
Khoa Công Nghệ Thông Tin - Đại Học Bách Khoa Tp. HCM
Bài Giảng Môn: Trí tuệ nhân tạo
Side 39
Hệ luật sinh

 Tìm kiếm: cốt lõi của các hệ thông minh.
 Cấu trúc CT theo hướng làm thuận tiện việc mô tả
và thi hành quá trình tìm kiếm.
 Hệ luật sinh.

 Hệ luật sinh , gồm:
– Một tập luật.
– CSDL/tri thức chứa các thông tin cho công việc cụ thể.
– Chiến lược điều khiển để chỉ rõ:

 thứ tự luật được so trùng.

 Giải quyết xung đột khi nhiều hơn 1 luật có thể dùng được.
– Bộ áp dụng luật.