zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Công Nghệ Thông Tin

» Kỹ thuật lập trình

Bài giảng Phân tích và thiết kế thuật toán: Tìm kiếm cục bộ (Local search) - Phạm Thế Bảo

Chia sẻ: Năm Tháng Tĩnh Lặng | Ngày: | Loại File: PDF | Số trang:4

Báo xấu

399
lượt xem 27
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Trong phân tích và thiết kế thuật toán, phương pháp tìm kiếm cục bộ thường được áp dụng để giải các bài toán tìm lời giải tối ưu. Trong bài giảng này chúng ta sẽ cùng áp dụng tìm kiếm cục bộ để giải 2 bài toán, đó là bài toán cây phủ tối thiểu và bài toán người giao hàng. Mời các bạn cùng tham khảo.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Phân tích và thiết kế thuật toán: Tìm kiếm cục bộ (Local search) - Phạm Thế Bảo

14/04/2008 TÌM KIẾM CỤC Ụ BỘ Ộ (ĐNA PHƯƠNG) (LOCAL SEARCH) Phạm Thế Bảo Khoa Toán – Tin học Trường Đại học Khoa học Tự nhiên Tp.HCM Nội dung • Thường được áp dụng để giải các bài toán tìm lời giải tối ưu. • Phương pháp: – Xuất phát từ một phương án nào đó. – Áp dụng một phép biến đổi lên phương án hiện hành để được một phương án mới tốt hơn. – Lặp lại việc áp dụng phép biến đổi lên phương án hiện hành cho đến khi không còn có thể cải thiện phương án được nữa. • Thông thường một phép biến đổi chỉ thay đổi một bộ phận nào đó của phương án hiện hành để được một phương án mới, nên gọi là phép biến đổi địa phương Æ kỹ thuật tìm kiếm địa phương. Phạm Thế Bảo 1
14/04/2008 Bài toán cây phủ tối thiểu • Cho G=(E,V) là một đồ thị vô hướng liên thông, V={đỉnh} V {đỉnh} và EE={cạnh}, {cạnh}, các cạnh đều có trọng số. Cây T có tập hợp các nút là V được gọi là cây phủ (spanning tree) của đồ thị G. • Cây phủ tối thiểu, chính là một cây phủ của G mà tổng độ dài (trọng số) các cạnh là bé nhất. • Ứng dụng: – Thiết kế mạng lưới giao thông. thông – Mạng máy tính. – Đường dây điện. – … Phạm Thế Bảo • Ví dụ: cho đồ thị có 5 đỉnh, và độ dài như hình. Các cạnh được sắp thứ tự: ad, ab, be, bc, ac, cd, bd, de, ae ,ce. b Cây xuất phát với giá trị là 20 a 3 4 4 Thêm cạnh ad=2 (nhỏ nhất), 3 6 c bỏ cạnh cd=5 Æ ta có cây 7 2 8 5 mới có giá trị. b Tổng giá trị bằng 20 e 6 4 d a 4 Đồ thị G c b 4 7 a 4 5 c 7 2 e d Tổng giá trị bằng e Phạm Thế Bảo d 2
14/04/2008 • Lại thêm cạnh ab=3, 3 b Tổng giá trị bằng 16 bỏ cạnh bc=4 Æ cây a 4 c mới giá trị bằng 16. 7 2 • Thêm cạnh be=3, bỏ cạnhh ae=77 Æ cây â e mới có giá trị. d • Áp dụng tiếp tục sẽ không cải thiện Æ 3 b Tổng giá trị bằng dừng. g a 4 c 3 Cây tối 2 thiểu e d Phạm Thế Bảo Bài toán người giao hàng • Phương pháp: – Xuất ấ phát từ một chu trình nào đó. – Bỏ đi hai cạnh có độ dài lớn nhất không kề nhau. Nối các đỉnh còn lại với nhau sao cho vẫn tạo ra một chu trình đủ. – Tiếp tục quá trình biến đổi trên cho đến khi nào không cải thiện được nữa thì dừng. Phạm Thế Bảo 3
14/04/2008 • Ví dụ: Xét bài toán TSP có 5 đỉnh như hình vẽ. Xét một phương án ban b đầu: chu trình (a b c d e 3 4 a 4 a) có giá trị là 25. 25 c 3 6 b 3 7 4 a 2 8 5 c 7 e 6 5 d Đồ thị G e 6 d Phương án ban đầu Phạm Thế Bảo • Bỏ hai cạnh lớn nhất 3 b 4 không kề nhau là ae và a c cd. Nối a với d và e với c Æ chu trình mới 2 8 (a b c e d a), giá trị là 23 23. d 6 • Bỏ tiếp ce và ab. Nối a e Phương án thứ hai với c và b với e Æ chu c trình mới (a c b e d a), 3 4 giá trị là 19. a b • Tiếp ế tục Æ giá trị tăng 2 Æ dừng 3 Kết quả d 6 e Phạm Thế Bảo Phương án thứ ba 4

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.