Giáo trình Trí tuệ nhân tạo

2 3 2 8 3 1 8 3 1 5 6 7 5 4 7 4 Mức 6: Có 24 trạng thái 1 2 3 1 2 3 8 4 7 8 4 7 6 5 6 5 . . .   30 Ở mức này ta gặp được trạng thái đích. 1 2 3 8 4 7 6 5 2. Phương pháp tìm kiếm theo chiều sâu. 2.1. Kỹ thuật tìm kiếm sâu. Tìm kiếm sâu trong không gian bài toán được bắt đầu từ một nút rồi tiếp tục cho đến khi hoặc đến ngõ cụt hoặc đến đích. Tại mỗi nút có luật trong tài, chẳng hạn, “đi theo nút cực trái”, hướng dẫn việc tìm. Nếu không đi tiếp đựoc, gọi là đến ngõ cụt, hệ thống quay lại một mức trên đồ thị và tìm theo hướng khác, chẳng hạn, đến nút “sát nút cực trái”. Hành động này gọi là quay lui. Thuật toán tìm kiếm theo chiều sâu được hình dung như việc khảo sát một cây bắt đầu từ gốc đi theo mọi cành có thể được, khi gặp cành cụt thì quay lại xét cành chưa đi qua. - Ở bước tổng quát, giả sử đang xét đỉnh i, khi đó các đỉnh kề với i có các trường hợp: + Nếu tồn tại đỉnh j kề i chưa được xét thì xét đỉnh này (nó trở thành đỉnh đã xét) và bắt đầu từ đó tiếp tục quá trình tìm kiếm với đỉnh này.. + Nếu với mọi đỉnh kề với i đều đã được xét thì i coi như duyệt xong và quay trở lại tìm kiếm từ đỉnh mà từ đó ta đi đến được i. 2.2. Giải thuật. Input: Cây/Đồ thị G = (V,E) với đỉnh gốc là n0 (trạng thái đầu) Tập đích Goals Output: Một đường đi p từ n0 đến một đỉnh n*  Goals   31 Method: Sử dụng hai danh sách hoạt động theo nguyên tắc LIFO (Stack) MO và DONG Procedure DFS; (Depth First Search) Begin Push (MO,no) DONG=null; While MO null do begin n:=pop (MO); if n DICH then exit; push (DONG, n); For m T(n) and mDONG+MO do Push (MO, m); end; Write (‘Không có lời giải’); End; Chú ý: Thủ tục Push(MO,n0) thực hiện việc bổ sung n0 vào stack MO Hàm Pop(MO) lấy phần tử đầu tiên trong Stack MO. 2.3. Đánh giá độ phức tạp của thuật toán tìm kiếm sâu. Gải sử nghiệm của bài toán là đường đi có độ dài d, cây tìm kiếm có nhân tố nhánh là k. Có thể xãy ra nghiệm là đỉnh cuối cùng được xét ở mức d+1 theo luật trọng tài. Khi đó độ phức tạp thời gian của thuật toán tìm kiếm theo chiều sâu trong trường hợp xấu nhất là O(kd). Để đánh giá độ phức tạp không gian của thuật toán tìm kiếm sâu ta có nhận xét ràng: Khi xét đỉnh j, ta chỉ cần lưu các đỉnh chưa được xét mà chúng là những đỉnh con của những đỉnh nằm trên đường đi từ đỉnh gốc đến j. Vì vậy chỉ cần lưu tối đa la k*d. Do đó độ phức tạp không gian của thuật toán là O(k*d).   32 2.4. Ưu và nhược điểm của phương pháp tìm kiếm sâu. 2.4.1. Ưu điểm.  Nếu bài toán có lời giải, phương pháp tìm kiếm sâu bảo đảm tìm ra lời giải.  Kỹ thuật tìm kiếm sâu tập trung vào đích, con người cảm thấy hài lòng khi các câu hỏi tập trung vào vấn đề chính.  Do cách tìm của kỹ thuật này, nếu lời giải ở rất sâu, kỹ thuật tìm sâu sẽ tiết kiệm thời gian. 2.4.2. Nhược điểm.  Tìm sâu khai thác không gian bài toán để tìm lời giải theo thuật toán đơn giản một cách cứng nhắc. Trong quá trình tìm nó không có thông tin nào hổ trợ để phát hiện lời giải. Nếu chọn nút ban đầu không thích hợp có thể không dẫn đến đích của bài toán.  Không phù hợp với không gian bài toán lớn, kỹ thuật tìm kiếm sâu có thể không đến lời giải trong khoảng thời gian vừa phải. 2.5. Các ví dụ. Ví dụ 1. Bài toán đong nước với m = 5, n = 4, k = 3 Nếu ta chọn nhánh ưu tiên đổ đầy bình thứ hai thì sẽ tìm thấy lời giải rất nhanh. Quá trình tìm kiếm có thể trình bày bằng bảng dưới đây i T(i) MO  DONG (0;0) (0;0) (5;0) (0;4) (5;0) (0;4) (0;0) (0;4) (5;4) (0;0) (4;0) (5;0) (5;4) (4;0) (0;0) (0;4) (4;0) (5;0) (4;4) (0;0) (0;4) (5;0) (5;4) (4;4) (0;0) (0;4) (4;0) (4;4) (5;4) (0;4) (4;0) (5;3) (5;0) (5;4) (5;3) (0;0) (0;4) (4;0) (4;4) (5;3)   33 Lời giải tìm được: (0;0)  (0;4)  (4;0)  (4;4)  (5;3) Ví dụ 2. Bài toán Tháp Hà nội với n = 3. Nhắc lại, dùng bộ ba (x1; x2; x3) biểu diễn trạng thái bài toán, với xi là cọc chứa đĩa lớn thứ i. i T(i) MO  DONG (1;1;1) (1;1;1) (1;1;2) (1;1;3) (1;1;2) (1;1;3) (1;1;1) (1;1;3) (1;1;1)(1;1;2) (1;2;3) (1;1;2)(1;2;3) (1;1;1)(1;1;3) (1;2;3) (1;1;3) (1;2;1) (1;2;2) (1;1;2)(1;2;1)(1;2;2) (1;1;1)(1;1;3)(1;2;3) (1;2;2) (1;2;3) (1;2;1) (3;2;2) (1;1;2)(1;2;1)(3;2;2) (1;1;1)(1;1;3)(1;2;3)(1;2;2) (3;2;2) (1;2;2) (3;2;3) (3;2;1) (1;1;2)(1;2;1)(3;2;1) (1;1;1)(1;1;3)(1;2;3)(1;2;2) (3;2;2) (3;2;1) (3;2;2) (3;2;3) (3;3;1) (1;1;2)(1;2;1)(3;3;1) (1;1;1)(1;1;3)(1;2;3)(1;2;2) (3;2;2) (3;2;1) (3;3;1) (3;2;1) (3;3;2) (3;3;3) (1;1;2)(1;2;1)(3;3;3) (1;1;1)(1;1;3)(1;2;3)(1;2;2) (3;2;2) (3;2;1) (3;3;3) (3;3;3) Lời giải của bài toán: (1;1;1)  (1;1;3)  (1;2;3)  (1;2;2)  (3;2;2)  (3;2;1)  (3;3;1)  (3;3;3)  Cả hai ví dụ trên, chúng ta đều thấy, tìm kiếm theo chiều sâu đều cho lời giải tốt và nhanh. Ví dụ 3. Bài toán tìm dãy hợp lý với số hạng đầu a1 = 26 Nhắc lại: Dãy a1, a2, ,an được gọi là hợp lý nếu thoả hai điều kiện:   34 - an là số nguyên tố - ak+1 = ak+1 hoặc 2*ak Như vậy, khi biết ak thì ta xác định được ak+1. Vì vậy có thể mô tả trạng thái bài toán tương ứng với giá trj ak tại thòi điểm đang xét. Ta có thể chỉ ra một cách tìm kiếm theo chiều sâu như sau I T(i) MO  DONG 26 26 27 52 27 52 26 52 53 104 27 53 104 26 52 104 105 208 27 53 105 208 26 52 104 208 209 416 27 53 105 209 416 26 52 104 208 . . . Với cách tìm kiếm theo theo thuật toán một cách máy móc như vậy thì rõ ràng không bao giờ đạt được đích. Trong khi chúng ta dễ dàng nhận được lời giải, chăng hạn: a1 = 26; a2 = 52; a3 = 53. Như vậy n =3 3. Tìm kiếm sâu dần 3.1. Kỹ thuật tìm kiếm sâu dần. Kỹ thuật tìm kiếm sâu dần là thực hiện việc tìm kiếm với độ sâu ở mức giưói hạn d nào đó. Nếu không tìm ra nghiệm ta tăng độ sâu lên d+1 và lại tìm kiếm theo độ sâu tới mức d+1. Quá trình trên được lặp lại với d lần lượt là 1, 2,...đến độ sâu max nào đó. Kỹ thuật tìm kiếm sâu dần thường được thực hiện khi cây tìm kiếm chứa nhánh vô hạn, và nếu sử dụng tìm kiếm theo độ sâu ta có thể mắc kẹt ở một nhánh nào đó (thuật toán không dừng) và không tìm ra nghiệm. n0 D   35 3.2. Giải thuật. Thuật toán tìm kiếm sâu dần sử dụng thuật toán tìm kiếm sâu hạn chế như thủ tục con. Đó là thủ tục tìm kiếm theo chiều sâu nhưng chỉ tới độ sâu d nào đó rồi quay lên. Thủ tục tìm kiếm sâu hạn chế (depth_limitedsearch) Procedure Depth_limited_search(d); {d là tham số độ sâu} Begin Push (MO,no); Depth(n0)=0; {hàm depth ghi lại độ sâu mỗi đỉnh} DONG=null; While MO null do begin n:=pop (MO); if n DICH then exit; push (DONG, n); if depth(n)<=d then For m T(n) and mDONG do begin Push (MO, m); depth(m)=depth(n)+1; end; end; Write (‘Không có lời giải’); End Thuật toán tìm kiếm sâu dần (Depth_deepening_search) sẽ sử dụng thủ tục tìm kiếm sâu hạn chế như thủ tục con:   36 Procedure Depth_deepening_search; Begin For d:=0 to max do Depth_limited_search(d); If thành công then exit; End; 3.3. Nhận xét. - Luôn tìm ra nghiệm (nếu bài toán có nghiệm), miễn là chọn max đủ lớn (giống như tìm kiếm theo chiều rộng) - Có độ phức tạp thời gian là O(kd) (giống tìm kiếm rộng) - Có độ phức tạp không gian là O(k*d) (giống tìm kiếm sâu) - Giải thuật tìm kiếm sâu dần thương áp dụng cho các bài toán có không gian trạng thái lớn và độ sâu của nghiệm không biết trước. 4. Phương pháp tìm kiếm tốt nhất đầu tiên (Best First Search). Cả hai kỹ thuật tìm kiếm rộng và tìm kiếm sâu đều là phương pháp cơ bản để khai thác không gian bài toán. Chúng đều vét cạn không gian để tìm ra lời giải theo thủ tục xác định trước. Mặc dù có sử dụng tri thức về trạng thái của bài toán để hướng dẫn tìm kiếm nhưng không phổ biến. Cho dù có một số ưu điểm, nhưng chúng là những kỹ thuật thực hiện một cách máy móc. Chính vì vậy chúng bị gán tên là “kỹ thuật tìm kiếm mù”. 4.1. Kỹ thuật tìm kiếm tốt nhất đầu tiên. Kỹ thuật tìm kiếm tốt nhất đầu tiên tìm lời giải có dùng tri thức về bài toán để hướng dẫn. Tri thức này hướng việc tìm kiếm về nút lời giải trong không gian bài toán. Tại mỗi nút được xem xét, người ta sẽ quyết định việc tìm kiếm tiếp tục theo nhánh nào tin tưởng sẽ dẫn đến lời giải. Trong các chương trình trí tuệ nhân tạo, kỹ thuật tìm kiếm tốt nhất đầu tiên sử dụng hàm đánh giá. Hàm này dùng các thông tin hiện tại về mức độ quan trọng của bài toán tại nút đó để gán giá trị cho nút này, gọi là trọng số của nút.   37 Giá trị này được xem xét trong lúc tìm kiếm. Thông thường, nút có trọng số nhỏ (lớn) nhất sẽ được chọn trong quá trình tìm kiếm. 4.2. Hàm đánh giá Trong nhiều vấn đề, ta có thể sử dụng kinh nghiệm, tri thức của chúng ta về vấn đề đó để đánh giá các trạng thái của vấn đề. Với mỗi trạng thái u, ta sẽ xác dịnh một giá trị số h(u), số này đánh giá “sự gần đích” của trạng thái u. Hàm h(u) được gọi là hàm đánh giá. Phương pháp tìm kiếm kinh nghiệm là phương pháp tìm kiếm có sử dụng đến hàm đánh giá. Trong quá trình tìm kiếm, tại mỗi bước ta sẽ chọn trạng thái kế tiếp là trạng thái có nhiều hứa hẹn dẫn tới đích nhiều nhất. Quá trình tìm kiếm trong không gian trạng thái có sử dụng hàm đánh giá bao gồm các bước cơ bản sau:  Biểu diễn thích hợp các trạng thái và các toán tử chuyển trạng thái  Xây dựng hàm đánh giá  Thiết kế chiến lược chọn trạng thái ở mỗi bước 4.3. Ưu và nhược điểm của phương pháp tìm kiếm tốt nhất đầu tiên. 4.3.1. Ưu điểm. - Phương pháp tìm kiếm tốt nhất đầu tiên tổ hợp các ưu điểm của phương pháp tìm kiếm rộng và tìm kiếm sâu. - Ưu điểm chủ yếu của phương pháp tìm kiếm tốt nhất đầu tiên là dùng tri thức để dẫn dắt việc tìm kiếm. Tri thức này giúp người ta bắt đầu từ đâu là tốt nhất và cách tốt nhất để tiến hành tìm lời giải. - Tìm kiếm tốt nhất đầu tiên tuân theo cách suy lý của một chuyên gia. Do đó có thể thấy rõ đường đi hơn tìm kiếm rộng và tìm kiếm sâu. 4.3.2. Nhược điểm. - Quá trình tìm kiếm có thể đi xa khỏi lời giải. Kỹ thuật này chỉ xét một phần của không gian và coi đó là phần hứa hẹn hơn cả.   38 4.4. Giải thuật. Dữ liệu tương tự như giải thuật tìm kiếm rông và sâu, sử dụng danh sách MO để lưu các đỉnh sẽ xét. Procedure BFS; {Best First Search} Begin Push(MO,n0); while MO null do begin i := Pop(MO); if i  Goals then exit; for j  T(i) do Push(MO,j); Sort(MO); {theo thứ tự của hàm đánh giá} end; write(‘Khong co loi giai’); end; 4.5. Các ví dụ. Ví dụ 1 Trong bài toán tìm kiếm đường đi trên bản đồ giao thông, ta có thể lấy độ dài của đường chim bay từ một thành phố đang xét tới một thành phố đích làm giá trị của hàm đánh giá của thành phố đang xét. Ví dụ 2 Bài toán 8 số. Chúng ta có thể đưa ra hai cách đánh giá u = đích = - Hàm h1: Với mỗi trạng thái u thì h1(u) là số quân không nằm đúng vị trí của nó trong trạng thái đích. Với ví dụ trên, ta có h1(u)=4 3  2  8    6  4  7  1  5  1  2  3  8 4 7 6 5   39 - Hàm h2: Gọi h2(u) là là tổng khoảng cách giữa vị trí của các quân trong trạng thái u và vị trí của nó trong trạng thái đích. Ở đây, khoảng cách được hiểu là số lần dịch chuyển ít nhất theo hàng hoặc cột để đưa một quân ở vị trí của hiện tại tới trạng thái đích. Với ví dụ trên, ta có:h2(u)=2+3+1+3= 9 (vì quân 3 cần ít nhất 2 dịch chuyển, quân 8 cần ít nhất 3 dịch chuyển, quân 6 cần ít nhất 1 dịch chuyển và quân 1 cần ít nhất 3 dịch chuyển) 5. Tìm kiếm đường đi có giá thành cực tiểu - Thuật toán AT Cho đồ thị G= (V, E) biểu diễn bài toán với đỉnh xuất phát n0 và tập đích DICH xác định. Với mỗi phép chuyển trạng thái nini+1 tốn chi phí c(ni, ni+1 ) ký hiệu c(u) với u= (ni, ni+1)E c(u) ni ni+1 Vấn đề: Tìm đường đi p: n0 n*  DICH sao cho min)()(  pu ucpc Chẳng hạn trong bài toán tìm đường đi trong bản đồ giao thông, giá của cung (i,j) chính là độ dài của đường nối thành phố i với thành phố j. Độ dài đường đi được xác định là tổng độ dài các cung trên đường đi. Vấn đề đặt ra là tìm đường đi ngắn nhất từ trạng thái ban đầu đến trạng thái đích.  Phương pháp giải 1) Nếu Euconstkuc  )()( thì min#min)(  ppc  Dùng phương pháp tìm kiếm theo chiều rộng. 2) Gọi g(n) là giá của đường đi cực tiểu từ đỉnh n0 đến n, khi đó bài toán có thể phát biểu như sau: Tìm đường đi từ đỉnh DICHnn k 0 sao cho:  DICHnngng k  /)(min)( Lúc đó, ta có: 0)( 0 ng  ),()(min)( ),( mncngmg Emn     40 Dùng 2 danh sách MO, DONG như trên. Tại mỗi thời điểm chọn đỉnh n trong MO ra xét là đỉnh thoả.  Thuật toán AT Input: Đồ thị G = (V,E), Đỉnh xuất phát n0 Hàm chi phí c: E  R+ c(i,j): xác định chi phí chuyển từ đỉnh i sang đỉnh j với (i,j)  E Tập các đỉnh đích DICH Output: Đường đi từ đỉnh n0 đến đỉnh n*  DICH sao cho g(n*) = c(p) = min{g(n)| nDICH}. Procedure AT; { Dùng g0(n) là chi phí cực tiểu của đường đi từ đỉnh xuất phát đến đỉnh n tại thời điểm đang xét và xem như hàm g} Begin g(n0):= 0; push(MO, n0); While MOnull do begin )(min:)( mgng MOm if nDICH then exit {xay dung duong di cuc tieu} push(DONG, n); if T(n) null then for mT(n) do if mMO+DONG then begin push(MO,m);   41 g(m):=g(n)+c(n,m); cha(m):=n; end else if g(m) >g(n)+c(n,m) then begin g(m):=g(n)+c(n,m); cha(m):=n; end; end; writeln(‘Khong co duong di’); End; Ví dụ 1. Bài toán Tháp Hà Nội -với chi phí chuyển đĩa như sau: Chi phí chuyển đĩa nhỏ giữa 2 cọc gần 1 Chi phí chuyển đĩa nhỏ giữa 2 cọc xa 3 Chi phí chuyển đĩa vừa giữa 2 cọc gần 2 Chi phí chuyển đĩa vừa giữa 2 cọc xa 5 Chi phí chuyển đĩa lớn giữa 2 cọc gần 4 Chi phí chuyển đĩa lớn giữa 2 cọc xa 8 Xuất phát từ đỉnh (1,1,1), ta có g(1,1,1) = 0. Khi xét đỉnh (1,1,1) ta có các đỉnh kề và chi phí tương ứng : g(1,1,2) = 1; g(1,1,3) = 3; như vậy đỉnh (1,1,2) được chọn Các đỉnh kề của (1,1,2) có giá trị hàm g: g(1,1,3) = 2 (ở đây giá của đỉnh (1,1,3) được tính lại); g(1,3,2) = 5; chọn đỉnh (1,1,3), ta lại tính tiếp giá trị hàm g của các đỉnh kề với đỉnh này: g(1,2,3) = 2; lại chọn đỉnh (1,2,3); chi phí của các đỉnh kề với nó: g(1,2,1) = 2 + 3 = 5; g(1,2,2) = 2 + 1 = 3; chọn đỉnh (1,2,2) g(1,2,1) = 3 +1 = 4 (được tính lại); g(3,2,2) = 3 + 8 = 11, chọn đỉnh (1,2,1)   42 Cứ tiếp tục như vậy cho đến khi xét đỉnh (3,3,3). Ví dụ 2 A n0=A DICH={F,K} B C D E F G H I K Có thể trình bày quá trình tìm kiếm bằng bảng dưới đây. Ký hiệu giá trị g(n) là chỉ số dưới tương ứng đỉnh n: ng(n) i T(i) MO DONG A0 A B C D B8 C4 D5 A C G B8 D5 G5 A C D H I B8 G5 H14 I6 A C D G B8 H14 I6 A C D G I K B8 H14 K8 A C D G B E F H14 K8 E10 F11 A C D G B K Lời giải của bài toán là A D  I  K và chi phí của đường đi tìm được là 8 Ví dụ 3. n0 = A; DICH = {G} A B C D E G F 8 2 5 4 3 1 9 1  2  5 1 7 4 48 3 63 2 9  5    43 i T(i) MO DONG A0 A B C D B5 C3 D6 A C A B E F D B4 D6 E7 F11 A C B A C E D6 E7 F11 A C B D A C F G E7 F9 G15 A C B D E B C F F9 G15 A C B D E F C D E G G14 A C B D E F G Đường đi tìm được p: A  D  F  G. Chi phí của đường đi là 14. 6. Tìm kiếm cực tiểu sử dụng hàm đánh giá - Thuật toán A* Đối với nhiều bài toán, việc tìm kiếm đường đi cực tiểu sẽ được định hướng tập trung xung quanh đường đi tốt nhất; nếu sử dụng các thông tin đặc tả về bài toán gọi là các heuristic. Đối với việc tìm kiếm đường đi với chi phí cực tiểu, người ta sử dụng hàm đánh giá heuristic như sau: Gọi g(n): giá cực tiểu đường đi từ n0n. Tại đỉnh n, g(n) xác định được. Gọi h(n): giá cực tiểu đường đi từ nDICH, h(n) không xác định được  người ta tìm cách ước lượng giá trị này. Đặt f0(n)=g0(n)+h0(n): dự đoán chi phí cực tiểu của đường đi từ n0DICH có đi qua đỉnh n. g0(n) là chi phí của đường đi từ đỉnh xuất phát đến đỉnh n tại thời điểm đang xét. h0(n) là ước lưọng (dự đoán) chi phí đường đi từ đỉnh n đến đích. Việc chọn giá trị xấp xỉ h0(n) của h(n) không có một phương pháp tổng quát và được xem như một nghệ thuật. Giá trị này sẽ do các chuyên gia đưa ra. Lúc này giải thuật tìm kiếm cực tiểu sẽ thay việc xét hàm g bởi hàm f. Tuy nhiên, người ta cũng chứng minh được 2 kết quả như sau:   44 Kết quả 1: Nếu h0(n) có tính chất: nnhnh  )()(0 0 và Euuc  0)( thì thủ tục TKCT sử dụng hàm f0(n) để chọn phần tử trong MO ra xét (thay g(n)) sẽ cho đường đi từ n0n*DICH sao cho )(min)( * ngng DICHn Kết quả 2: Giả sử dùng 2 hàm ước lượng 01h và 02h thoả tính chất: ),()()( 0202 nmhnhmh  (giá cực tiểu của đường đi từ mn) và )()()(0, 0201 nhnhnhNn  . Khi đó #DONG2  #DONG1 Nhận xét:  hh0 phương án tốt nhất  00h phương án tồi nhất Thuật toán A* Input: Đồ thị G = (V,E), Đỉnh xuất phát n0 Hàm chi phí c: E  R+ c(i,j): xác định chi phí chuyển từ đỉnh i sang đỉnh j với (i,j)  E h: V  R+; h(n) xác định dự đoán chi phí tối ưu của đường đi từ đỉnh n đến đích. (ký hiệu h thay cho h0, (tương tự g)) Tập các đỉnh đích DICH Output: Đường đi từ đỉnh n0 đến đỉnh n*  DICH Procedure A* ; Begin g(n0):= 0; push(MO, n0); While MOnull do begin )(min:)( mfnf MOm if nDICH then   45 exit {xay dung duong di cuc tieu} push(DONG, n); if T(n) null then for mT(n) do if mMO+DONG then begin push(MO,m); tính f(m); cha(m):=n; end else if fmới(m) > fcũ(n) then begin f(m):= fmới(m); cha(m):=n; end; end; writeln(‘Khong co duong di’); End; Ví dụ 1. Cho đồ thị biểu diễn bài toán và giá trị dự đoán h0 như sau: n A B C D E F G H h0(n) 14 10 10 5 5 4 4 0 A B D C E F G H 5 3 7 4 2 6 5 3 2 3 12 7   46 Tìm đường đi từ đỉnh A đến đỉnh H. Trước tiên đỉnh A được đưa vào danh sách MO g(A) = 0; h(A) = 14; f(A) = 14 Xét đỉnh A, (đưa A vào danh sách DONG) ta có các đỉnh kề B, C, D: g(B) = 5; f(B) = 15; g(C) = 3; f(C) = 13; g(D) = 7; f(D) = 12  chọn đỉnh D. Xét đỉnh D (đưa D vào danh sách DONG) có các đỉnh kề A, C, E. Đỉnh A đã ở trong danh sách DONG, ta tính lại f(C) và tính f(E): f(C) không thay đổi; f(E) = g(D) +c(D,E) + H(E) = 7 + 6 + 5 = 18; f(E) = 18, chọn đỉnh C, có các đỉnh kề A, D, E. Tính lại f(E) = 12, chọn E. Các đỉnh kề của E là C, D, F, G. Tính f(F) = 14; f(G) = 16, chọn F. Các đỉnh kề của F là E, G, B và f(B), f(E), f(G) không đổi, chọn B. Các đỉnh kề của B là F, H. f(H) = 17, chọn G. Tính lại f(H) = 15 và dừng. Đường đi tìm được là p: A  C  E  G  H với chi phí đường đi là 15 7. Phương pháp tìm kiếm leo đồi (hill-climbing search) 7.1. Kỹ thuật tìm kiếm leo đồi. Tìm kiếm leo đồi là tìm kiếm theo độ sâu được hướng dẫn bởi hàm đánh giá. Song khác với tìm kiếm theo độ sâu, khi phát triển một đỉnh u thì bước tiếp theo ta chọn trong số các đỉnh con của u, đỉnh có hứa hẹn nhiều nhất để phát triển, đỉnh này được xác định bởi hàm đánh giá. 7.2. Giải thuật. Input: Đồ thị G = (V,E), đỉnh xuất phát n0. Hàm đánh giá h(n) đối với mỗi đỉnh n. Tập đỉnh đích DICH Output: Đường đi từ đỉnh n0 đến DICH Procedure HLC; {Hill Climbing Search} begin Push(MO,n0);   47 while MO null do begin i = Pop(MO); if T(i)  DICH null then begin L:= null; for j  T(i) do if j chưa xét then đưa j vào danh sách L sắp xếp L theo thứ tự hàm đánh giá; chuyển danh sách L vào đầu danh sách MO; end; write(‘Khong co loi giai’); end; 7.3. Nhận xét. Phương pháp tìm kiếm leo đồi chú trọng tìm hướng đi dễ dẫn đến trạng thái đích nhất. Cách đó được đưa ra nhằm làm giảm công sức tìm kiếm. Thuật toán tìm kiếm leo đồi thực chất là thuật toán tìm kiếm theo chiều sâu, song tại mỗi bước ta sẽ ưu tiên chọn một trạng thái có hứa hẹn nhanh tới đich nhất để phát triển trước. Vấn đề quan trọng là biết khai thác kheo léo thông tin phản hồi để xác định hướng đi tiếp và đẩy nhnah quá trình tìm kiếm. Thông thường ta gán mỗi trạng thái của bài toán với một số đo (hàm đánh giá) nào đó nhằm đánh giá mức độ gần đích của nó. Điều đó có nghĩa là nếu trạng thái hiện thời là u thì trạng thái v sẽ được phát triển tiếp theo nếu v kề với u và hàm đanh giá của v đạt giá trị max (hoặc min). Tuy nhiên phương pháp này không được cải thiện so với các phương pháp khác trong một số trường hợp sau:   48  Cực trị địa phương: nút đang xét tốt hơn các nút lân cận, nhưng đó không phải là phương án tốt nhất trong toàn thể, ví vậy có thể phải quay lui về nút trước để đi theo hướng khác. Giải pháp này đòi hỏi ghi nhớ lại nhiều đường đi.  Cao nguyên bằng phẳng: Các giá trị của các phương án như nhau, không xác định được ngay hướng nào là tốt hơn trong vùng lân cận. 7.4. Các ví dụ. Ví dụ 1. Bài toán trò chơi 8 số. 2 8 3 1 2 3 trạng thái đầu 1 6 4 trạng thái đích 8 4 7 5 7 6 5 Trong bài toán này ta sử dụng hàm đánh giá, ký hiệu là h với ý nghĩa: h(u) cho biết số các chữ số trong trạng thái u không trùng với vị trí cú nó trong trạng thái đích. Trạng thái có tiềm năng dẫn đến đích nhanh nhất (được ưu tiên phát triển trước) là trạng thái có hàm đánh giá h đạt giá trị min.. Minh hoạ cây tìm kiếm cho trò chơi này theo giải thuật leo đồi ở trang sau Trạng thái được chọn đi tiếp ở hướng mũi tên. Ở mức 3 chúng ta thấy có hai trạng thái cùng giá trị hàm đánh giá (= 3). Đây là trương hợp “cao nguyên băng phẳng” như nhận xét trên, nếu ta chọn phương án kia thì chắc chắn quá trình tìm kiếm sẽ khác đi nhiều. Trường hợp này dành cho độc giả.   49 2 8 3 1 6 4 7 5 h(u) = 4 2 8 3 2 8 3 2 8 3 1 6 4 1 4 1 6 4 7 5 7 6 5 7 5 h(u) = 5 h(u) = 3 h(u) = 5 2 8 3 2 3 2 8 3 1 4 1 8 4 1 4 7 6 5 7 6 5 7 6 5 h(u) = 3 h(u) = 3 h(u) = 4 2 3 2 3 1 8 4 1 8 4 7 6 5 7 6 5 h(u) = 2 h(u) = 4 1 2 3 8 4 7 6 5 h(u) = 1 1 2 3 1 4 7 5 8. Phương pháp sinh và thử. Chiến lược này đơn giản, gồm ba bước: - Trước hết tạo ra một giải pháp. Trong vài bài toán cụ thể đó là việc chọn một lời giải trong không gian các lời giải hay tạo ra một đường đi.   50 - Thứ hai, thử xem lời giải đó có thích hợp không bằng cách so sánh phương án khác hay so sanh với điểm cuối cần suy diễn. - Tiếp theo, nếu lời giải đạt được thì dừng, ngước lại, lặp lại từ bước đầu với nút khác. Với phương pháp này nếu bài toán có llời giải thì sẽ đưa đến đích. Tuy nhiên kích thước bài toán lớn sẽ tăng khối lượng tính toán. Việc tạo lời giải ban đầu có thể thực hiện ngẫu nhiên, và cũng hy vọng ngẫu nhiên mà đạt được lời giải, bởi vậy, không thể không tính đến chỉ một vài hướng đi được cảm nhận là tốt, và loại trừ trước các hướng không dẫn đến lời giải. Ví dụ1. Tìm số có 6 chữ số mà tổng bình phương các chữ số chia hết cho 3. Giai đoạn sinh: tạo ra số có 6 chữ số và ta gọi các chữ số từ trái qua phải lần lượt là a, b, c, d, e, f thì 0 < a <= 9 , 0 <= b, c, d, e, f <= 9. Giai đoạn thử: nểu a*a + b*b + c*c + d*d + e*e + f*f chia hết cho 3 thì chon, ngược lại, tạo ra số khác. Ví dụ 2. Một xâu nhị phân được gọi là thưa nếu trong xâu không có hai chữ số 1 đứng kề nhau. Tìm xâu nhị phân thưa có chiều dài n. Giai đoạn sinh: Tạo ra một xâu nhị phân S có chiều dài n. Giai đoạn thử: Kiểm tra có phải xâu thưa không? (Pos(‘11’,S) = 0). Trong hai ví dụ trên, sinh viên có thể lập trình để tìm tất cả các lời giải của bài toán, chẳng hain tìm tất cả các xâu nhị phân thưa có chiều dài n cho trước. Ví dụ 3. Một bệnh nhân có một vài triệu chứng, chẳng hạn: sốt cao về buổi chiều, ho và mệt mỏi ,. Bác sĩ có chẩn đoán nghi bị lao phổi, người ta sẽ cho làm ngay xét nghiệm, nếu đúng là dương tính thì kết luận và điều trị bệnh lao phổi, ngược lai, băt buộc bác sĩ phải chuyển hướng suy nghĩ sang một bệnh khác, v.v   51 9. Phương pháp thoả mãn ràng buộc. Phương pháp thoả mãn ràng buộc hổ trợ cho phương pháp sinh và thử, khi chú ý tới một số ràng buộc áp đặt lên các nút trong không gian bài toán. Mục đích đặt ra là xác định đường đi trong đồ thị không gian bài toán, đường đi từ trạng thái đầu đến trạng thái cuối đáp ứng một vài ràng buộc nào đó. Do vậy quá trình tìm kiếm lời giải bao gồm hai phần liên quan chặt chẽ với nhau: - Tìm kiếm trong không gian các ràng buộc. - Tìm kiếm trong không gian các bài toán ban đầu. Nội dung của phương pháp như sau: Thực hiện các bước từ a) đến e) dưới đây cho đến khi tìm được lời giải đày đủ của bài toán hoặc tất cả các đương đều đã duyệt qua nhưng không cho kết quả. a) Chọn một đỉnh chưa được xét trong đồ thị tìm kiếm. b) Áp dụng các luật suy diễn trên các ràng buộc đối với đỉnh đã chọn để tạo ra tập các ràng buộc mới. c) Nếu tập các ràng buộc mới có mâu thuẫn thì đưa ra thông báo đường đi hện thời tới nút đang xét dẫn tới bế tắc. d) Nếu tập ràng buộc mô tả lời giải đầy đủ của bài toán thì dừng và đưa ra thông báo thành công. Ngược lai, sang bước sau. e) Áp dụng các luật biến đổi không gian trạng thái tương ứng để tạo ra lời giải bộ phận, tương hợp với tập các ràng buộc hiện thời. Thêm các lời giải bộ phận này vào đồ thị tìm kiếm. Ví dụ. Xét bài toán điền các chữ số phân biệt thay cho các chữ cái S, E, N, D, M, O, R, Y sao cho phép cộng sau là đúng: SEND MORE MONEY Các ràng buộc ban đầu: - Các chữ cái khác nhau không nhận cùng một giá trị. - Các ràng buộc số học (cộng có nhớ hoặc không có nhớ.   52 Gọi C1, C2, C3, C4 lần lượt lá số nhớ của các cột từ phải sang trái. Khi đó ta xây dựng các ràng buộc cụ thể như sau: E, N, D,O, R, Y thuộc tập {0 ..9} (1) S, M thuộc tập {1..9} (2) C1, C2, C3, C4 thuộc tập {0,1} (3) D + E = Y + 10*C1 (4) N + R + C1 = E + 10*C2 (5) E + O + C2 = N + 10*C3 (6) S + M + C3 = O + 10*C4 (7) M = C4 (8) Từ ràng buộc (2) và (8) suy ra M = 1 và C4=1 (9) Từ ràng buộc (7) và (9) suy ra S +C3 = O + 9, lúc này có hai phương án để lựa chọn: Phương án 1: C3 = 0, khi đó ta có S = O + 9, như vậy S = 9 và O = 0 (10-1) Từ ràng buộc (6) ta có E + C2 = N, suy ra C2 = 1 và E + 1 = N (11-1) Từ ràng buộc (5), ta có R + C1 = 9, như vậy R = 8 và C1 = 1 (12-1) (do kết hợp với các ràng buộc (2) và (10-1). Từ ràng buộc (4) ta có D + E = Y +10. Đến bứơc này ta có thể khảng định các giá trị của D, E, Y chỉ có thể nhận trong tập {2, 3, 4, 5, 6, 7}. Ngoài ra D + E >= 12. Vì vậy chỉ có các khả năng sau có thể xãy ra: - D = 5 và E = 7 - D = 7 và E = 5 (hai truờng hợp này Y = 2) - D = 6 và E = 7 - D = 7 và E = 6 (hai trường hợp sau Y = 3) Xét khả năng thứ nhất. Từ ràng buộc (11-1) ta suy ra N = 8 mâu thuẫn với (12- 1) nên bị loại   53 Xét khả năng thứ hai. Từ ràng buộc (11-1) ta suy ra N= 6. Kiểm tra điều kiện bài toán đều thoả mãn. Vậy ta có nghiệm là: S = 9, E = 5, N= 6, D = 7, M= 1, O = 0, R = 8, Y = 2. Xét khả năng thứ ba. Từ ràng buộc (11-1) suy ra N = 8 mâu thuẫn với (12-1) Xét khả năng thứ tư. Từ ràng buộc (11-1) suy ra N=7 = D mâu thuẫn. Phương án 2. C3 = 1. Từ ràng buộc (7) ta có S = O + 8, suy ra S = 8 và O = 0 (10-2) (vì M=1 và S <= 9). Từ ràng buộc (6) ta có E = N +10 mâu thuẫn với ràng buộc (1). vậy phương án 2 không có lời giải. 10. Cài đặt một số giải thuật. Một số quy ước:  Giả sử đồ thị G được cho bởi ma trận kề A.  Các danh sách MO và DONG được lưu trong cùng một mảng, với các chỉ số riêng.  Mảng logic Dau dùng để đánh dấu các đỉnh đã xét (nằm trong danh sách DONG 10.1. Tìm kiếm rộng.  Danh sách MO và DONG được lưu trong mảng Q, d và c là chỉ số của phần tử đầu và cuối của queue Q.  V = { 1..n}  Thủ tục Duyet_rong(i) đánh dấu tất cả các đỉnh từ i có thể đến được đỉnh đó. Procedure Khoitao; Begin Fillchar (Dau, n, True); End; Procedure Duyet_rong (i:byte); Var Q: array [1..100] of byte;   54 d, c, j, k: byte; Begin d:=1; {Khởi tạo hàng đợi rỗng } c:=1; Q[c]:= i; Dau[i]:= false; While d<=c do begin j:= Q[d]; inc(d); for k:=1 to n do if (A[j,k]=1) and Dau[k] then begin inc(c); Q[c]:=k; Dau[k]:=false; end; end; End; Ví dụ 1. Tìm đường đi từ đỉnh i0 đến đỉnh j0 của đồ thị G. Dữ liệu được lưu vào file Text có cấu trúc như sau: - Dòng đầu tiên chứa 3 số n, i0, j0 (n là số đỉnh của đồ thị) - n dòng tiếp theo lần lượt chứa giá trị n dòng của ma trận A. Tên file được nhập từ bàn phím khi thực hiện chương trình. Giá trị của mảng Truoc tạ vị trí j Truoc[j] xác định đỉnh đứng trước j trong đường đi tìm được. Program đuongdi; Var A: array[1..50,1..50] of byte;   55 Dau: array[1..50] of boolean; Truoc: array[1..50] of byte; n, i0, j0: byte; Procedure khoitao; Var i, j : byte; f:text; tenfile:string; Begin write(‘ten file’); readln(tenfile); assign(f, tenfile); reset(f); readln(f,n,i0,j0); for i:=1 to n do begin for j:=1 to n do read(f, A[i,j]); readln(f); end; close(f); Fillchar (Dau,n,true); End; Procedure BFS(i:byte); Var Q: array [1..50] of byte; d,c,j,k: byte; Begin d:=1;   56 c:=1; Q[c]:=i; Dau[i]:=false; Truoc[i] := 0; While d<=c do begin j:=Q[d]; inc(d); for k:=1 to n do if (A[j,k]=1) and Dau[k] then begin inc(c) ; Q[c]:=k; Dau[k]:=false; Truoc[k] := j; end; end; End; Procedure inkq(j: byte); Begin if Truoc[j] 0 then inkq(truoc[j]); write(j:4); End; Procedure Duyet; Var i:byte; Begin BFS(i0); if Dau[j0] then   57 inkq(j0) else writeln(‘ Khong co duong di’); End; BEGIN {main} Khoitao; Duyet; Readln; END. Ví dụ 2. Tìm số thành phần liên thông của một đồ thị . Dữ liệu được lưu vào file Text có cấu trúc như sau: - Dòng đầu tiên chứa số n (số đỉnh của đồ thị) - n dòng tiếp theo lần lượt chứa giá trị n dòng của ma trận A. - Tên file được nhập từ bàn phím khi thực hiện chương trình. Program lienthong; Var A: array[1..50,1..50] of byte; Dau: array [1..50] of boolean; n, So:byte; Procedure khoitao; Var i, j : byte; f:text; tenfile:string; Begin write(‘ten file’); readln(tenfile); assign(f, tenfile);   58 reset(f); readln(f,n); for i:=1 to n do begin for j:=1 to n do read(f, A[i,j]); readln(f); end; close(f); Fillchar (Dau,n,true); So:=0; End; Procedure BFS(i:byte); Var Q: array [1..50] of byte; d,c,j,k: byte; Begin d:=1; c:=1; Q[c]:=i; Dau[i]:=false; While d<=c do begin j:=Q[d]; inc(d); for k:=1 to n do if (a[j,k]=1) and Dau[k] then begin inc(c) ;   59 Q[c]:=k; Dau[k]:=false; end; end; End; Procedure Duyet; Var i:byte; Begin For i:=1 to n do If Dau[i] then begin inc(So); BFS (i); end; writeln(‘So thành phần liên thông:’, So); End; BEGIN {main} Khoitao; Duyet; Readln; END.   60 10.2. Tìm kiếm sâu. Với giả thiết như duyệt rộng, do MO hoạt động như stack nên dùng thủ tục đệ quy. Procedure DFS (i:byte); {Depth First Search} {Xuất phát từ đỉnh i, đánh dấu các đỉnh được xét khi tìm kiếm theo chiều sâu} Var j: byte; Begin Dau[i]:=false; For j:=1 to n do If (a[i,j]=1) and Dau[j] then DFS (j); End; Ví dụ 1. Tìm đường đi từ đỉnh i0 đến đỉnh j0. Program Duong_di; Var A: array[1..50,1..50] of byte; Truoc: array [1..50] of byte; Dau: array [1..50] of boolean; n, i0, j0: byte; Procedure Khoitao; Var i, j : byte; f:text; tenfile:string; Begin write(‘ten file’); readln(tenfile);   61 assign(f, tenfile); reset(f); readln(f,n,i0,j0); for i:=1 to n do begin for j:=1 to n do read(f, a[i,j]); readln(f); end; close(f); Fillchar (Dau,n,true); End; Procedure  DFS (i:byte);   Var j: byte; Begin Dau[i]:=false; For j:=1 to n do If (a[i,j]=1) and Dau[j] then DFS (j); End; Procedure inkq(j: byte); Begin if Truoc[j] 0 then inkq(truoc[j]); write(j:4); End; Procedure duyet;   62 Begin DFS(i0); if dau[j0] then inkq(j0) else writeln(‘Khong co duong di’); End; BEGIN {main} Khoitao; Duyet; Readln; END. Ví dụ 2. Tìm tất cả hoán vị của (1,2,...n) Program hoanvi; Var A:array [1..50] of byte; n:byte; Dau: array [1..50] of boolean; Procedure Khoitao; Begin write(‘n = ‘); readln(n); Fillchar(Dau,n, true); End;   63 Procedure DFS (i:byte); Begin if i<n then for j:=1 to n do if Dau[j] then begin A[i]:=j; Dau[j]:=false; DFS (j); Dau[j]:=true; end else begin j:=1; While not Dau[j] do inc (j); a[n]:=j; begin for j:=1 to n do write (A[j]:4); witeln; end; end; End; BEGIN {main} Khoitao; DFS (1); Readln; END.   64 10.3. Thuật toán AT – Tìm kiếm cưc tiểu. Giả thiết dữ liệu lưu trữ như tìm kiếm rộng. cp là mảng chi phí của đồ thị G. Đồ thị G được lưu trữ bởi ma trận chi phí cp, trong đó cp[i,j] = Vocung có nghĩa là không có cung (i,j). Procedure ddcuctieu; Const Vocung = 70000; Var A: array[1..50,1..50] of byte; Truoc: array [1..50] of byte; Dau: array [1..50] of boolean; cp: array[1..50, 1..50] of word; n, i0, j0: byte; Procedure Khoitao; Var i, j : byte; f:text; tenfile:string; Begin write(‘ten file’); readln(tenfile); assign(f, tenfile); reset(f); readln(f,n,i0,j0); for i:=1 to n do begin   65 for j:=1 to n do read(f, cp[i,j]); readln(f); end; close(f); Fillchar (Dau,n,true); End; Procedure inkq(j: byte); Begin if Truoc[j] 0 then inkq(truoc[j]); write(j:4); End; Procedure Timkiem; Begin g[i0]:=0; truoc[i0]:=0; d:=1; c:=1; Q[c]:=i0; While d<=c do begin k:=d; for l:=d+1 to c do if g[q[l]]<g[q[k]] then k:=l; tam:=q[d]; q[d]:=q[k];   66 q[k]:=tam; m:=q[d]; inc(d); if m=j0 then inkq(j0) else for l:=1 to n do if (cp[m,l]< vocung) then if dau[l] then begin inc(c); q[c]:=l; dau[l]:=false; g[l]:=g[m]+cp[m,n]; truoc[l]:=m; end else if g[l]>g[m]+cp[m,n] then begin g[l]:= g[m]+cp[m,n]; truoc[l]:=m; end; end; End; Begin Khoitao; Timkiem; End;   67 10.4. Tìm kiếm leo đồi. Trong chương trình cài đặt này, chúng ta quy ước nếu đỉnh đang xét là đỉnh u, thì đỉnh kề với u có khả năng đến đích nhất là đỉnh có khoảng cách với u lớn nhất. Khi đó giải thuật leo đồi có thể trình bày lại như sau. Leodoi(i,j): Thực hiện giải thuật leo đồi từ đỉnh i đến đỉnh j. - Nếu (i, j) E : d=c[i,j], push(i,j,k), exit - Nếu (i,j) E: Tìm k sao cho c[i,k]=max {c[l,k]/ lT[i] and dau[i,l]}: Nếu có (d=c[l,k]): dau[i,l]=false, push(i,j,d), Leodoi(k,j) Ngược lại (d=0): pop(k,j,d), leodoi(k,j) Dữ liệu đựơc thiết kế như sau: - Mảng A lưu danh sách các cung của đồ thị G - S là stack lưu danh sách các đỉnh sẽ được xét và Top là đỉnh của S - i0, j0 là đỉnh xuất phát và đỉnh kết thúc - Toàn bộ thông tin được lưu trong file dạng Text có cấu trúc như sau: dòng đầu lưu m (số cung của đồ thị), i0, j0; m dòng tiép theo mỗi dòng chứa thông tin của mộtcung đồ thị G (đỉnh đầu, đỉnh cuối và độ dài cung). Procedure Leodoi; Type cung = record dau, cuoi: byte; kc: word; end; Var S, A: array[1..50] of cung; B: array[1..50] of boolean;   68 m,i0,j0, Top: byte; Procedure Khoitao; Var f: text; l: byte; d: word; tenfile: string; begin write(‘Nhap ten file: ‘); readln(tenfile); assign(f,tenfile); reset(f); readln(f,m,i0,j0); for l:=1 to m do with A[l] do readln(f,dau, cuoi, kc); fillchar(B, l, false); Top:= 0; end; Procedure Pop( Var i,j: byte; var d: word); {Lấy một bản ghi (i,j,d) từ S} begin with S[Top] do begin i:= dau; j:= cuoi; d:= kc; end;   69 dec(Top); end; Procedure TimKiem(i: byte; Var j: byte; var d: word); { Tìm cung (i,j) có c[i,j] lớn nhất, nếu có thì d = c[i,j] và đấnh dấu cung ơi,jư là true, ngược lại d = 0 } Var l,p: byte; begin d:=0; for l:= 1 to m do if (A[l].dau = i) and (A[l].kc > d) and not B[l] then begin j:= A[l].cuoi; p:= l; d:= A[l].kc; end; B[l]:= true; end; Function DenDich(i,j: byte; var d:word): boolean; Var l: byte; begin for l:= 1 to m do if (A[l].dau = i) and (A[l].cuoi = j) then begin d:= A[l].kc; DenDich:= true;   70 end else begin DenDich:= false; d:= 0; end; end; Procedure Inkq(j:byte); Var d:word; k: byte; begin d:=0; for k:= 1 to Top do begin write(S[k].dau); d:=d + S[k].kc; end; writeln(j); writeln(‘ Chi phi: ‘,d); end; Procedure Duongdi(i,j: byte); Var k,d: byte; Begin if Dendich(i,j) then begin   71 push(i,j,d); inkq(j); exit; end; Timkiem(i,k,d); if d > 0 then begin push(i,j,d); duongdi(k,j); end else if Top > 0 then begin pop(i,j,d); duongdi(i,j); end else writeln(‘Khong co duong di’); end; Begin {leo doi} Khoitao; Duongdi(i0,j0); end;   72 11. Bài tập. Bài tập 1. Cho ma trận kề A= (aij) biểu diễn một đồ thị vô hướng G = (V,E) dưới đây: trong đó aij=  nếu (i,j)E, ngược lại aij là chi phí để đi từ đỉnh i sang đỉnh j. a. Hãy tìm đường đi từ đỉnh 1 sang đỉnh 4 theo các phương pháp tìm kiếm rộng và tìm kiếm sâu. b. Tìm đường đi ngắn nhất từ đỉnh 1 sang đỉnh 4 Lời giải - Vẽ đồ thị G được biểu diễn bởi ma trận kề A ở trên 1  2 2 3 6 5 4 5 6 8 3 34  7                   0263 2058 503 68307 3704 40   73 - Phương pháp duyệt rộng n t(n) open  close 1 2 3 6 4 dichdừng 2 1, 3, 6 2, 4, 5, 6 2, 3, 5 1 2 3, 6 6, 4, 5 4, 5 1 1, 2 1, 2, 3 1, 2, 3, 6 Đường đi từ đỉnh 1 đến đỉnh 4 theo phương pháp duyệt rộng là: 1 2 3 4 - Phương pháp duyệt sâu n t(n) open  close 1 2 6 5 4 dichdừng 2 1, 3, 6 2, 3, 5 3, 4, 6 1 2 3, 6 3, 5 3, 4 1 1, 2 1, 2, 6 1, 2, 6, 5 Đường đi từ đỉnh 1 đến đỉnh 4 theo phương pháp duyệt sâu là: 1 2 6 5 4 - Phương pháp tìm kiếm cực tiểu n t(n) open close 1 2 6 5 3 4DICH  dừng 2 1, 3, 6 2, 3, 5 3, 4, 6 2, 4, 5, 6 10 24 311, 67 311, 59 311, 414 414 1 1, 2 1, 2, 6 1, 2, 6, 5 1, 2, 6, 5, 3 Vậy đường đi ngắn nhất: 1 2 6 5 4 với chi phí 14   74 Bài tập 2. Người ta sử dụng hai bình chứa có dung tích lần lượt là 3(lít) và 4(lít) để đong 2(lít) nước. giả sử lượng nước được lấy từ vòi không hạn chế và công để lấy nước từ vòi cho đầy một bình là 3, công để đổ nước trong một bình ra ngoài là 2 và đổ nước từ bình này sang bình khác thì tốn công là 5. Hãy chỉ ra quá trình tìm kiếm lời giải bằng phương pháp tìm kiếm theo chiều rộng và tìm kiếm leo đồi. Lời giải - Phương pháp tìm kiếm theo chiều rộng n t(n) open  close (0,0) (0,4) (3,0) (3,4) (3,1) (0,3) (0,1) (3,3) (1,0) (2,4) (0,4), (3,0) (0,0), (3,4), (3,1) (0,0), (3,4), (0,3) (0,4), (3,0) (0,1), (3,0), (3,4), (0,4) (0,0), (0,4), (3,3), (3,0) (0,0), (3,1), (0,4), (1,0) (0,3), (3,0), (2,4) (0,0), (3,0), (1,4), (0,1) (0,0) (0,4), (3,0) (3,0), (3,4), (3,1) (3,4), (3,1), (0,3) (3,1), (0,3) (0,3), (0,1) (0,1), (3,3) (3,3), (1,0) (1,0), (2,4) (2,4), (1,4), (0,0) (0,0), (0,4) (0,0),(0,4),(3,0) (0,0),(0,4),(3,0), (3,4) (0,0),(0,4),(3,0), (3,4), (3,1) (0,0),(0,4),(3,0), (3,4), (3,1), (0,3) (0,0),(0,4),(3,0), (3,4), (3,1), (0,3), (0,1) (0,0),(0,4),(3,0), (3,4), (3,1), (0,3), (0,1), (3,3) (0,0),(0,4),(3,0), (3,4), (3,1), (0,3), (0,1), (3,3), (1,0) Quá trình đong nước theo phương pháp duyệt rộng là: (0,0)(3,0)(0,3)(3,3)(2,4)   75 - Phương tìm kiếm leo đồi (giả thiết đỉnh kề với đỉnh đang xáe và có khoảng cách đên đỉnh đó lớn nhất là đỉnh có triển vọng đến đích nhất) ((0,0), (2,4))E  k= (3,0) c[(0,0), (3,0)]=5 ((3,0), (2,4)) E  k= (0,3) c[(3,0), (0,3)]=5 ((0,3), (2,4)) e  k= (3,3) c[(0,3), (3,3)]=5 ((3,3), (2,4)) E  dừng c[(3,3), (2,4)]=5 Quá trình đong nước theo phương pháp leo đồi là: (0,0)(3,0)(0,3)(3,3)(2,4) với chi phí 20 Bài tập 3. Đại dương được xem như là một mặt phẳng toạ độ trên đó có n hòn đảo với toạ độ lần lượt là (x1, y1), (x2, y2), , (xn, yn). Một chiếc ca nô xuất phát từ đảo d1 muốn tuần tra đến đảo d2. bình xăng của ca nô chỉ chứa đủ xăng để đi được một quãng đường dài không quá m (km). Trên đường đi ca nô có thể ghé một số đảo nào đó để tiếp thêm xăng, lúc này ca nô được tiếp thêm xăng đầy bình chứa. Hãy chỉ ra một đường đi từ đảo d1 đến đảo d2 sao cho số lần ghé đảo trung gian để tiếp thêm xăng là ít nhất. Hướng dẫn Ta xem hai đảo là kề nhau nếu khoảng cách giữa chúng không vượt quá m (km). Bài toán cần tìm đường đi từ đảo d1 đến đảo d2 thông qua các đảo kề nhau. Thuật toán tìm kiếm theo chiều rộng cho phép tìm đường tìm ra đường đi nối hai đảo qua ít cạnh trung gian nhất (tức là ít đảo trung gian nhất). Dữ liệu vào lưu trong file dạng text, dòng đầu chứa số đảo n, dòng thứ hai chứa khoảng cách lớn nhất cano có thể đi liên tục, n dònh tiếp theo mỗi dòng chứa hai giá trị tương ứng với toạ độ của mỗi đảo.   76 Bài tập 4. Một mạng lưới giao thông giữa n thành phố (các thành phố được đánh số từ 1 đến n) được cho bởi ma trận a=(aij)n*n , trong đó: 0, nếu không có đường đi trực tiếp từ i đến j aij= 1, nếu có đường đi trực tiếp từ i đến j và là đường đi an toàn 2, nếu có đường đi trực tiếp từ i đến j nhưng phải qua một chặng đường nguy hiểm Quy ước: aii=1, i =1..n Cho trước hai thành phố i0, i1. hãy tìm một đường đi từ i0 đến i1 sao cho số chặng đường nguy hiểm phải đi qua là ít nhất. Hướng dẫn: Trước hết phải xác định đồ thị biểu diễn bài toán. Ở đây dễ thấy rằng mỗi thành phố tương ứng với một đỉnh của đồ thị, vấn đề chỉ còn xác định tập cung E căn cứ vào giả thiết của bài toán. Bài tập 5. Cho bảng vuông gồm m*n ô. Trên mỗi ô ghi số 0 hay 1. a. Từ một ô nào đó có thể chuyển sang ô chứa số 1 có chung cạnh với nó. giả sử đang ở ô (h,c). Hãy tìm xem có cách di chuyển từ ô này ra một ô ở mép bảng hay không? Tìm cách chuyển qua ít ô nhất. b. Một miền của bảng là tập hợp các ô có chung cạnh và có cùng giá trị. hãy đếm xem bảng có bao nhiêu miền. miền lớn nhất có bao nhiêu ô. c. Cho phép thay đổi giá trị tất cả các ô trong cùng một miền. Hãy xác định miền cần thay đổi để số miền giảm nhiều nhất. d. Hãy xác định miền cần thay đổi để thu được một miền mới lớn nhất. Hướng dẫn: Mỗi ô tương ứng với một đỉnh của đồ thị. Hai đỉnh kề nhau khi và chỉ khi hai ô tương ứng có thể chuyển sang nhau. Mỗi miền của bảng tương ứng với một miền liên thông của đồ thị.   77 Bài tập 6. Lập chương trình đối với bài toán đong nước, với các số m, n, k là các số dương bất kỳ được nhập từ bàn phím khi thực hiện chương trình. Hướng dẫn: Sử dụng thuật toán tìm kiếm rộng sẽ cho số lần thao tác là ít nhất. Bài tập 7. Một toà lâu đài được mô tả bằng một hình chữ nhật có m*n ô. Giữa các ô có một số bức tưòng ngăn cách chia lâu đài thành các phòng. Như vậy, mỗi phòng tương ứng với tập các ô thông nhau. Tại ô (i,j), cho biết thông tin có tường ngăn giữa ô này với bốn ô kề với nó không bởi giá trị aij là một số nhị phân 4 chữ số tương ứng ô (i,j) có (1) hoặc không có (0) tường ở phía Tây, Bắc, Đông, Nam. Ví dụ aij = 1001 có nghĩa là ô (i,j) có tường ở phía Tây và Nam, nhưng không có tường ở phía Bắc và Đông. Hãy viết chương trình thực hiện các yêu cầu sau: a. Đếm số phòng của toà lâu đài. b. Cho biết phòng lớn nhất có diện tích là bao nhiêu ô. c. Cho biết nên phá bức tường ngăn hai phòng nào để được một phòng mới có diện tích lớn nhất. Hương dẫn: Giá trị aij có thể nhận tương ứng với số thập phân từ 0 đến 15. Vì vậy ta lưu dữ liệu trong file dạng text có cấu trúc như sau: dòng đầu chứa hai số m,n. Từ dòng thứ hai đến dòng thứ m+1, chứa các hàng của ma trận A = (aij). Kết quả đưa ra file dạng text có cấu trúc như sau: dòng đầu chứa số phòng, dònh hai chứa diện tíach phòng lớn nhất và dong ba chứa hàng, cột, hướng của bức tường cần phá. Chẳng hạn dữ liệu vào là 4 6 11 6 11 6 3 10 6 7 9 6 13 5 15 5 1 10 12 7 13 7 5 13 11 10 8 10 12 13   78 Dữ liệu ra sẽ là: 5 9 4 1 Dong Bài tập 8. Một sân chơi hình chữ nhật gồm m*n ô đơn vị. Trên mỗi ô (i,j) có đóng các trụ bê tông chiều cao aij. Giả thiết nước không thấm qua được các cạnh giữa hai trụ bê tông kề nhau. Sau một trận mưa đủ lớn, hãy tính nước đọng lại trên sân. Hướng dẫn Chia nước thành từng tầng có chiều cao bằng 1. Tính thể tích nước đọng trên mỗi tầng theo thuật toán loang tìm thành phần liên thông. Bài tập 9. Tìm 2 chữ số phân biệt a và b sao cho thoã mãn hai điều kiện sau: a. a2b chia hết cho 3 b. a2b - ab=110 Bài tập 10. Gảii bài toán đoán chữ sau DONALD CROSS + GERALD + ROADS ROBERT DANGER   79 Bài tập 11. Cho số có hai chữ số. Nếu viết thêm hai chữ số về bên phải số đó thì được số mới lớn hơn số đã ho là 1986 đơn vị. Hãy tìm số đã cho và hai chữ số viết thêm đó. Bài tập 12. Giải bài toán đoán chữ sau: T + TH THA THAN 4321 Chương trình tham khảo Program cano_di_tuan; { Bài tập 3} uses crt; type dao = record x,y: integer; end; var n,d1,d2,so: byte; m: word; a: array[byte] of dao; b: array[byte] of boolean; tr: array[byte] of byte; procedure nhap; var f: text; s: string[20];   80 i: byte; begin clrscr; write('ten file du lieu:'); readln(s); assign(f,s); reset(f); readln(f,n); readln(f,m); for i:=1 to n do with a[i] do readln(f,x,y); close(f); end; procedure indulieu; var i: byte; begin writeln('so dao:',n); writeln('gioi han khoang cach:',m); for i:=1 to n do with a[i] do writeln('toa do dao ',i,' : (',x,',',y,')'); end; procedure khoitao; var i: byte; begin for i:=1 to n do   81 b[i]:= true; end; function kc(i,j: byte):real; begin kc:= sqrt(sqr(a[i].x-a[j].x)+sqr(a[i].y-a[j].y)); end; procedure bfs(i: byte); var j,k,d,c: byte; q: array[byte] of byte; begin d:=1; c:=1; q[1]:=i; b[i]:= false; while d<=c do begin j:= q[d]; d:=d+1; for k:=1 to n do if b[k] and (kc(k,j) <= m) then begin c:=c+1; q[c]:=k; b[k]:= false; tr[k]:=j; end;   82 end; end; procedure inketqua; var i:byte; begin write('duong di ghe dao it nhat nhu sau: '); write(d1); i:=d1; so:=0; while id2 do begin write('-->',tr[i]); so:=so+1; i:=tr[i]; end; writeln; writeln('duong di tren ghe qua ',so-1,' dao'); end; procedure timduongdi; begin write('dao xuat phat: '); readln(d1); write('dao ket thuc: '); readln(d2); bfs(d2); if b[d2] then write('khong co duong di tu ',d1,' den ',d2)   83 else inketqua; readln; end; BEGIN nhap; khoitao; indulieu; timduongdi; END. Program laudai; { Bài tập 7} uses crt; type size = 0..100; var m,n,so,p,hang,cot: size; A:array[size,size] of 0..15; ph: array[size,size] of word; S: array[size] of word; dt: word; huong: string[4]; procedure nhap; var f: text; i,j: size; begin clrscr;   84 assign(f,'input.pas'); reset(f); read(f,m,n); for i:=1 to m do for j:=1 to n do read(f,A[i,j]); close(f); end; procedure khoitao; var i,j: size; begin for i:=1 to m do for j:=1 to n do ph[i,j]:=0; so:=0; end; procedure bfs(i,j: size); var qh,qc: array[size] of size; d,c,k,l: size; begin ph[i,j]:= so; d:=1; c:=1; qh[1]:=i; qc[1]:=j;   85 while d<=c do begin k:= qh[d]; l:= qc[d]; d:=d+1; if A[k,l]>=8 then S[k,l]:=A[k,l]-8 else if (k<m) and (ph[k+1,l]=0) then begin c:=c+1; qh[c]:=k+1; qc[c]:=1; ph[k+1,l]:=so; end; if A[k,l]>=4 then A[k,l]:=A[k,l]-4 else if (l<n) and (ph[k,l+1] = 0) then begin c:=c+1; qh[c]:=k; qc[c]:=l+1; ph[k,l+1]:=so; end; if A[k,l]>=2 then A[k,l]:= A[k,l]-2 else if (k>1) and (ph[k-1,l] = 0) then   86 begin c:=c+1; qh[c]:=k-1; qc[c]:=l; ph[k-1,l]:=so; end; if A[k,l] >=1 then A[k,l]:= A[k,l]-1 else if (l>1) and (ph[k,l-1]=0) then begin c:=c+1; qh[c]:=k; qc[c]:=l-1; ph[k,l-1]:=so; end; end; end; procedure demphong; var i,j: size; begin for i:=1 to m do for j:=1 to n do if ph[i,j] = 0 then begin so:= so+1; bfs(i,j);   87 end; end; procedure smax; var i: word; j,k: size; begin dt:=0; for i:=1 to so do begin S[i]:=0; for j:=1 to m do for k:=1 to n do if ph[j,k]=i then S[i]:= S[i]+1; if S[i] > dt then dt:= S[i]; end; end; procedure phatuong; { Chỉ cần phá phía Đông hoặc phía Nam, phía Tây của ô (i,j) tương ứng là phía Đông của ô (i,j-1), tươnh tự, phía Bắc của ô (i,j) tương ứng phía Nam của ô (i- 1,j)} var i,j: size; max,tg: word; begin max:=0; for i:=1 to m do   88 for j:=1 to n do begin if i< m then if ph[i,j] ph[i+1,j] then begin tg:= S[ph[i,j]] + S[ph[i+1,j]]; if tg >= max then begin hang :=i; cot:=j; huong:= 'nam'; max:= tg; end; end; if j<n then if ph[i,j] ph[i,j+1] then begin tg:= S[ph[i,j]] + S[ph[i,j+1]]; if tg >= max then begin hang:=i; cot:=j; huong:= 'dong'; max:= tg; end; end; end; end;   89 procedure inkq; var i,j: size; f: text; begin assign(f,'out.pas'); rewrite(f); writeln(f,so); writeln(f,dt); writeln(f,hang,' ',cot,' ',huong); close(f); end; BEGIN nhap; khoitao; demphong; smax; phatuong; inkq; END.