Báo cáo tài liệu vi phạm
Giới thiệu
Kinh doanh - Marketing
Kinh tế quản lý
Biểu mẫu - Văn bản
Tài chính - Ngân hàng
Công nghệ thông tin
Tiếng anh ngoại ngữ
Kĩ thuật công nghệ
Khoa học tự nhiên
Khoa học xã hội
Văn hóa nghệ thuật
Sức khỏe - Y tế
Văn bản luật
Nông Lâm Ngư
Kỹ năng mềm
Luận văn - Báo cáo
Giải trí - Thư giãn
Tài liệu phổ thông
Văn mẫu
THỊ TRƯỜNG NGÀNH HÀNG
NÔNG NGHIỆP, THỰC PHẨM
Gạo
Rau hoa quả
Nông sản khác
Sữa và sản phẩm
Thịt và sản phẩm
Dầu thực vật
Thủy sản
Thức ăn chăn nuôi, vật tư nông nghiệp
CÔNG NGHIỆP
Dệt may
Dược phẩm, Thiết bị y tế
Máy móc, thiết bị, phụ tùng
Nhựa - Hóa chất
Phân bón
Sản phẩm gỗ, Hàng thủ công mỹ nghệ
Sắt, thép
Ô tô và linh kiện
Xăng dầu
DỊCH VỤ
Logistics
Tài chính-Ngân hàng
NGHIÊN CỨU THỊ TRƯỜNG
Hoa Kỳ
Nhật Bản
Trung Quốc
Hàn Quốc
Châu Âu
ASEAN
BẢN TIN
Bản tin Thị trường hàng ngày
Bản tin Thị trường và dự báo tháng
Bản tin Thị trường giá cả vật tư
Tìm
Danh mục
Kinh doanh - Marketing
Kinh tế quản lý
Biểu mẫu - Văn bản
Tài chính - Ngân hàng
Công nghệ thông tin
Tiếng anh ngoại ngữ
Kĩ thuật công nghệ
Khoa học tự nhiên
Khoa học xã hội
Văn hóa nghệ thuật
Y tế sức khỏe
Văn bản luật
Nông lâm ngư
Kĩ năng mềm
Luận văn - Báo cáo
Giải trí - Thư giãn
Tài liệu phổ thông
Văn mẫu
NGÀNH HÀNG
NÔNG NGHIỆP, THỰC PHẨM
Gạo
Rau hoa quả
Nông sản khác
Sữa và sản phẩm
Thịt và sản phẩm
Dầu thực vật
Thủy sản
Thức ăn chăn nuôi, vật tư nông nghiệp
CÔNG NGHIỆP
Dệt may
Dược phẩm, Thiết bị y tế
Máy móc, thiết bị, phụ tùng
Nhựa - Hóa chất
Phân bón
Sản phẩm gỗ, Hàng thủ công mỹ nghệ
Sắt, thép
Ô tô và linh kiện
Xăng dầu
DỊCH VỤ
Logistics
Tài chính-Ngân hàng
NGHIÊN CỨU THỊ TRƯỜNG
Hoa Kỳ
Nhật Bản
Trung Quốc
Hàn Quốc
Châu Âu
ASEAN
BẢN TIN
Bản tin Thị trường hàng ngày
Bản tin Thị trường và dự báo tháng
Bản tin Thị trường giá cả vật tư
Thông tin
Tài liệu Xanh là gì
Điều khoản sử dụng
Chính sách bảo mật
0
Trang chủ
Khoa Học Tự Nhiên
Toán học
Bài giảng Toán rời rạc: Chương 6.3 - ThS. Trần Quang Khải
Đang chuẩn bị liên kết để tải về tài liệu:
Bài giảng Toán rời rạc: Chương 6.3 - ThS. Trần Quang Khải
Bảo Quỳnh
54
28
pdf
Không đóng trình duyệt đến khi xuất hiện nút TẢI XUỐNG
Tải xuống
Bài giảng Toán rời rạc: Chương 6.3 cung cấp cho người học những kiến thức như: Bài toán tìm đường đi ngắn nhất; Giới thiệu bài toán TSP. Mời các bạn cùng tham khảo! | TOÁN RỜI RẠC Chương 6 Đồ thị Giảng viên ThS. Trần Quang Khải Nội dung phần 3 1. Bài toán tìm đường đi ngắn nhất Giải thuật Dijsktra. 2. Giới thiệu bài toán TSP. Toán rời rạc 2011-2012 Chương 6 Đồ thị 2 Chương 6 Bài toán tìm đường đi ngắn nhất Giảng viên ThS. Trần Quang Khải Toán rời rạc 2011-2012 Đồ thị có trọng số Weighted graph Là đồ thị mà mỗi cạnh được gán một số nguyên hoặc thực với ngụ ý nào đó. Toán rời rạc 2011-2012 Chương 6 Đồ thị 4 Đồ thị có trọng số Liên quan Thời gian. Khoảng cách. Chi phí. Toán rời rạc 2011-2012 Chương 6 Đồ thị 5 Đồ thị có trọng số Độ dài length của đường đi có trọng số Tổng trọng số của các cạnh trên đường đi. Đường đi ngắn nhất đường đi có độ dài nhỏ nhất trong số các đường đi có thể có. Lưu ý Khác với khái niệm độ dài là tổng số cạnh. Toán rời rạc 2011-2012 Chương 6 Đồ thị 6 Bài toán tìm đường đi ngắn nhất Shortest path problems Tìm ra đường đi có độ dài nhỏ nhất giữa 2 đỉnh s source và t destination . Các thuật toán Dijsktra giữa 2 đỉnh không cạnh âm . Floyd-Warshall mọi cặp đỉnh . Bellman-Ford có cạnh âm . Toán rời rạc 2011-2012 Chương 6 Đồ thị 7 Bài toán tìm đường đi ngắn nhất Nhận xét Có thể bỏ bớt các cạnh bội chỉ giữ lại cạnh có trọng số nhỏ nhất. Có thể bỏ đi các khuyên có trọng số không âm. Nếu có khuyên trọng số âm có thể không có lời giải. Toán rời rạc 2011-2012 Chương 6 Đồ thị 8 Bài toán tìm đường đi ngắn nhất Biểu diễn đồ thị dạng ma trận kề aij Trọng số cạnh nhỏ nhất nối i đến j nếu có. 0 nếu không có cạnh nối i đến j nếu có. Phải kiểm tra giá trị 0 trong ma trận. Tổng quát hơn thay 0 bằng . Toán rời rạc 2011-2012 Chương 6 Đồ thị 9 Nguyên lý Bellman Gọi P là đường đi ngắn nhất từ i đến j k là một đỉnh nằm giữa i và j trên P thì Đường đi P1 từ i đến k cũng chính là đường đi ngắn nhất từ i đến k. Đường đi P2 từ k đến j cũng chính là đường đi ngắn nhất từ k đến j. Toán rời rạc 2011-2012 Chương 6 Đồ thị 10 Thuật toán Dijsktra Ý tưởng Giải thuật Dijsktra chủ yếu dựa trên nguyên lý gán nhãn labeling . Tác giả Edsger Dijkstra
TÀI LIỆU LIÊN QUAN
Giáo trình Toán rời rạc - Chương 6 Lý thuyết đồ thị - Cây
Giáo trình Toán rời rạc - Chương 1 Cơ sở Logic
Giáo trình Toán rời rạc - Chương 2 Phép đếm
Giáo trình Toán rời rạc - Chương 3 Quan hệ
Giáo trình Toán rời rạc - Chương 4 Hàm Bool
Giáo trình Toán rời rạc - Chương 5 Đồ thị
Bài giảng Toán rời rạc ứng dụng trong tin học - Chương 2: Các bài toán về đường đi
Bài giảng Toán rời rạc ứng dụng trong tin học - Chương 3: Đồ thị phẳng và bài toán tô màu đồ thị
Bài giảng Toán học rời rạc và cấu trúc rời rạc: Chương 2 - Đại học Khoa Học Tự Nhiên Tp. Hồ Chí Minh
Bài giảng Toán học rời rạc và cấu trúc rời rạc: Chương 3 - Đại học Khoa Học Tự Nhiên Tp. Hồ Chí Minh
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.