Phân tích thiết kế thuật giải

PHÂN TÍCH THIẾT KẾ THUẬT GIẢI GIỚI THIỆU TS. NGÔ QUỐC VIỆT 2014 Giới thiệu chung • Giải thuật/thuật toán là một thủ tục, bao gồm một số bước hữu hạn để giải quyết vấn đề • “Algorithm” bắt nguồn từ tên nhà toán học Al−Khowarizmi 2 Giới thiệu Các thuật toán có một số tính chất chung: • Đầu vào: có các giá trị đầu vào xác định. • Đầu ra: từ tập các giá trị đầu vào, thuât toán sẽ tạo các giá trị đầu ra, xem là nghiệm của bài toán. • Tính xác định: các bước của thuật toán phải được xác định một cách chính xác. • Tính hữu hạn: một thuật toán chứa một số hữu hạn các bước (có thể rất lớn) với mọi tập đầu vào. • Tính hiệu quả: mỗi bước phải thực hiện chính xác, trong khoảng thời gian hữu hạn. • Tính tổng quát: thuật toán phải áp dụng được cho một họ các vấn đề. 3 Giới thiệu • Thuật giải biểu diễn bởi lưu đồ hoặc trình tự các bước • Các tiêu chí đánh giá: • Đơn giản, dễ hiểu, cài đặt. • Thời gian thực hiện và tài nguyên cần. • Tuy nhiên và cũng là nghịch lý là thuật giải càng hiệu quả thì càng có vẻ khó hiểu  tiêu chí chung dựa trên độ phức tạp (algorithm complexity) của thuật giải. 4 Giới thiệu • Giải quyết vấn đề từ cách đơn giản nhất như vét cạn. • Các phương pháp thông minh hơn, hay dựa trên toán học: xác suất, xấp xỉ. • Đến những phương pháp khác: Heuristic, mạng neural, trí tuệ nhân tạo, thuật giải genetic, v.v. 5 Giới thiệu • Độ phức tạp gồm nhiều mức độ: xấu nhất, trung bình, tốt nhất. • Không sử dụng tốt nhất để so sánh. • Thuật giải được xem là hiệu quả nếu nó có độ phức tạp là hàm đa thức theo kích thước dữ liệu đầu vào. • Thực tế, không thể gọi độ phức tạp 6x1023xN20 là hiệu quả. 6 Các chiến lược thiết kế thuật giải • Vét cạn (brute force): thử tất cả mọi khả năng để tìm ra KQ. Đơn giản, không hiệu quả. • Quay lui, thử và sai (back tracking, try and error): lưu giữ trạng thái của các bước trên đường tìm lời giải. Nếu gặp trở ngại, quay lại bước trước và rẽ sang hướng khác. Thường áp dụng khi nghiệm là tìm một tổ hợp (ví dụ tìm đường đi). 7 Các chiến lược thiết kế thuật giải • Thủ tục đệ quy cho bài toán quay lui: gọi lại chính nó với tổ hợp lời giải ở bước trước (vd: bài toán 8 con hậu). • Chia để trị (divide and conquer): chia bài toán lớn thành các bài toán nhỏ hơn (vd: mergesort, quicksort). • Thuật giải tham lam (greedy): chọn lời giải của mỗi bước là tối ưu cục bộ tốt nhất.  Chọn hàm tối ưu cục bộ. Nghiệm chỉ gần đúng với lời giải tối ưu. 8 Các chiến lược thiết kế thuật giải • Quy hoạch động (dynamic programming): cũng thuộc dạng chia để trị nhưng theo cách bottom- up. • Xác suất: sử dụng lý thuyết sắp xếp để tìm lời giải. Chọn lời giải ngẫu nhiên. • Thuật giải di truyền: mô phỏng quá trình tiến hoá theo đó thế hệ sau sẽ tốt hơn sẽ tốt hơn thế hệ trước. 9 Bài tập 1. Cho ma trận MxN (bao gồm số âm và dương). Viết CT tìm ma trận con sao cho tổng các giá trị các phần tử trong ma trận con đó là lớn nhất. 10