KĨ THUẬT THIẾT KẾ GIẢI THUẬT Tổng Quan: Nắm vững các kĩ thuật thiết kế giải thuật: chia để trị, quy hoạch động, tham ăn, quay lui, cắt tỉa alpha-beta, nhánh cận và tìm kiếm địa phương. Với mỗi kĩ thuật cần nắm được: • Nội dung kĩ thuật. • Vận dụng kĩ thuật vào giải các bài toán thực tế. • Đánh giá được giải thuật | Giải thuật Kĩ thuật thiết kế giải thuật CHƯƠNG 3 KĨ THUẬT THIẾT KẾ GIẢI THUẬT TỔNG QUAN Mục tiêu Nắm vững các kĩ thuật thiết kế giải thuật chia để trị quy hoạch động tham ăn quay lui cắt tỉa alpha-beta nhánh cận và tìm kiếm địa phương. Với mỗi kĩ thuật cần nắm được Nội dung kĩ thuật. Vận dụng kĩ thuật vào giải các bài toán thực tế. Đánh giá được giải thuật. Kiến thức cơ bản cần thiết Các cấu trúc dữ liệu đặc biệt là cấu trúc cây và đồ thị. Tài liệu tham khảo . Aho . Hopcroft . Ullman Data Structures and Algorithms Addison-Wesley 1983. Chapter 10 . Jeffrey H Kingston Algorithms and Data Structures Addison-Wesley 1998. Chapter 12 . Đinh Mạnh Tường Cấu trúc dữ liệu Thuật toán Nhà xuất bản khoa học và kĩ thuật Hà nội-2001. Chương 8 . Nguyễn Đức Nghĩa Tô Văn Thành Toán rời rạc 1997 Chương 3 5 . Nội dung cốt lõi Nói chung khi thiết kế một giải thuật chúng ta thường dựa vào một số kĩ thuật nào đó. Chương này sẽ trình bày một số kĩ thuật quan trọng để thiết kế giải thuật như Chia để trị Divide-and-Conquer quy hoạch động dynamic programming kĩ thuật tham ăn greedy techniques quay lui backtracking và tìm kiếm địa phương local search . Các kĩ thuật này được áp dụng vào một lớp rộng các bài toán trong đó có những bài toán cổ điển nổi tiếng như bài toán tìm đường đi ngắn nhất của người giao hàng bài toán cây phủ tối tiểu. KĨ THUẬT CHIA ĐẺ TRỊ Nội dung kĩ thuật Có thể nói rằng kĩ thuật quan trọng nhất được áp dụng rộng rãi nhất để thiết kế các giải thuật có hiệu quả là kĩ thuật chia để trị divide and conquer . Nội dung của nó là Để giải một bài toán kích thước n ta chia bài toán đã cho thành một số bài toán con có kích thưóc nhỏ hơn. Giải các bài toán con này rồi tổng hợp kết quả lại để được lời giải của bài toán ban đầu. Đối với các bài toán con chúng ta lại sử dụng kĩ Nguyễn Văn Linh Trang 45 Sưu tầm bởi Giải thuật Kĩ thuật thiết kế giải thuật thuật chia để trị để có được các bài toán kích thước nhỏ horn nữa. Quá
