Kỹ thuật lập trình - Chương 2: Thuật toán – Thuật giải

TRẦN MINH THÁIEmail: minhthai@huflit.edu.vnWebsite: www.minhthai.edu.vn Cập nhật: 05 tháng 09 năm 2015Chương 2. Thuật toán – Thuật giải1Nội dungThuật toán?Thuật toán vs Thuật giảiThuật giải Heuristic & các nguyên lýTìm kiếm chiều sâu & Tìm kiếm chiều rộngTìm kiếm leo đồiTìm kiếm ưu tiên tối ưuMột số thuật giải cơ bảnThuật toán?Là một thủ tục tính toán xác định nhận các giá trị hoặc một tập các giá trị (input) và sinh ra một vài giá trị hoặc tập giá trị (output)Cách thức/ quy trình thực hiện hoàn thành một công việc xác định cụ thể nào đó. VD Cộng 2 số, tính tổng dãy Fibonaci, Đặc trưng của Thuật toánTính đúng đắnTính dừngTính xác địnhTính hiệu quảTính phổ quát??? Đặc trưng nào quan trọng nhất ???Đặc trưng của Thuật toán [1] Tính đúng đắn * Đảm bảo kết quả đúng sau khi thực hiện đối với bộ dữ liệu đầu vào[2] Tính dừng Dừng  Sau một vài bước thực hiệnĐặc trưng của Thuật toán [3] Tính xác định - Rõ ràng, cụ thể - Không nhập nhằng, gây hiểu lầm  hiểu, cài đặt[4] Tính hiệu quả - Giải quyết trong thời gian, điều kiện cho phép - Đáp ứng yêu cầu người dùng[5] Tính phổ quát Có thể giải quyết được một lớp bài toán tương tựCách biểu diễn thuật toán02 cách phổ biến[1] Mô tả các bước thực hiện của thuật toán[2] Sử dụng sơ đồ thuật toánCách biểu diễn thuật toán[1] Mô tả các bước thực hiện của thuật toán - Ngôn ngữ tự nhiên - Mã giả (Pseudocode): Lai ghép ngôn ngữ tự nhiên với mã của ngôn ngữ lập trìnhVD Mô tả các bước thực hiện của thuật toán tìm USCLN của hai số nguyên – NN tự nhiênInput: Hai số nguyên a, bOutput: USCLN của a và bThuật toán:Bước 1: Nếu a = b thì USCLN là aBước 2: Nếu a > b thì tìm USCLN của a - b và b, quay lại Bước 1Bước 3: Nếu a b) THEN a = a – b; ELSE b = b – a;END WHILERETURN a;Một số từ khóa mã giả cơ bảnIF THEN ENDIFIF THEN ... ELSE ... ENDIFWHILE DO ENDWHILEDO UNTIL DISPLAY RETURN Cách biểu diễn thuật toán[2] Sử dụng sơ đồ thuật toán (flowchart) Dùng các ký hiệu hình học để biểu diễn quá trình thực hiệnBắt đầu/ kết thúcĐiều kiệnRẽ nhánhNhập/ xuấtTrả về giá trịLuồng xử lýKhối xử lýVD Sơ đồ thuật toán tìm trị tuyệt đối của số nguyênInput: Số nguyên nOutput: Giá trị tuyệt đối của nThuật toán:Độ phức tạp thuật toánĐánh giá độ tốt/ xấu của thuật toán cùng loạiĐơn giản, dễ hiểu, dễ cài đặtThời gian thực hiện, sử dụng tài nguyên hệ thống??? Thực tế ??? - Thuật toán hiệu quả  Dễ hiểu, dễ cài đặt? - Ước lượng số phép tính thực hiện  Thời gian?VD Thuật toán sắp xếp mảng một chiều bằng phương pháp đổi chỗ trực tiếpInput: Mảng một chiều a, kích thước NOuput: Mảng a có thứ tự tăng dần Thuật toán: Bước 1: i=1;Bước 2: j = i+1; Bước 3:      Trong khi j sự bùng nổ số lượng các trạng thái Các dữ liệu của bài toán không được cho trước, nhưng hệ thống phải đạt được trong quá trình tìm kiếmPhương pháp TK trên đồ thị KGTTPhát triển từ giải thuật quay lui (back – tracking)Tìm kiếm chiều rộng (breath-first search)Tìm kiếm chiều sâu (depth-first search)TK chiều sâu bằng cách đào sâu nhiều lần (depth-first search with iterative deepening)Tìm kiếm chiều rộngKhởi tạo Open = [A]; Closed = []2. Open = [B,C,D] Closed = [A]3. Open = [C,D,E,F] Closed = [B,A]Open = [D,E,F,G,H]; Closed = [C,B,A]Open = [E,F,G,H,I,J]; Closed = [D,C,B,A]Open = [F,G,H,I,J,K,L]; Closed = [E,D,C,B,A]Open = [G,H,I,J,K,L,M]; Closed = [F,E,D,C,B,A] Tìm kiếm chiều sâuKhởi tạo: Open = [A]; Closed = []Open = [B,C,D]; Closed = [A]Open = [E,F,C,D]; Closed = [B,A]Open = [K,L,F,C,D]; Closed = [E,B,A]Open = [S,L,F,C,D]; Closed = [K,E,B,A]6. Open = [L,F,C,D]; Closed = [S,K,E,B,A]7. Open = [T,F,C,D]; Closed = [L,S,K,E,B,A]8. Open = [F,C,D]; Closed = [T,L,S,K,E,B,A] Tìm kiếm chiều sâu hay chiều rộng?Có cần thiết tìm một đường đi ngắn nhất đến mục tiêu hay không?Sự phân nhánh của không gian trạng tháiTài nguyên về không gian & thời gian sẵn cóKhoảng cách trung bình của đường dẫn đến trạng thái mục tiêuYêu cầu đưa ra tất cả các lời giải/chỉ là lời giải tìm được đầu tiênTìm kiếm chiều sâu bằng cách đào sâu nhiều lầnĐộ sâu giới hạn (depth bound): giải thuật TK sâu sẽ quay lui khi trạng thái đang xét đạt đến độ sâu giới hạn đã địnhTK chiều sâu bằng cách đào sâu nhiều lần: TK sâu với độ sâu giới hạn là 1, nếu thất bại, nó sẽ lặp lại GT TK chiều sâu với độ sâu là 2, GT tiếp tục cho đến khi tìm được mục tiêu, mỗi lần lặp lại tăng độ sâu lên 1GT này có độ phức tạp về thời gian cùng bậc với TK Rộng và TK SâuTìm kiếm leo đồiGiải thuật:Mở rộng trạng thái hiện tại và đánh giá các trạng thái con của nó bằng hàm đánh giá heuristicCon “tốt nhất” sẽ được chọn để đi tiếpGiới hạn: Giải thuật có khuynh hướng bị sa lầy ở những cực đại cục bộ: Lời giải tìm được không tối ưu Không tìm được lời giải mặc dù có tồn tại lời giảiGiải thuật có thể gặp vòng lặp vô hạn do không lưu giữ thông tin về các trạng thái đã duyệt Tìm kiếm leo đồi1. Khởi tạo ngăn xếp S chỉ chứa trạng thái đầu; 2. Lặp 2.1 If S rỗng then {thông báo thất bại; stop}; 2.2 Lấy trạng thái u ở đầu ngăn xếp S; 2.3 If u là trạng thái kết thúc then {thông báo thành công; stop}; 2.4 For mỗi trạng thái v kề u do đặt v vào danh sách L; 2.5 Sắp xếp L theo thứ tự: trạng thái tốt nhất ở đầu danh sách; 2.6 Chuyển danh sách L vào ngăn xếp S; Tìm kiếm leo đồi1. Khởi tạo Open = [A5]; Closed = []2. Đánh giá A5: Open = [B4,C4,D6]; Closed = [A5]3. Đánh giá B4: Open = [C4,E5,F5,D6]; Closed = [B4,A5]4. Đánh giá C4: Open = [H3,G4,E5,F5,D6]; Closed = [C4,B4,A5]5. Đánh giá H3: Open = [O2,P3,G4,E5,F5,D6]; Closed = [H3,C4,B4,A5]6. Đánh giá O2: Open = [P3,G4,E5,F5,D6]; Closed = [O2,H3,C4,B4,A5]7. Đánh giá P3: tìm được lời giải!Tìm kiếm ưu tiên tối ưu (Best-First Search)Tìm kiếm chiều sâu: không quan tâm đến sự mở rộng của tất cả các nhánh Tìm kiếm chiều rộng: không bị rơi vào các nhánh cụtTìm kiếm ưu tiên tối ưu: kết hợp tìm kiếm chiều sâu + tìm kiếm chiều rộng Mở rộng cây theo các nút có nhiều tiềm năng chứa trạng thái đích hơn các nút khácTìm kiếm BFS - Ví dụThuật giải BFS1. Đặt OPEN chứa trạng thái khởi đầu.2. Cho đến khi tìm được trạng thái đích hoặc không còn nút nào trong OPEN, thực hiện : 2.1. Chọn trạng thái tốt nhất (Tmax) trong OPEN (và xóa Tmaxkhỏi OPEN) 2.2. Nếu Tmax là trạng thái kết thúc thì thoát. 2.3. Ngược lại, tạo ra các trạng thái kế tiếp Tk có thể có từ trạng thái Tmax. Đối với mỗi trạng thái kế tiếp Tk thực hiện: Tính f(Tk); Thêm Tk vào OPENThuật giải AT1. Đặt OPEN chứa trạng thái khởi đầu.2. Cho đến khi tìm được trạng thái đích hoặc không còn nút nào trong OPEN, thực hiện : 2.1. Chọn trạng thái (Tmax) có giá trị g nhỏ nhất trong OPEN (và xóa Tmax khỏi OPEN) 2.2. Nếu Tmax là trạng thái kết thúc thì thoát. 2.3. Ngược lại, tạo ra các trạng thái kế tiếp Tk có thể có từ trạng thái Tmax. Đối với mỗi trạng thái kế tiếp Tk thực hiện : g(Tk) = g(Tmax) + cost(Tmax, Tk); Thêm Tk vào OPEN.Thuật giải AKT (Algorithm for Knowlegeable Tree Search)1. Đặt OPEN chứa trạng thái khởi đầu.2. Cho đến khi tìm được trạng thái đích/ không còn nút nào trong OPEN: 2.1. Chọn trạng thái (Tmax) có giá trị f nhỏ nhất trong OPEN (và xóa Tmax khỏi OPEN) 2.2. Nếu Tmax là trạng thái kết thúc thì thoát. 2.3. Ngược lại, tạo ra các trạng thái kế tiếp Tk có thể có từ trạng thái Tmax. Đối với mỗi trạng thái kế tiếp Tk thực hiện : g(Tk) = g(Tmax) + cost(Tmax, Tk); Tính h’(Tk) f(Tk) = g(Tk) + h’(Tk); Thêm Tk vào OPEN.Thuật giải A*1. Open:={s}; Close:={};2. Trong khi (Open khác rỗng ) 2.1 Chọn đỉnh p tốt nhất trong Open 2.2 Nếu p là đỉnh kết thúc thì thoát. 2.3 Di chuyển đỉnh p qua Close và tạo danh sách các đỉnh q có nối với p 2.3.1 Nếu q có trong Open: Nếu (g(q) > g(p) +cost(p,q)) thì g(q) = g(p) +cost(p,q) f(q) = g(q) + h(q); Nút trước của q là p; 2.3.2 Nếu q chưa có trong Open thì g(q) = g(p) + cost(p,q); f(q) = g(q) + h(q); Thêm q vào Open; Nút trước q là p; 2.3.3 Nếu q có trong Close thì Nếu (g(q)>g(p)+cost(p,q)) thì Di chuyển q vào Open; Nút trước của q là p;3. Không tìm được. Thuật giải A* - Ví dụCho đồ thị, trạng thái ban đầu A. Tìm đường đi ngắn nhất đến trạng thái đích BGiá trị tại mỗi đỉnh là giá trị hàm h tương ứngGiá trị tại mỗi cạnh là độ dài đường đi giữa hai đỉnh Thuật giải A* - Ví dụBướcOpenChọn pClosedCác đỉnh q nối với p1A2AAC (gC=9, hC=15, fC=24)D (gD=7, hD=6, fD=13)E (gE=13, hE=8, fE=21)F (gF=20, hF=7, fF=27)3D, E, C, FDA, DE (gE=gD+kc(D,E)=7+4, hE=8, fE=19)H (gH=gD+kc(D,H)=7+8, hH=10, fH=25)4E, C, H, FEA, D, EI (gI=gE+kc(E,I)=11+3, hI=4, fI=18)K (gK=gE+kc(E,K)=11+4, hK=2, fK=17)5K, I, C, H, FKA, D, E, K B (gB=gK+kc(K,B)=15+6, hB=0, fB=21)6I, B, C, H, FIA, D, E, K, IK (gK<gI+kc(I,K)=14+9)Giữ K trong ClosedB (gB=gI+kc(I,B)=14+5, hB=0, fB=19)7B, C, H, FBA, D, E, K, I, BE có trong Open: Cập nhật gEĐỉnh đã có trong OpenĐỉnh đã có trong ClosedCây tìm kiếm tìm đượcA14D67E8413C159F7H108K24I43B0956Thuật giải A* - Bài tậpCho đồ thị, trạng thái ban đầu A. Tìm đường đi ngắn nhất đến trạng thái đích KABCDEFGHK3975863112764687535269150515118Bài toán tô màu đồ thịCho đồ thị vô hướng, hãy tô màu tất cả các đỉnh với số màu ít nhất, sao cho 2 đỉnh nối với nhau được tô khác màu Bài toán tô màu đồ thịGọi k là số màu đã được dùng để tô màuk=1;Trong khi chưa tô hết các đỉnh { Chọn đỉnh p có bậc cao nhất Lặp từ màu 1 đến màu k { Nếu tồn tại màu i khác với màu các đỉnh kề với p thì chọn màu i } Nếu đỉnh p chưa tô màu. Tô màu cho đỉnh p với màu mới k +1}Bài toán tô màu đồ thị - Ví dụCBADEFGHIĐỉnhCDFEHIABGBậc654333222Bài toán tô màu đồ thị - Ví dụCBADEFGHI[1] Tô màu 1 cho đỉnh C[2] Tô màu 2 cho đỉnh D[3] Tô màu 1 cho đỉnh F[4] Tô màu 3 cho đỉnh E[5] Tô màu 3 cho đỉnh H[6] Tô màu 1 cho đỉnh I[7] Tô màu 2 cho đỉnh A[8] Tô màu 2 cho đỉnh B[9] Tô màu 2 cho đỉnh GBài toán tô màu đồ thịVấn đề cài đặt:Loại bỏ đỉnh đã tôĐánh dấu những màu bị cấm tô của mỗi đỉnhBài toán tô màu đồ thịGọi k là số màu đã được dùng để tô màuk=1;Trong khi chưa tô hết các đỉnh { Chọn đỉnh p có bậc cao nhất Lặp từ màu 1 đến màu k Nếu tồn tại màu i không bị cấm tô thì màu tô p = i Nếu đỉnh p chưa tô màu thì k=k+1, màu tô p = k Với những đỉnh q có nối với p Hạ bậc q, thêm màu tô p vào danh sách màu cấm tô của q Gán bậc của đỉnh p = 0}Bài toán tô màu đồ thị - Ví dụCBADEFGHIÁp dụng tô màu cho đồ thị sauĐỉnhBậcC6D5F4E3H3I3A2B2G2Bài toán tô màu đồ thị - Ví dụBước 1: Chọn đỉnh CCác đỉnh nối với C: A, B, D, E, G, H, GĐỉnhBậcBậc mớiMàu cấm tôMàu tôC601D541F44E321H321I33A211B211G211CBADEFGHIBài toán tô màu đồ thị - Ví dụBước 2: Chọn đỉnh DCác đỉnh nối với D: E, F, H, IĐỉnhBậcBậc mớiMàu cấm tôMàu tôD4012F432E211, 2H211, 2I322A111B111G111C001CBADEFGHIBài toán tô màu đồ thị - Ví dụBước 3: Chọn đỉnh FCác đỉnh nối với F: B, H, GĐỉnhBậcBậc mớiMàu cấm tôMàu tôF3021E111, 2H101, 2I222A111B101G101C01D02CBADEFGHIBài toán tô màu đồ thị - Ví dụBước 4: Chọn đỉnh ICác đỉnh nối với I: A, EĐỉnhBậcBậc mớiMàu cấm tôMàu tôI2021A101E101, 2B001H001, 2G001C01D02F01CBADEFGHIBài toán tô màu đồ thị - Ví dụBước 5: Chọn đỉnh AĐỉnhBậcBậc mớiMàu cấm tôMàu tôA0012B001E001, 2H001, 2G001C01D02F01I01CBADEFGHIBài toán tô màu đồ thị - Ví dụBước 6: Chọn đỉnh BĐỉnhBậcBậc mớiMàu cấm tôMàu tôB0012E001, 2H001, 2G001C01D02F01I01A02CBADEFGHIBài toán tô màu đồ thị - Ví dụBước 7: Chọn đỉnh EĐỉnhBậcBậc mớiMàu cấm tôMàu tôE001, 23H001, 2G001C01D02F01I01A02B02CBADEFGHIBài toán tô màu đồ thị - Ví dụBước 8: Chọn đỉnh HĐỉnhBậcBậc mớiMàu cấm tôMàu tôH001, 23G001C01D02F01I01A02B02E03CBADEFGHIBài toán tô màu đồ thị - Ví dụBước 9: Chọn đỉnh GĐỉnhBậcBậc mớiMàu cấm tôMàu tôG0012C01D02F01I01A02B02E03H03CBADEFGHIBài toán tô màu đồ thị - Bài tậpCBADEFGHIBài tậpÁp dụng giải thuật A* cho bài toán Ta-CanhÁp dụng giải thuật tô màu đồ thị cho bài toán xếp lịch, cuộc họp và bố trí đèn tín hiệu giao thôngCài đặt các thuật toán trênQ&A