tailieunhanh - Programming HandBook part 157

Tham khảo tài liệu 'programming handbook part 157', công nghệ thông tin, kỹ thuật lập trình phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | Rõ ràng phương án L vừa thực hiện cũng chính là phương án tối ưu của trường hợp này vì thời gian hoàn thành là 8 đúng bằng thời gian của công việc J3. Ta hy vọng rằng một giải Heuristic đơn giản như vậy sẽ là một thuật giải tối ưu. Nhưng tiếc thay ta dễ dàng đưa ra được một trường hợp mà thuật giải Heuristic không đưa ra được kết quả tối ưu. tì 3 t5 2 tí 2 Md M2 2 3 u 2 11 3 2 3 Mi M2 2 2 4 2 15 2 Nếu gọi T là thời gian để gia công xong n chi tiết máy do thuật giải Heuristic đưa ra và T0 là thời gian tối ưu thì người ta đã chứng minh được rằng T _ 3 M M là số máy Với kết quả này ta có thể xác lập được sai số mà chúng ta phải gánh chịu nếu dùng Heuristic thay vì tìm một lời giải tối ưu. Chẳng hạn với số máy là 2 M 2 ta có 2 Ẩ . . . T0 6 và đó chính là sai số cực đại mà trường hợp ở trên đã gánh chịu. Theo công thức này số máy càng lớn thì sai số càng lớn. Trong trường hợp M lớn thì tỷ số 1 M xem như bằng 0 . Như vậy sai số tối đa mà ta phải chịu là T 4 3 T0 nghĩa là sai số tối đa là 33 . Tuy nhiên khó tìm ra được những trường hợp mà sai số đúng bằng giá trị cực đại dù trong trường hợp xấu nhất. Thuật giải Heuristic trong trường hợp này rõ ràng đã cho chúng ta những lời giải tương đối tốt. III. CÁC PHƯƠNG PHÁP TÌM KIẾM HEURISTIC Qua các phần trước chúng ta tìm hiểu tổng quan về ý tưởng của thuật giải Heuristic nguyên lý Greedy và sắp thứ tự . Trong mục này chúng ta sẽ đi sâu vào tìm hiểu một số kỹ thuật tìm kiếm Heuristic - một lớp bài toán rất quan trọng và có nhiều ứng dụng trong thực tế. . Cấu trúc chung của bài toán tìm kiếm Để tiện lợi cho việc trình bày ta hãy dành chút thời gian để làm rõ hơn đối tượng quan tâm của chúng ta trong mục này. Một cách chung nhất nhiều vấn đề-bài toán phức tạp đều có dạng tìm đường đi trong đồ thị hay nói một cách hình thức hơn là xuấtphát từ một đỉnh của một đồ thị tìm đường đi hiệu quả nhất đến một đỉnh nào đó . Một phát biểu khác thường gặp của dạng bài toán này là Cho trước hai trạng thái To và TG hãy xây dựng chuỗi trạng