Thuật toán nâng cao
GVHD:Nguyễn Bá Tường
Học viên: Nhóm 3
GIẢI THUẬT HEURISTIC &
ỨNG DỤNG GIẢI THUẬT HEURISTIC
TRONG BÀI TOÁN NGƯỜI ĐƯA THƯ
Nội dung Tiểu luận
Ứng dụng bài toán người đưa thư2
Hỏi đáp3
Nội dung thuật giải Heuristic
Giới thiệu thuật giải Heuristic
Thể hiện khá tự
nhiên, gần gũi với
cách suy nghĩ và
hành động của
con người
Thuật giải Heuristic là một sự
mở rộng khái niệm thuật toán
Thường tìm
được lời giải tốt
Giải bài toán theo thuật giải
Heuristic thường dễ dàng và
nhanh chóng đưa ra kết quả hơn
so với giải thuật tối ưu, vì vậy
chi phí thấp hơn
Nội dung thuật giải Heuristic
Hàm Heuristic
Đó là các hàm đánh giá thô - một ước lượng
về khả năng dẫn đến lời giải tính từ trạng thái
hiện tại (khoảng cách giữa trạng thái hiện tại
và trạng thái đích)

Item 2
Item 5
Item 3
Item 4
Tìm kiếm chiều sâu
Tìm kiếm leo đồi
Tìm kiếm ưu tiên tối ưu
Các phương pháp
tìm kiếm Heuristic

Cấu trúc chung của bài toán tìm kiếm
Nhiều vấn đề-bài toán phức tạp đều có
dạng "tìm đường đi trong đồ thị"
Xuất phá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 đó
Đa số các bài đều có thể được biểu
diễn dưới dạng đồ thị
Vấn đề
chung
Một trạng thái là một đỉnh của đồ thị
Các phương pháp
tìm kiếm Heuristic

Tìm kiếm chiều sâu(DFS)
Là thuật toán duyệt hoặc tìm kiếm trên một cây
hoặc đồ thị. Thuật toán khởi đầu tại gốc
và phát triển xa nhất có thể theo mỗi nhánh
Tìm kiếm chiều sâu bắt đầu từ đỉnh xuất phát, đi
theo cạnh trái, tiếp tục tìm kiếm xong ở cây con

Định nghĩa
Leo đồi đứng
dốc
Tìm kiếm leo đồi, thực chất
chỉ là trường hợp đặc biệt
của tìm kiếm theo chiều sâu
nhưng không thể quay lui.
Là leo đồi nhưng sẽ duyệt
tất cả các hướng đi có thể
và chọn đi theo trạng thái
tốt nhất trong số các trạng
thái kế tiếp có thể có
Nếu trạng thái bắt đầu
cũng là trạng thái đích thì
báo là đã tìm được lời
giải. Ngược lại, đặt trạng
thái hiện hành (T
i
) là
trạng thái khởi đầu
Tư tưởng
Lặp lại cho đến khi đạt
đến trạng thái kết thúc
hoặc cho đến khi không
tồn tại một trạng thái tiếp
theo hợp lệ (Tk) của
trạng thái hiện hành
Các phương pháp
tìm kiếm Heuristic


4
Chương trình Demo
ỨNG DỤNG BÀI TOÁN NGƯỜI ĐƯA THƯ

Phát biểu bài toán
Mục đích bài toán :
Để tiết kiệm thời gian đi đưa thư trong một địa phương.
Người đưa thư phải đi qua tất cả các điểm cần phát thư rồi trở về
vị trí ban đầu với đường đi ngắn nhất.
Bài toán có thể phát biểu lại như sau: Giả sử có một đồ thị có
trọng số dương, tìm đường đi ngắn nhất qua tất cả các đỉnh của
đồ thị rồi trở về đỉnh ban đầu.
ỨNG DỤNG BÀI TOÁN NGƯỜI ĐƯA THƯ

Hạn chế khi sử dụng thuật toán tối ưu
Đồ thị có n đỉnh, khi đó thuật toán tối ưu cho bài toán này sẽ là
thuật toán tìm đường đi ngắn nhất cho chu trình Haminton. Do
đó thuật toán tối ưu sẽ có độ phức tạp là O( n!) và không thể
thực hiện thuật toán.
Vì vậy sẽ sử dụng thuật giải Heuristic cho bài toán này.
ỨNG DỤNG BÀI TOÁN NGƯỜI ĐƯA THƯ

Cài đặt thuật toán
Thử
việc &
đào tạo
Chương trình được viết trên môi trường
Visual C++ 6.0
Công cụ lập trình
Input