Bài giảng Thiết kế và đánh giá thuật toán: Tham ăn - TS. Lê Nguyên Khôi

Thiết Kế & Đánh Giá Thuật Toán<br /> Tham Ăn<br /> TS. Lê Nguyên Khôi<br /> Trường Đại Học Công Nghệ - ĐHQGHN<br /> <br /> Nội Dung<br />
<br /> <br /> Bài toán<br /> Trả tiền thừa<br />
Ba lô<br />
<br /> <br /> Chiến lược tham ăn<br />
Cây bao trùm nhỏ nhất<br />
<br /> <br /> Thuật toán Prim<br />
Thuật toán Kruskal<br />
<br /> <br /> 1<br /> <br /> Bài Toán Trả Tiền Thừa<br /> Các loại đồng xu 100c, 25c, 10c, 5c, 1c<br />
Với khoản tiền cần trả lại, sao cho số<br /> lượng đồng xu là ít nhất.<br />
Ví dụ: trả lại 189c<br />
<br /> <br /> 189 xu 1c => 189<br />
18 xu 10c, 1 xu 5c, 4 xu 1c => 23<br />
<br /> <br /> 2<br /> <br /> Bài Toán Trả Tiền Thừa<br /> Số lượng đồng xu trả lại là ít nhất?<br />
Ý tưởng:<br />
<br /> <br /> Sử dụng lần lượt các đồng xu có mệnh giá từ<br /> lớn nhất đến nhỏ nhất<br />
Hy vọng số lượng đồng xu là ít nhất<br />
<br /> <br />
<br /> <br /> Ví dụ: trả lại 189c<br /> 1 xu 100c, 3 xu 25c, 1 xu 10c, 4 xu 1c => 9<br />
9 xu đã ít nhất chưa<br />
<br /> <br /> 3<br /> <br /> Lập Trình Động – Nhắc Lại<br /> Thường áp dụng cho bài toán tối ưu<br />
Xác định được lời giải tối ưu<br />
<br /> <br />
<br /> <br /> Dựa trên lời giải tối ưu các bài toán con<br /> <br /> Có thể phức tạp hóa vấn đề<br />
Không khả thi với bài toán thực tế<br />
<br /> <br /> Không gian tìm kiếm rộng<br />
Thời gian tìm kiếm lâu<br />
<br /> <br /> 4<br /> <br />