YOMEDIA
Bài giảng: Thuật giải Heuristic (ThS. Đào Quốc Thắng)
Chia sẻ: Le Van Dai
| Ngày:
| Loại File: PDF
| Số trang:27
324
lượt xem
72
download
Download
Vui lòng tải xuống để xem tài liệu đầy đủ
Chuyên đề bồi dưỡng đội tuyển Olympic Tin học: Thuật giải Heuristic của trường ĐH Ngân hàng Tp. HCM gồm các nội dung chính: Khái niệm “Thuật toán” và “Thuật giải”; Thuật giải Heuristic; Một số ví dụ ứng dụng; Bài tập.
AMBIENT/
Chủ đề:
Nội dung Text: Bài giảng: Thuật giải Heuristic (ThS. Đào Quốc Thắng)
- CHUYÊN ĐỀ BỒI DƯỠNG ĐỘI TUYỂN OLYMPIC TIN HỌC
THUẬT GIẢI HEURISTIC
Giảng viên: ThS. Đào Quốc Thắng
Khoa Công nghệ thông tin
Trường ĐH Ngân hàng Tp HCM
1
- Nội dung
Khái niệm “Thuật toán” và “Thuật giải”
Thuật giải Heuristic
Một số ví dụ ứng dụng
Bài tập
2
- Khái niệm “Thuật toán” và
“Thuật giải”
Quan điểm lập trình cấu trúc
Algorithm + Data structure
= Program
Thuật toán: dãy hữu hạn các bước
không mập mờ và có thể thực hiện
được, quá trình hành động theo các
bước này phải dừng và cho kết quả
như mong muốn.
3
- Các tính chất cơ bản của thuật
toán
Xác định.
Hữu hạn.
Tính đúng.
4
- Hạn chế
Có nhiều bài toán cho tới nay vẫn chưa xây
dựng được thuật toán.
Có bài toán xây dựng được thuật toán song
không thể áp dụng được do không đủ tài
nguyên để cung cấp.
Có thể giải quyết một số bài toán theo những
cách khác, thường cho kết quả tốt và thực
hiện dễ dàng hơn so với thuật toán.
5
- Thuật giải
Các cách giải chấp nhận được nhưng
không hoàn toàn đáp ứng đầy đủ các
tiêu chuẩn của thuật toán.
6
- 2. Thuật giải Heuristic
Là sự mở rộng của thuật toán với các
đặc tính:
Thường cho lời giải tốt (nhưng không chắc
là tốt nhất).
Cho phép giải quyết bài toán một cách
nhanh chóng, dễ dàng.
Thể hiện tự nhiên, gần gũi với suy luận của
con người.
7
- Các nguyên lý cơ sở của thuật
giải Heuristic
Nguyên lý tham lam (nguyên lý
Greedy).
Nguyên lý thứ tự.
Nguyên lý hướng đích (hàm Heuristic).
Nguyên lý vét cạn.
8
- Nguyên lý tham lam
Lấy tiêu chuẩn tối ưu toàn cục (đặt ra
cho bài toán) làm tiêu chuẩn chọn lựa
hành động cục bộ (từng bước/từng giai
đoạn thực hiện).
9
- Nguyên lý hướng đích (Hàm
Heuristic)
Các hàm đánh giá thô, giá trị phụ thuộc
vào trạng thái hiện tại của bài toán tại
một bước giải, cho phép chọn lựa hành
động một cách hợp lý trong từng bước
của thuật giải.
10
- Nguyên lý vét cạn
Bài toán tìm kiếm: cố gắng hạn chế
không gian tìm kiếm hoặc sử dụng một
kiểu dò tìm đặc biệt dựa vào đặc thù
riêng của bài toán để nhanh chóng đi
tới mục tiêu.
11
- 3. Một số ví dụ ứng dụng
Bài toán hành trình ngắn nhất: ứng
dụng nguyên lý Greedy
Bài toán phân việc: ứng dụng nguyên lý
thứ tự
Bài toán tô màu bản đồ: ứng dụng
nguyên lý thứ tự
Bài toán Ta-canh: ứng dụng hàm
Heuristic
12
- Bài toán hành trình ngắn nhất
Một người bán hàng mỗi ngày phải đem
hàng từ công ty đến giao cho các đại lý
trong thành phố, rồi sau đó quay trở lại
vị trí xuất phát (về lại công ty). Giả sử
giữa mỗi cặp điểm (công ty/đại lý) đều
tồn tại một đường đi trực tiếp. Hãy tìm
con đường đi ngắn nhất sao cho mỗi
đại lý chỉ được đi qua đúng 1 lần.
13
- Ví dụ minh họa
1
5 1
7
2
3
2
5
4
2 4
3
4 3
1
14
- Bài toán phân việc
Một công ty nhận hợp đồng gia công n
chi tiết máy J1, J2, …Jn. Công ty có m
máy công cụ P1, P2, …Pm, trong đó
mỗi chi tiết máy đều có thể gia công
trên bất kỳ máy nào, một khi đã gia
công một chi tiết máy thì không thể
ngưng giữa chừng.
15
- Ví dụ
Giả sử thời gian cần thiết để gia công
mỗi chi tiết Ji là Ti, hãy phân công công
việc trên các máy để thời gian thực hiện
hợp đồng là ngắn nhất.
VD 1: m=3, n=5, T1=2, T2=5, T3=8,
T4=1, T5=5.
VD 2: m-2, n=5, T1=3, T3, T4=2,
T5=2.
16
- Bài toán tô màu bản đồ
Cho một bản đồ n vùng, hãy tô màu
các vùng sao cho mỗi cặp 2 vùng lân
cận phải được tô bằng 2 màu riêng biệt
và số màu được sử dụng là ít nhất.
17
- Ví dụ: Tô màu bản đồ
6
8
2
3 5 9
1 7
4
18
- Bài toán Ta-canh (trò chơi 9-
puzzle)
Cho hình vuông kích thước 3x3 với 9 ô
chứa 1 trong 8 con số 1, 2, …, 8 và 1 ô
để trống. Hãy di chuyển ô trống sao
cho các ô số được sắp xếp theo thứ tự
tứ 1 đến 8.
19
- Ví dụ minh họa
3 1 4 1 2 3
7 6 4 5 6
8 2 5 7 8
20
Thêm tài liệu vào bộ sưu tập có sẵn:
Báo xấu
LAVA
ERROR:connection to 10.20.1.98:9315 failed (errno=111, msg=Connection refused)
ERROR:connection to 10.20.1.98:9315 failed (errno=111, msg=Connection refused)
Đang xử lý...
Thêm vào BST
Báo xấu
