Bài giảng Trí tuệ nhân tạo

0 tới tập ĐICH thì thủ tục tìm kiếm theo chiều rộng dừng và cho ta đường đi p có độ dài ngắn nhất (thậm chí cây G vô hạn). Nếu không tồn tại đường đi như vậy thuật toán dừng nếu và chỉ nếu đồ thị cây G là hữu hạn. 106Các phương pháp tìm kiếm trong KGTT: Depth First Search (TKS)	Vào: Cây G = (N, A), đỉnh gốc n0, tập ĐICH  N	Ra : Đường đi p từ đỉnh n0 tới đỉnh n*  ĐICH	Phương pháp:	/* Sử dụng danh sách MO kiểu LIFO và danh sách ĐONG kiểu FIFO */	{MO  n0	/* Cho đỉnh n0 vào đầu danh sách MO */	 While MO   do	{n  get(MO)	/* Lấy đỉnh n ở đầu danh sách MO */	 	 ĐONG  ĐONG  {n}	 if B(n)   then	 	{MO  MO  B(n) 	/* Cho B(n) vào đầu danh sách MO */ 	 if B(n)  ĐICH   then	{exit(thành công); Xây dựng đường đi p}	}	}	 write(không thành công);	}107Các phương pháp tìm kiếm trong KGTT: Depth First Search (TKS)VD: Áp dụng thuật toán tìm kiếm theo chiều sâu với cây sau, tập ĐICH = {o, p} 	Thứ tự duyệt: a b d h 	 	Đường đi: a b d h o 108Các phương pháp tìm kiếm trong KGTT: Depth First Search (TKS)Nếu cây G hữu hạn thì thủ tục tìm kiếm theo chiều sâu sẽ dừng và cho kết quả là một đường đi từ n0 đến tập ĐICHĐường đi nhận được theo thuật toán TKR (nếu có) sẽ là đường đi ngắn nhất còn đường đi nhận được theo thuật toán TKS (nếu có) có thể không phải là đường đi ngắn nhất. Hơn nữa, nếu đồ thị vô hạn thì thủ tục TKS có thể lặp vô hạn, thậm chí trong đồ thị G tồn tại đường đi từ n0 tới tập ĐICH.109Các phương pháp tìm kiếm trong KGTT: Depth First Search (TKS)Khắc phục bằng cách giới hạn độ sâu của giải thuật.Chiến lược giới hạn: Cố đònh một độ sâu DTheo cấu hình tài nguyên của máy tínhTri thức trong việc đònh giới hạn độ sâu.Giới hạn độ sâu => co hẹp không gian trạng thái => có thể mất nghiệm.110Các phương pháp tìm kiếm trong KGTT: Depthwise search (TKSD)Tìm kiếm theo chiều sâu đối với lớp các đỉnh tuỳ thuộc vào mức sâu k đã cho ban đầu. Cách thực hiện: Ta ký hiệu độ sâu hiện tại là DS, ban đầu gán DS = k, duyệt các đỉnh trong phạm vi độ sâu  DS, nếu chưa tìm được đường đi thì tăng DS = DS + k và tiếp tục duyệt.Độ sâu d(n) của đỉnh n được định nghĩa:d(n0) 	= 0d(n)	= d(m) +1 nếu nB(m)111Các phương pháp tìm kiếm trong KGTT: Depthwise search (TKSD)Vào: Cây G = (N, A), đỉnh gốc n0, tập ĐICH  N, mức sâu kRa: Đường đi p từ đỉnh n0 tới đỉnh n*  ĐICHPhương pháp: /* Sử dụng ds MO kiểu lai LIFO và FIFO, ds DONG kiểu FIFO */	{MO  n0; DS = k;	 While MO   do	{n  get(MO)	/* Lấy đỉnh n ở đầu danh sách MO */	 	 DONG  ĐONG  {n}	 if B(n)   then	 	{if B(n)  ĐICH   then {exit(thành công); Xây dựng đường đi p}	 case d(n) do {	[0..DS - 1]: đặt B(n) vào đầu MO	DS: đặt B(n) vào cuối MO	DS + 1: {DS = DS + k;	 if k =1 then đặt B(n) vào cuối MO	 else đặt B(n) vào đầu MO	}}}	write(không thành công); }112Các phương pháp tìm kiếm trong KGTT: Depthwise search (TKSD)VD: Áp dụng thuật toán TKSD với cây sau:Tập ĐICH = {r, p}, độ sâu k = 2.Thứ tự duyệt: a b d e c f g h n o k lĐường đi: a c f l p 113Các phương pháp tìm kiếm trong KGTT: Depthwise search (TKSD)Khi k =1 thủ tục TKSD trở thành thủ tục TKRKhi k>=2 thủ tục TKSD tìm theo chiều sâu đối với các đỉnh có độ sâu nằm trong khoảng từ tk + 1 đến (t + 1)k với t bắt đầu từ 0 và mỗi lần tăng lên 1Nếu trong cây G tồn tại ít nhất một đường đi từ đỉnh n0 đến ĐICH thì thủ tục TKSD sẽ dừng và cho kết quả là đường đi có độ dài khác đường đi ngắn nhất không quá k - 1. Nếu không tồn tại đường đi như vậy thì thủ tục TKSD dừng khi và chỉ khi G hữu hạn114Các phương pháp tìm kiếm trong KGTT: Cost minimization search (TKCT)Giả sử C: AR+ là hàm giá (cost) tương ứng mỗi cung a  A với giá chi phí c(a)R+. Với một đường đi p trong G, p = n1, ..., nk ta có: 	Xác định p: n0nk  DICH sao cho: c(p)  min	Kí hiệu g(n) là giá của đường đi cực tiểu từ n0 đến n. Khi đó, bài toán trên được phát biểu thành: Tìm đường đi p0 từ đỉnh gốc n0 đến đỉnh nk  DICH sao cho g(nk)=min{g(n)| n  DICH}.	115Vào: Cây G = (N, A), đỉnh gốc n0, tập ĐICH  N, c: A  R+Ra: Đường đi p từ đỉnh n0 tới đỉnh n*  ĐICH sao cho c(p) minPhương pháp: /* Sử dụng 2 danh sách MO và DONG */	{MO  n0; g0(n0)=0; /*g0(n): giá của đường đi hiện tại từ n0 đến n*/	 While MO   do	{n  get(MO) /* Lấy đỉnh n  MO sao cho g0(n) min */	 	 ĐONG  ĐONG  {n}	 if n  ĐICH then exit(thành công)	 if B(n)   then	 	{MO  B(n)  MO	 for each m  B(n) do	g0(m) = g0(n) + c(n, m)}	} write(không thành công);	}Các phương pháp tìm kiếm trong KGTT: Cost minimization search (TKCT)116VD: Áp dụng thuật toán TKCT đối với cây sau	Tập ĐICH = {n, p}	 	Thứ tự duyệt: a c b f l m d g h p	Đường đi: a c f l p Có giá: 10Các phương pháp tìm kiếm trong KGTT: Cost minimization search (TKCT)117Thủ tục TKR là trường hợp riêng của thuật toán TKCT khi c(a) =1 a  A. Thủ tục TKS cũng là trường hợp riêng của thủ tục TKCT khi lấy tiêu chuẩn chọn n  MO là d(n) max thay cho điều kiện g0(n) minNếu trong cây G tồn tại đường đi p từ n0 đến ĐICH thì thủ tục TKCT sẽ dừng và cho kết quả là đường đi p sao cho c(p) min. Hơn nữa, thủ tục TKCT tối ưu theo nghĩa số đỉnh cho vào tập ĐONG là nhỏ nhất so với các thủ tục tìm kiếm chỉ dựa vào giá các cung. Các phương pháp tìm kiếm trong KGTT: Cost minimization search (TKCT)118Các Heuristic áp dụng cho thủ tục TKCT : Chỉ xét các đỉnh trong B(n) có triển vọng đạt tới tập ĐICH. Sắp xếp các đỉnh trong MO trước mỗi lần xử lý nhờ các hàm đánh giá.Các phương pháp tìm kiếm trong KGTT: Cost minimization search (TKCT)119“Heuristics là các quy tắc, phương pháp, chiến lược, mẹo giải hay phương cách nào đó nhằm làm giảm khối lượng tìm kiếm lời giải trong không gian bài toán cực lớn.”Thuật giải Heuristic là một sự mở rộng khái niệm thuật toán. Nó thể hiện cách giải bài toán với các đặc tính sau:Thường tì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 toán theo thuật giải Heuristic thường dễ dàng và nhanh chóng đưa ra kết quả hơn so với giải thuật tối ưu, vì vậy chi phí thấp hơn.Thuật giải Heuristic thường thể hiện khá tự nhiên, gần gũi với cách suy nghĩ và hành động của con người.Các phương pháp tìm kiếm trong KGTT: Heuristic search: TKCT*120Có nhiều phương pháp để xây dựng một thuật giải Heuristic, trong đó người ta thường dựa vào một số nguyên lý cơ bản như sau:Nguyên lý vét cạn thông minh: Trong một bài toán tìm kiếm nào đó, khi không gian tìm kiếm lớn, ta thường tìm cách giới hạn lại không gian tìm kiếm hoặc thực hiện một kiểu dò tìm đặc biệt dựa vào đặc thù của bài toán để nhanh chóng tìm ra mục tiêu.Nguyên lý tham lam (Greedy): Lấy tiêu chuẩn tối ưu (trên phạm vi toàn cục) của bài toán để làm tiêu chuẩn chọn lựa hành động cho 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.Các phương pháp tìm kiếm trong KGTT: Heuristic search: TKCT*121Nguyê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 sát nhằm nhanh chóng đạt được một lời giải tốt.Hàm Heuristic: Trong việc xây dựng các thuật giải Heuristic, người ta thường dùng các hàm Heuristic. Đó là các hàm đánh giá thô, giá trị của hàm phụ thuộc vào trạng thái hiện tại của bài toán tại mỗi bước giải. Nhờ giá trị này, ta có thể chọn được cách hành động tương đối hợp lý trong từng bước của thuật giải.Các phương pháp tìm kiếm trong KGTT: Heuristic search: TKCT*122Thủ tục TKCT là thuật giải tìm kiếm đường đi tối ưu khi chỉ xét tới các thông tin về các đỉnh, các cung và giá thành của chúng.Trong nhiều trường hợp việc tìm kiếm đường đi sẽ được định hướng rõ thêm nếu sử dụng các tri thức thu được dựa trên các hiểu biết về tình huống vấn đề ở mỗi bước. Các phương pháp tìm kiếm trong KGTT: Heuristic search: TKCT*123Các Heuristic trong việc tìm kiếm cực tiểu hoá giá thành:Chọn toán tử xây dựng cung B sao cho có thể loại bớt những đỉnh không liên quan đến bài toán hoặc ít có triển vọng nằm trên đường đi tối ưu.Sử dụng thông tin bổ sung nhằm xây dựng tập MO và cách lấy các đỉnh trong tập MO. Muốn vậy, ta phải đưa ra độ đo, tiêu chuẩn nào đó để tìm ra các đỉnh có triển vọng, thường gọi là các hàm đánh giá. Một số phương pháp xây dựng hàm đánh giá:	- Dựa vào xác suất của đỉnh trên đường đi tối ưu.	- Dựa vào khoảng cách, sự sai khác giữa một đỉnh nào đó với tập các đỉnh đích.Các phương pháp tìm kiếm trong KGTT: Heuristic search: TKCT*124Vào: 	Đồ thị G=(N,A) tuỳ ý, đỉnh gốc n0. tập đỉnh đích ĐICH.	Hàm f0: NR+. /*f0 là hàm ước lượng heuristic nào đó*/Ra: 	Đường đi p từ đỉnh n0 tới đỉnh n*  ĐICH Phương pháp: { MO{n0}; Tính f0(n0) ;	While MO   do 	{n  get(MO); /* Lấy n  MO sao cho f0 (n)  min */	 ĐONG  ĐONG  {n};	 if n ĐICH then exit(“ thành công”);	 if B(n)   then 	 for each m  B(n) do	 if m ĐONG  MO then 	{ MO MO  {m}; Tính f0(m)}	else if f0cũ(m) >fmới(m) then MO MO  {m}};	Write(“ không thành công”) }Các phương pháp tìm kiếm trong KGTT: Heuristic search: TKCT*125f0=g0+h0 , trong đó: h0(n) là tri thức bổ sung chỉ ra triển vọng của đỉnh n nằm trên đường tối ưu.f0(n) là ước lượng của hàm:	f(n)=g(n)+h(n) , trong đó: 	g(n) là giá đường đi tối ưu từ n0 tới n	h(n) là giá đường đi tối ưu từ n tới tập ĐICHf0(n) là xấp xỉ của giá đường đi tối ưu từ n0 tới tập ĐICH và đi qua đỉnh n. Thủ tục TKCT là trường hợp riêng của thủ tục TKCT* khi lấy h0=0	Các phương pháp tìm kiếm trong KGTT: Heuristic search: TKCT*126Kết quả 1: (Tính đúng đắn)Nếu đối với mỗi đỉnh nN ta có 0  h0(n)  h(n) và tồn tại >0 sao cho aA c(a) thì thủ tục TKCT* dừng và cho đường đi p: n0n*ĐICH sao cho g(n*) min. Kết quả 2: (Tính tối ưu)Giả sử thủ tục TKCT*i sử dụng hàm đánh giá f0i(n)=g0(n)+h0i(n), i=1,2 và giả sử h2 thoả mãn điều kiện h02(m) – h02(n)  h(m, n), (h(m,n) là độ dài đường đi ngắn nhất từ m đến n) và n 0  h01(n)  h02(n)  h(n) thì số nút đưa vào tập DONG của thuật toán TKCT2* bao giờ cũng nhỏ hơn số nút đối với thuật toán TKCT1*.Các phương pháp tìm kiếm trong KGTT: Heuristic search: TKCT*127VD: Xét bài toán tháp Hà Nội với n=2, lấy hàm f0=g0+h0, trong đó h0(n) là thông tin nói thêm về mối liên hệ giữa n và trạng thái đích. Chẳng hạn:	h0=2 nếu ở cọc C chưa có đĩa nào,	h0=1 nếu ở cọc C có đĩa to,	h0=3 nếu ở cọc C có đĩa nhỏ,	h0=0 nếu ở cọc C đã có hai đĩa.Các phương pháp tìm kiếm trong KGTT: Heuristic search: TKCT*128Các phương pháp tìm kiếm trong KGTT: Heuristic search: TKCT* g0 =0 g0 =1 g0 =2 g0 =3 h0 = 2, f0=2 h0 = 3, f0=4 h0 = 2, f0=3 h0 = 1 f0=3 h0 = 3 f0=5 h0 = 2 f0=4 h0 = 2 f0=5 h0 = 0 f0=3 h0 = 1 f0=4 ĐICH 129Qui bài toán về các bài toán con và các chiến lược tìm kiếm trên đồ thị Và/HoặcQui bài toán về các bài toán conThể hiện dưới dạng đồ thị VÀ/HOẶCCác phương pháp tìm kiếm trong đồ thị VÀ/HOẶC130Qui bài toán về các bài toán conÝ tưởng cơ bản là xuất phát từ bài toán đặt ra, tách bài toán này thành các bài toán con cho đến khi bài toán ban đầu trở thành các bài toán sơ cấp. Bài toán sơ cấp được hiểu là bài toán mà lời giải của chúng có thể nhận được ngay.VD: Với bài toán n2 – 1 số, bài toán sơ cấp chính là bài toán chuyển ô trống 1 lần để nhận được trạng đích. Với bài toán tháp Hà Nội, bài toán sơ cấp là chuyển 1 đĩa từ cọc này sang cọc khác.131Thể hiện dưới dạng đồ thị VÀ/HOẶCĐồ thị (định hướng) VÀ/HOẶC là cặp G = (N,A), sao cho n  N, tất cả các đỉnh m B(n) cùng thuộc vào một trong hai kiểu: đỉnh VÀ, đỉnh HOẶC. Khi các đỉnh con m của n là đỉnh VÀ thì cung (n,m) (m B(n)) được nối bởi ngoặc lớn. VD:132Thể hiện dưới dạng đồ thị VÀ/HOẶC133Đỉnh giải được:Các đỉnh kết thúc (cuối) là đỉnh giải được.Nếu đỉnh n có các đỉnh con là đỉnh VÀ thì nó là đỉnh giải được khi và chỉ khi tất cả các đỉnh con của nó giải được.Nếu đỉnh n có các đỉnh con là đỉnh HOẶC thì nó là đỉnh giải được khi và chỉ khi tồn tại 1 đỉnh con của nó giải được. Đỉnh không giải được:Nếu đỉnh n không là đỉnh kết thúc và không có các đỉnh con thì nó là đỉnh không giải được.Nếu đỉnh n không là đỉnh kết thúc và có các đỉnh con là đỉnh VÀ thì nó là đỉnh không giải được khi và chỉ khi tồn tại một đỉnh con không giải được.Nếu đỉnh n không là đỉnh kết thúc mà có các đỉnh con là đỉnh HOẶC thì nó là đỉnh không giải được khi và chỉ khi tất cả các đỉnh con là không giải được Thể hiện dưới dạng đồ thị VÀ/HOẶC134Đồ thị lời giải: Là đồ thị con của đồ thị VÀ/HOẶC chỉ chứa các đỉnh giải được và đỉnh đầu.Nhận xét: Nếu trên đồ thị VÀ/HOẶC không có đỉnh VÀ nào thì đồ thị VÀ/HOẶC trở thành đồ thị thông thường và khi đó đồ thị con lời giải sẽ suy biến thành đường đi từ đỉnh đầu tới một đỉnh kết thúc nào đó.Mục đích của quá trình tìm kiếm trên đồ thị VÀ/HOẶC là ta phải xác định xem đỉnh đầu có giải được hay không. Trong trường hợp giải được thì ta phải đưa ra cây lời giải thoả mãn điều kiện nào đó.Thể hiện dưới dạng đồ thị VÀ/HOẶC135Các phương pháp tìm kiếm trong đồ thị VÀ/HOẶC136Thủ tục gđ(nN) { if nhan(n)= “kxđ” then	if kt(n) then nhan(n)="gđ"	else if n MO ĐONG then nhan(n)=”kxđ”	else if kieu(n) then 	{bien=True;	While B(n)  and bien do	{m  get(B(n));	 gđ(m); 	 bien=(nhan(m)=”gđ”)}	if bien then nhan(n)=”gđ” else nhan(n)=”kxđ”}	else 	{bien=false;	repeat 	{m get(B(n));	 gđ(m);	 bien=(nhan(m)=”gđ”)}	until bien or B(n)=	if bien then nhan(n)=”gđ” else nhan(n)=”kxđ”}}Các phương pháp tìm kiếm trong đồ thị VÀ/HOẶC137Thủ tục tìm kiếm theo chiều rộng TKRMThủ tục tìm kiếm theo chiều sâu TKSMCác phương pháp tìm kiếm trong đồ thị VÀ/HOẶC138Vào: Cây VÀ/HOẶC G=(N, A) với đỉnh đầu n0, tập đỉnh kết thúc T={ti} NRa: Thông báo “không thành công” nếu n0 kgđ, “thành công” nếu n0 gđ và đưa ra cây lời giải.Phương pháp: /* sử dụng hai danh sách FIFO: MO, ĐONG */{MO ={n0}; While MO   do 	{n get(MO); /*Lấy đỉnh n đầu danh sách MO*/	 ĐONG{n}  ĐONG;	 bool = false;	 if B(n)  and bool = false then 	{MO MO B(n); /* đưa B(n) vào cuối danh sách MO */ 	 For each m B(n) do 	{if kt(m) then {nhan=”gđ”; bool=true}}	 if bool then 	{gđ(n0);	if nhan(n0)=”gđ” then exit(“thành công”)	else loại khỏi MO các đỉnh có tổ tiên là đỉnh giải được}}	 else {nhan(n)=”kgđ”; kgđ(n0);	 if nhan(n0) = “kgđ” then exit (“không thành công”)	 else loại khỏi MO các đỉnh có tổ tiên là đỉnh không giải được;}}} Các phương pháp tìm kiếm trong đồ thị VÀ/HOẶC: Thủ tục TKRM139VD:Áp dụng thuật toán TKRM đối với cây sau	Tập T = {t1,t2,t3,t4}Thứ tự duyệt:abcdefgijkCây lời giải:các cung tô đậmNhận xét: Nếu cây lời giải tồn tại thì thủ tục TKRM sẽ dừng và cho kết quả là cây lời giải có độ cao nhỏ nhấtCác phương pháp tìm kiếm trong đồ thị VÀ/HOẶC: Thủ tục TKRMabcde fgij kAt1t2BCt3t4DEF140Các phương pháp tìm kiếm trong đồ thị VÀ/HOẶC: Thủ tục TKSMVào: Cây VÀ/HOẶC G=(N, A) với đỉnh đầu n0, tập đỉnh kết thúc T={ti} N. Giới hạn sâu D.Ra: Thông báo “không thành công” nếu n0 kgđ, “thành công” nếu n0 gđ và đưa ra cây lời giải.Phương pháp: /* sử dụng hai danh sách FIFO: DONG, LIFO: MO */{MO ={n0}; While MO   do 	{n get(MO); /*Lấy đỉnh n đầu danh sách MO*/	 ĐONG{n}  ĐONG;	 bool = false;	 if d(n) = : . & _ ~Dựa trên quy tắcChuỗi các chữ cái, chữ số, dấu _ ,bắt đầu bằng một chữ thường (VD : anna, x25, x__y, alpha_beta,...)Chuỗi các ký tự đặc biệt (VD : , === > , ...)Chuỗi các ký tự nằm trong cặp dấu ‘ ’ (VD : ‘Hoàng’, ‘Hoa’,...)ĐỐI TƯỢNG DỮ LIỆU – Nguyên tố186Gồm số nguyên và số thựcVí dụ :Số nguyên : -3, -100, 1, 5 ,2, ...Số thực : 1.25, -3.25, ...Số thực ít được sử dụng trong lập trình PrologĐỐI TƯỢNG DỮ LIỆU - Số187BiếnChuỗi các chữ cái, chữ số và dấu _, bắt đầu bằng một chữ viết HOA hoặc dấu _.Ví dụ : X, Result, Object2, _23Biến vô danhKý hiệu : _Nếu biến chỉ xuất hiện một lần, không cần đặt tên. Sử dụng biến vô danhVí dụ : haschild(X) :- parent(X,Y). %Biến Y chỉ xuất hiện một lầnhaschild(X) :- parent(X,_). %Thay thế bằng biến vô danhĐỐI TƯỢNG DỮ LIỆU - Biến188ĐỐI TƯỢNG DỮ LIỆU – Cấu trúcCác đối tượng có nhiều thành phần.Ví dụ :Đối tượng date có thể xem là một cấu trúc với các thành phần : day, month, year.Thể hiện bằng Prolog: Ví dụ :date(1,may, 2005)date1may2005189Term (hạng)Tất cả các đối tượng dữ liệu trong Prolog được gọi là term.Ví dụ : thangnam, ngay(1, thangchin,2005) là các term.So khớp (matching)Là thao tác quan trọng nhất trên các term.Là quá trình kiểm tra xem hai term có khớp nhau hay không.ĐỐI TƯỢNG DỮ LIỆU – Cấu trúc190Hai term được xem là khớp (match) nhau nếu:Giống nhau hoàn toànCác biến trong cả hai term được khởi tạo thành các đối tượng sao cho sau khi thay thế chúng bằng các đối tượng này thì chúng giống nhau hoàn toàn.Ví dụCho hai term date(D,M, 2005) và date(D1, thangchin, Y1) được coi là khớp nhauTa có : D khởi tạo thành D1, M khởi tạo thành thangchin, còn Y1 khởi tạo thành 2005.ĐỐI TƯỢNG DỮ LIỆU – Cấu trúc191Xác định hai term có khớp nhau hay không?Nếu S, T là hằng số thì chúng khớp nhau khi chúng cùng một đối tượng.Nếu S là biến và T bất kỳ. Nếu chúng khớp nhau thì S được khởi tạo thành T và ngược lại.Nếu S và T là cấu trúc. Chúng khớp nhau khi tất cả các thành phần trong S và T khớp nhau.ĐỐI TƯỢNG DỮ LIỆU – Cấu trúc192KIỂU DỮ LIỆU & PHÉP TOÁNKIỂU DỮ LIỆUchar : ký tự ở giữa cặp dấu ‘’.Ví dụ : ‘a’, ‘b’, ‘1’, ...integer : số nguyên (từ -32768 đến 32767)Ví dụ : 200, -521, 322, ...real : số thựcVí dụ : 25.18, -78.3e+21, 25.5e-20, ...string : chuỗi dài tối đa 64KB, nằm cặp dấu “”.Ví dụ : “chào các bạn”, “Prolog”symbol : chuỗi dài tối đa 80 ký tự, có thể không có dấu “”.Ví dụ : prolog, “Prolog”, chao_cac_ban,...193KIỂU DỮ LIỆU & PHÉP TOÁNPHÉP TOÁN TRONG SWI-PROLOGPhép toán số học : +, -, *, /, mod, //, **Biểu thức số học: được xây dựng nhờ vị từ isNumber is Expr	Number: đối tượng cơ bản	Expr: biểu thức số học được xây dựng từ các phép toán số học, các số và các biến.Phép so sánh số học : >, =, 0Sử dụng thuật toán EuclideUSCLN của X và X là X.USCLN của X và Y là USCLN của X – Y và Y nếu X>Y.USCLN của X và Y là USCLN của Y-X và X nếu X xác định mục tiêu cần giải P(2) Biểu diễn bài toán dưới dạng chuẩn=> P i(jqij).(3) Chuyển sang mệnh đề Horn (luật, sự kiện)(4) Chuyển sang PrologNguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo197(1) uscln(X,Y,Z)  Z là USCLN của X,Y.(2) uscln(X,Y,Z)  [(X>Y)  (T=X-Y)  uscln(T,Y,Z)] [(XY)  (T=X-Y)  uscln(T,Y,Z).	uscln(X,Y,Z)  (XY, T is X-Y, uscln(T,Y,Z).uscln (X,Y,Z):-XY, is(T, X-Y), uscln(T,Y,Z).uscln (X,Y,Z):-X truePlist = [P1|Plist1] => true nếu P không tấn công P1 và P không tấn công các vị trí trong Plist1Bài toán 8 Hậu214Kiểm tra một vị trí đặt hậu pos(X,Y) thật sự không tấn công những con Hậu khácnoattack(_, []).noattack(pos(X,Y), [pos(X1,Y1) | Others]) :-	Y =\= Y1, Y1-Y =\= X1-X, Y1-Y=\=X-X1, noattack(pos(X,Y),Others).Chương trình?Bài toán 8 Hậu215Điều khiển quay lui và lát cắtProlog tự động quay lui để thoả mãn mục tiêu.Đây là một công việc hữu ích nhưng có những lúc lại không hiệu quả.Cần có những cách điều khiển (ngăn) quay lui.216Mối quan hệ giữa X và Y được xác lập qua 3 luật:Luật 1: Nếu X 2.Kết quả của câu hỏi trên?Điều khiển quay lui và lát cắt219f(1,Y) sẽ cho kết quả Y=0.Khi đó, Y>2 trở thành 0>2 (=> false).Vì vậy, goal cho kết quả là : No.Prolog phải duyệt qua cả 3 mệnh đề của vị từ f.Điều khiển quay lui và lát cắt220Lát cắt:Ký hiệu: !Dùng để ngăn Prolog quay lui trong trường hợp đã tìm ra lời giải hoặc sẽ không tìm ra lời giải thêm nếu tiếp tục.Điều khiển quay lui và lát cắt221Thêm lát cắt :f(X,0) :- X2.Prolog sẽ cho kết quả ra sao? Thực thi như thế nào?Điều khiển quay lui và lát cắt222Prolog sẽ cho ra cùng kết quả: No.Không có sử dụng đến mệnh đề (luật) 2 và 3. =>đỡ tốn kém thời gian thực hiện.=> tăng hiệu quả cho chương trình.Điều khiển quay lui và lát cắt223Với đoạn chương trình:f(X,0) :- XB,!.	max(A,B,B).Điều khiển quay lui và lát cắt231Thuận lợi:Lát cắt làm tăng hiệu quả chương trình (tiết kiệm không gian, thời gian,)Loại bỏ được những chọn lựa chắc chắn sai.Có thể thực hiện các luật có dạng:if ĐK1 then KL1else KL2Điều khiển quay lui và lát cắt232Khó khăn:Trật tự các mệnh đề trong vị từ có thể ảnh hưởng đến kết quả (khi sử dụng lát cắt)Ví dụ:Vớip :- a,b.p :- c.p (a  b)  cĐiều khiển quay lui và lát cắt233Ví dụ:Trong khi vớip :- a, !, b.p :- c.p (a  b)  ( a  c)Cònp :- c.p :- a, !, b.p c  (a  b) Điều khiển quay lui và lát cắt234ÔN TẬP