tailieunhanh - Bài giảng Toán rời rạc: Một số bài toán tối ưu trên đồ thị - ThS. Hoàng Thị Thanh Hà

Bài giảng Toán rời rạc - Một số bài toán tối ưu trên đồ thị được biên soạn gồm các nội dung chính sau: Một số bài toán trên đồ thị; Thuật toán dijkstra; Thuật toán floyd tìm khoảng cách của các cặp đỉnh. Mời các bạn cùng tham khảo! | Nội dung 1. MỘT SỐ BÀI TOÁN TRÊN ĐỒ THỊ Toán rời rạc 5 2. THUẬT TOÁN DIJKSTRA MỘT SỐ BÀI TOÁN TỐI ƯU 3. THUẬT TOÁN FLOYD TÌM KHOẢNG TRÊN ĐỒ THỊ CÁCH CỦA CÁC CẶP ĐỈNH Ts. Hoàng Thị Thanh Hà Khoa Thống kê Tin học Trường Đại học Kinh tế 30 October 2012 1 30 October 2012 2 MỘT SỐ BÀI TOÁN TRÊN ĐỒ THỊ MỘT SỐ BÀI TOÁN TRÊN ĐỒ THỊ Mở đầu Có thể coi sơ đồ của đường đi từ A đến B trong Trong đời sống chúng ta thường gặp những thành phố là một đồ thị với đỉnh là các giao lộ tình huống như sau để đi từ địa điểm A đến địa A và B coi như giao lộ cạnh là đoạn đường điểm B trong thành phố có nhiều đường đi nối hai giao lộ. Trên mỗi cạnh của đồ thị này ta nhiều cách đi có lúc ta chọn đường đi ngắn gán một số dương ứng với chiều dài của đoạn nhất theo nghĩa cự ly có lúc lại cần chọn đường thời gian đi đoạn đường hoặc cước phí đường đi nhanh nhất theo nghĩa thời gian và vận chuyển trên đoạn đường đó . có lúc phải cân nhắc để chọn đường đi chi phí thấp nhất . 30 October 2012 3 30 October 2012 4 MỘT SỐ BÀI TOÁN TRÊN ĐỒ THỊ THUẬT TOÁN DIJKSTRA a ĐN Đồ thị có trọng số là đồ thị G V E mà mỗi cạnh Cho đơn đồ thị liên thông có trọng số G V E . Tìm e E được gán bởi một số thực m e gọi là trọng số của khoảng cách d u0 v từ một đỉnh u0 cho trước đến một cạnh hoặc cung e đỉnh v bất kỳ của G và tìm đường đi ngắn nhất từ u0 đến v. Ở đây trọng số của mỗi cạnh được xét là một số dương và còn gọi là chiều dài của cạnh đó. Có một số thuật toán tìm đường đi ngắn nhất ở đây ta có Mỗi đường đi từ đỉnh u đến đỉnh v có chiều dài là m u v bằng thuật toán do E. Dijkstra nhà toán học người Hà Lan đề tổng chiều dài các cạnh mà nó đi qua. Khoảng cách d u v giữa xuất năm 1959. Trong phiên bản mà ta sẽ trình bày người hai đỉnh u và v là chiều dài đường đi ngắn nhất trong các đường ta giả sử đồ thị là vô hướng các trọng số là dương. Chỉ đi từ u đến v. cần thay đổi đôi chút là có thể giải được bài toán tìm Có thể xem một đồ thị G bất kỳ là một đồ thị có trọng số đường đi ngắn nhất trong đồ thị có hướng. mà .

• Toán học
• Bài giảng Toán rời rạc
• Toán rời rạc
• Bài toán tối ưu trên đồ thị
• Thuật toán dijkstra
• Thuật toán floyd
• Ma trận khoảng cách
• Giáo trình toán rời rạc
• Tài liệu toán rời rạc
• Học toán rời rạc
• Lý thuyết về toán rời rạc
• Câu hỏi Toán rời rạc
• Bài tập Toán rời rạc
• Hệ thức truy hồi
• Quan hệ chia để trị Toán rời rạc
• Nguyên lý toán rời rạc
• Cấu hình tổ hợp
• Cấu hình toán rời rạc
• Bài giảng môn học Toán học rời rạc
• Toán học rời rạc
• Môn Toán học rời rạc
• Tập hợp và logic mệnh đề
• lý thuyết toán rời rạc
• đề cương Toán rời rạc