tailieunhanh - MỘT SỐ BÀI TOÁN TỐI ƯU TRÊN ĐỒ THỊ PHẦN 3

Giới thiệu bài toán: Một người xuất phát từ một thành phố nào đó muốn tới thăm n 1 thành phố khác, mỗi thành phố đúng một lần, rồi quay về thành phố ban đầu. Hỏi nên đi theo trình tự nào để độ dài tổng cộng các đoạn đường đi qua là ngắn nhất (khoảng cách giữa hai thành phố có thể hiểu là cự ly thông thường hoặc thời gian cần đi hoặc chi phí của hành trình, . và xem như cho trước). Xét đồ thị đầy đủ G=(V,E), với V={1, 2, ., n}, có trọng số với. | MỘT SỐ BÀI TOÁN TỐI ƯU TRÊN ĐÒ THỊ - PHẦN 3 BÀI TOÁN DU LỊCH. . Giới thiệu bài toán Một người xuất phát từ một thành phố nào đó muốn tới thăm n-1 thành phố khác mỗi thành phố đúng một lần rồi quay về thành phố ban đầu. Hỏi nên đi theo trình tự nào để độ dài tổng cộng các đoạn đường đi qua là ngắn nhất khoảng cách giữa hai thành phố có thể hiểu là cự ly thông thường hoặc thời gian cần đi hoặc chi phí của hành trình . và xem như cho trước . Xét đồ thị đầy đủ G V E với V 1 2 . n có trọng số với trọng số mij m i j có thể khác mji m j i . Như vậy ta có thể xem G như là một đồ thị có hướng đầy đủ mạnh theo nghĩa với mọi i j 1 2 . n iyj luôn có i j j i eE. Bài toán trở thành tìm chu trình Hamilton có độ dài ngắn nhất trong G. Bài toán nổi tiếng này đã có lời giải bằng cách sử dụng phương pháp nhánh và cận . . Phương pháp nhánh và cận Giả sử trong một tập hữu hạn các phương án của bài toán ta phải chọn ra được một phương án tối ưu theo một tiêu chuẩn nào đó thí dụ làm cho hàm mục tiêu đạt giá trị nhỏ nhất . Ta sẽ tìm cách phân chia tập phương án đang xét thành hai tập con không giao nhau. Với mỗi tập này ta sẽ tính cận dưới chặn dưới đủ tốt của các giá trị hàm mục tiêu ứng với các phương án trong đó. Mang so sánh hai cận dưới vừa tính được ta có thể phán đoán xem tập con nào có nhiều triển vọng chứa phương án tối ưu và tiếp tục phân chia tập con đó thành hai tập con khác không giao nhau lại tính các cận dưới tương ứng . Lặp lại quá trình này thì sau một số hữu hạn bước cuối cùng sẽ được một phương án tốt nói chung là tối ưu. Nếu không thì lặp lại quá trình phân chia để kiểm tra và sau một vài bước ta sẽ được phương án tối ưu. Người ta thường mô tả quá trình phân chia đó bằng một cây có gốc mà gốc sẽ tượng trưng cho tập toàn bộ các phương án còn các đỉnh ở phía dưới lần lượt tượng trưng cho các tập con trong quá trình phân nhánh nhị phân . Vì vậy phương pháp này mang tên nhánh và cận. . Cơ sở lý luận của phép toán Nếu không xác định thành phố xuất phát thì có