PhÇn III Một số ứng dụng của đồ thị
B. Các bài toán tối u
1 . Bài toán ng ời du lịch
Một ngời du lịch muốn đi tham quan n thành phố A1, A2,...An. Xuất phát từ một thành phố nào đó, ngời du lịch muốn đi đến tất cả các thành phố còn lại, mỗi thành phố một lần rồi quay về thành phố xuất phát. Biết rằng ai j là chi phí từ thành phố A1 đến thành phố Aj (i,j=1,2,...n). Hãy tìm một hành trình thỏa mãn yêu cầu nêu ra với tổng chi phí ít nhất.
Rõ ràng là ta có thể thiết lập một tơng ứng 1-1 giữa hành trình Aơ(1) ∏ Aơ(2) ∏ ... ∏Aơ(n) ∏ Aơ(1)
Với một hoán vị ơ =(ơ(1),....,ơ(n)) của n số tự nhiên 1,2,...n. Khi đặt f(ơ)= aơ(1)ơ(2)+...+aơ(n-1)ơ(n)+aơ(n)ơ(1)
và gọi ∑ là tập tất cả các hoán vị ơ=(ơ(1),....,ơ(n)) của n số tự nhiên 1,2,...,n, ta có thể phát biểu lại bài toán dới mô hình tối u sau
min{f(ơ):ơ∈∑}.
Dựa trên phép tính hoán vị, ta có thể thấy rằng tổng số hành trình của ngời du lịch là n!, nhng vì trên thực tế có thể lấy một thành phố cố định nào
đó làm nơi xuất phát, nên chỉ có (n-1)! hành trình thực sự khác nhau.
2 Bài toán thay thế thiết bị:
Máy móc, thiết bị sử dụng lâu ngày tất nhiên sẽ h hỏng dần. Để thiết bị hoạt động đợc liên tục, nhà máy cần phải tiến hành sửa chữa thờng xuyên (bảo dỡng) hoặc nếu cần thì mua mới để thay thế. Vấn đề đặt ra là khi nào cần thay thế thiết bị?
Xây dựng giải thuật: Giả sử, xét một kỳ kế hoạch là 5 năm. vào đầu kỳ, nhà máy mua thiết bị mới và sẽ thay thế nó sau t năm. Cần xác định t bằng bao nhiêu sao cho tổng chi phí bảo dỡng và mua mới trong cả kỳ kế hoạch là nhá nhÊt?
Bài toán thiết bị nêu trên có thể diễn đạt dới dạng bài toán tìm đờng đi ngắn nhất trên mạng. Cách làm nh sau:
+) Xây dựng mạng gồm 6 đỉnh (số năm của kỳ kế hoạch + 1).Các đỉnh từ 1- 5 biểu diễn thời điểm đầu của mỗi năm, đỉnh 6 biểu diễn thời gian kết thúc kỳ hạn kế hoạch. Mỗi đỉnh đợc nối với tất cả mọi đỉnh còn lại, trên mỗi cạnh đó biểu diễn chi phí (giá mua mới + chi phí bảo dỡng). Từ đó, ta tìm đ- ợc cần phải thay thế, bảo dỡng dựa theo những năm nào thì phù hợp với yêu càu đặ ra cho bài toán.
3 Bài toán giao thông:
Cho một mạng giao thông của thành phố, đối với một loại phơng tiện giao thông (ví dụ: xe đạp và xe máy, ôtô con, ôtô tải....) có những con đờng có thể
đi cả hai chiều, một số ít đờng phố chỉ đi đợc một chiều, có đờng phố cấm một loại xe nào đó trong những giờ nhất định. Bài toán đặt ra là cần tìm đ- ờng đi ngắn nhất từ một điểm A bất kỳ đến một điểm Z bất kỳ trong thành phố bằng loại phơng tiện đang có.
Đối với thành phố rộng nh thành phố Hồ Chí Minh, có hàng ngàn nút giao thông thì việc giải bài toán trên không phải là rễ dàng. Bài toán này rất có ý nghĩa đối với nghành du lịch, thơng mại. Bài toán này cũng có thể dùng mạng giao thông của cả một vùng rộng lớn.
4. Bài toán truyền thông tin:
Giả sử ta cần tuyền thông tin trong một mạng lới truyền tin. Qua mỗi đ- ờng truyền tin đều có hiện tợng nhiễu(độ dài của cung biểu thị độ nhiễu). Bài toán đặt ra là cần tìm đờng truyền tin từ A bất kỳ tới điểm Z bất kỳ trong mạng sao cho thông tin ít bị nhiễu nhất, thông tin nhận đợc chính xác nhất.
Để giải quyết bài toán trên chúng ta cũng phải sử dụng bài toán tìm đờng
đi ngắn nhất.
Ngoài những bài toán trên, trong thực tế còn rất nhiều vấn đề mà ta chỉ áp dụng bài toán tìm đờng đi ngắn nhất để giải quyết chúng.
KÕt luËn
Lí thuyết đồ thị là một lĩnh vực nghiên cứu đã có từ lâu, và có nhiều ứng dụng hiện đại. Nó đợc sử dụng để giải quyết các bài toán trong lí thuyết đồ thị, gải quyết các bài toán thực tế phục cụ cho lợi ích của con ngời. Nó đã
đóng góp một vai trò rất quan trọng trong đời sống con ngời.
ở bài khoá luận này em đã tìm hiểu và khai thác đợc một phần của lí thuyết đồ thị và đã giải quyết đợc 2 bài toán cụ thể để minh hoạ:
+ Bài toán tìm đờng đi ngắn nhất trên đồ thị không trọng số.
+ Bài toán tìm đờng đi ngắn nhất trên đồ thị không trọng số.
Cụ thể em đã dùng 2 thuật toán để minh hoạ chúng. Đó là, Thuật toán tìm theo chiều rộng và thuật toán Dijkstra.
Hớng phát triển của khoá luận này là việc xây dựng chơng trình để giải những bài toán cụ thể mang tính thực tế nh các bài toán ứng dụng của đồ thị và các bài toán ứng dụng bài toán tìm đờng đi ngắn nhất...
Vì thời gian có hạn nên trong khoá luận này không thể tránh khỏi những thiếu sót. Vậy em mong đợc sự thông cảm và giúp đỡ của thầy cô cùng bạn bè sinh viên giúp em hoàn thiện khoá luận này.
Một lần nữa em xin đợc bày tỏ lòng biết ơn đến cô Hồ Thị Huyền Thơng cùng toàn thể thầy cô trong khoa CNTT và bạn bè sinh viên đã giúp em hoàn thành khoá luận này. Em xin chân thành cảm ơn!
Vinh, Ngày 15 Tháng 5 Năm 2005