BÀI 5
BÀI TOÁN LIỆT KÊ
Nguyễn Văn Hiệu, 2012, Discrete Mathematics 1
Giáo viên: TS. Nguyễn Văn Hiệu
Email: nvhieuqt@dut.udn.vn
5.1. Giới thiệu
Nguyễn Văn Hiệu, 2012, Discrete Mathematics 2
Nội
dung
5.1. Giới thiệu
5.2. Phương pháp sinh
5.3. Phương pháp quay lui
5.1. Giới thiệu
Nguyễn Văn Hiệu, 2012, Discrete Mathematics 3
Mục
đích
Đưa ra danh sách tất cả các cấu hình
có
thể có
Bản
chất
Xác định một thuật toán để theo đó có
thể lần lượt xây dựng được tất cả các
cấu hình đang quan tâm.
5.1. Giới thiệu
Nguyễn Văn Hiệu, 2012, Discrete Mathematics 4
Nguyên
tắc
Không được lặp lại một cấu hình
Không được bỏ sót một cấu hình
Lưu
ý
Chỉ giải với bài toán chưa có phương
pháp giải
Phương pháp Sinh
Phương pháp quay lui
5.2. Phương pháp sinh
Nguyễn Văn Hiệu, 2012, Discrete Mathematics 5
Thường
sử dụng
Giải bài toán liệt kê tổ hợp
Điều
kiện
Xác định được một thứ tự.
Có cấu hình đầu tiên
Có cấu hình cuối cùng
Xác định được thuật toán để xây dựng
cấu hình kế tiếp