Giáo trình giải thuật của Nguyễn Văn Linh part 12

KĨ THUẬT TÌM KIẾM ÐỊA PHƯƠNG 3.6.1 Nội dung kĩ thuật Kĩ thuật tìm kiếm địa phương (local search) 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 như sau: • 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 phương án đã có. • 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 được phương án nữa....
Nội dung trích xuất từ tài liệu:
Giáo trình giải thuật của Nguyễn Văn Linh part 12Giải thuật Kĩ thuật thiết kế giải thuật3.6 KĨ THUẬT TÌM KIẾM ÐỊA PHƯƠNG3.6.1 Nội dung kĩ thuậtKĩ thuật tìm kiếm địa phương (local search) thường được áp dụng để giải các bàitoán tìm lời giải tối ưu. Phương pháp như sau: • 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 phương án đã có. • 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 được phương án nữa.Nguyễn Văn Linh Trang 78 Sưu t m b i: www.daihoc.com.vnGiải thuật Kĩ thuật thiết kế giải thuậtThông thường một phép biến đổi chỉ thay đổi một bộ phận nào đó của phương ánhiện hành để được một phương án mới nên phép biến đổi được gọi là phép biến đổiđịa phương và do đó ta có tên kĩ thuật tìm kiếm địa phương. Sau đây ta sẽ trình bàymột số ví dụ áp dụng kĩ thuật tìm kiếm địa phương.3.6.2 Bài toán cây phủ tối thiểuCho G = (V,E) là một đồ thị vô hướng liên thông, trong đó V là tập các đỉnh và E làtập các cạnh. Các cạnh của đồ thị G đề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ủ (spaning tree) của đồ thị G.Cây phủ tối thiểu là một cây phủ của G mà tổng độ dài (trọng số) các cạnh nhỏ nhất.Bài toán cây phủ tối thiểu thường được áp dụng trong việc thiết kế một mạng lướigiao thông giữa các thành phố hay thiết kế một mạng máy tính.Kĩ thuật tìm kiếm địa phương áp dụng vào bài toán này như sau: • Phương án ban đầu là một cây phủ nào đó. n(n - 1) • Thành lập tập tất cả các cạnh theo thứ tăng dần của độ dài (có 2 cạnh đối với đồ thị có n đỉnh). • Phép biến đổi địa phương ở đây là: Chọn một cạnh có độ dài nhỏ nhất trong tập các cạnh chưa sử dụng để thêm vào cây. Trong cây sẽ có một chu trình, loại khỏi chu trình cạnh có độ dài lớn nhất trong chu trình đó. Ta được một cây phủ mới. Lặp lại bước này cho đến khi không còn cải thiện được phương án nữa.Ví dụ 3-12: Cho đồ thị G bao gồm 5 đỉnh a, b, c, d,e và độ dài các cạnh được chotrong hình 3-15.Tập hợp các cạnh để xét được thành blập theo thứ tự từ nhỏ đến lớn là ad,ab, be, bc, ac, cd, bd, de, ae và ce. 3 4Cây xuất phát với giá là 20 (Hình 3-16). Thêm cạnh ad = 2, bỏ cạnh cd = 45 ta được cây mới có giá là 17 (Hình a c3-17). 3 6Lại thêm cạnh ab = 3, bỏ cạnh bc = 4 7 2 8 5ta được cây có giá là16 (Hình 3-18).Thêm cạnh be = 3, bỏ cạnh ae = 7 tađược cây có giá là 12. (Hình 3-19). e d 6Việc áp dụng các phép biến đổi đếnđây dừng lại vì nếu tiếp tục nữa thì Hình 3-15: Bài toán cây phủ tối thiểucũng không cải thiện được phươngán.Vậy cây phủ tối thiểu cần tìm là cây trong hình 3-19Nguyễn Văn Linh Trang 79 Sưu t m b i: www.daihoc.com.vnGiải thuật Kĩ thuật thiết kế giải thuật b b 4 4 a 4 c a 4 c 7 5 7 2 e d e d Hình 3-16: Cây xuất phát, giá 20 Hình 3-17: Giá 17 b b 3 3 a 4 c a 4 c 7 2 2 3 e d e d Hình 3-18: Giá 16 Hình 3-19: Giá 123.6.3 Bài toán đường đi của người giao hàng.Ta có thể vận dụng kĩ thuật tìm kiếm địa phương để giải bài toán tìm đường đi ngắnnh ...