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
Giới thiệu
Đăng ký
Đăng nhập
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
Thông tin
Điều khoản sử dụng
Quy định bảo mật
Quy chế hoạt động
Chính sách bản quyền
Giới thiệu
Đăng ký
Đăng nhập
0
Trang chủ
Khoa Học Tự Nhiên
Toán học
Giáo trình lý thuyết đồ thị - Bài 14
Đang chuẩn bị liên kết để tải về tài liệu:
Giáo trình lý thuyết đồ thị - Bài 14
Xuân Hòa
67
1
pdf
Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
Bài toán đường đi ngắn nhất Trước mỗi chuyến xuất hành, chúng ta thường phải suy nghĩ và chọn ra cho mình một hành trình “tiết kiệm” nhất theo nghĩa tốn ít thời gian, tốn ít nhiên liệu hoặc tốn ít tiền nhất Lý thuyết Đồ thị sẽ giúp chúng ta tìm ra giải pháp đó. 8.1. Bài toán Đường đi ngắn nhất | BÀI 14 Chương 8 Bài toán đường đi ngắn nhất Trước mỗi chuyến xuất hành chúng ta thường phải suy nghĩ và chọn ra cho mình một hành trình tiết kiệm nhất theo nghĩa tốn ít thời gian tốn ít nhiên liệu hoặc tốn ít tiền nhất . Lý thuyết Đồ thị sẽ giúp chúng ta tìm ra giải pháp đó. 8.1. Bài toán Đường đi ngắn nhất Bài toán Cho đồ thị G V E và hai đỉnh a b. Tìm đường đi ngắn nhất nếu có đi từ đỉnh a đến đỉnh b trong đồ thị G. ý nghĩa thực tế Bài toán này giúp chúng ta chọn các hành trình tiết kiệm nhất quãng đường thời gian chi phí . trong giao thông lập lịch thi công các công trình một cách tối ưu xử lý trong truyền tin . Thuật toán duyệt đồ thị theo chiều rộng đã cho ta lời giải của bài toán này. Song ta có thêm thuật toán sau đây. Thuật toán 8.1 1. Lần lượt gán nhãn cho các đỉnh của đồ thị mỗi đỉnh không quá một lần như sau - Đỉnh a được gán nhãn là số 0. - Những đỉnh kề với đỉnh a được gán số 1. - Những đỉnh kề với đỉnh đã được gán nhãn số 1 được gán số 2. - Tương tự những đỉnh kề với đỉnh đã được gán số i được gán nhãn là số i 1. Thực hiện cho đến khi gán được nhãn cho đỉnh b hoặc không gán nhãn được nữa. 2. Nếu đỉnh b được gán nhãn nào đó là k thì kết luận có đường đi ngắn nhất từ đỉnh a tới đỉnh b với độ dài k ngược lại thì trả lời là không có. 3. Khôi phục đường đi Nếu ở bước 2. chỉ ra b được gán nhãn k nào đó thì ta đi ngược lại theo quy tắc sau đây Nếu đỉnh y được gán nhãn j với j 1 thì sẽ có đỉnh x được gãn nhãn j-1 sao cho có cạnh đi từ x tới y. Đi ngược lại cho đến khi gặp đỉnh a ta nhận được đường đi ngắn nhất cần tìm. Ví dụ 8.1 Bài toán con sói con dê và cái bắp cải Một con sói một con dê và một cái bắp cải đang ở bờ sông. Người lái đò phải đưa chúng sang sông. Nhưng thuyền quá bé nên mỗi chuyến chỉ chở được một hành khách thôi. Vì những lý do mà ai cũng biết không thể bỏ mặc sói với dê hoặc dê với bắp cải mà không có người trông. Vậy người lái đò phải xử trí thế nào mà vẫn đưa được sói dê và bắp cải sang bên kia sông. Xây dựng đồ thị vô hướng với các đỉnh .
TÀI LIỆU LIÊN QUAN
Giáo trình Lý thuyết đồ thị: Phần 2 - PGS. Nguyễn Cam, PTS. Chu Đức Khánh
Đề thi LÝ THUYẾT ĐỒ HỌA K27 (lần 2)
Quản lý môi trường đô thị và khu công nghiệp
Kiến trúc sư làm gì để biến đổi đô thị?
Bài tập về lý thuyết đồ thị
Lập trình Android cơ bản: Bài 2 Xây dựng giao diện đơn giản
Bài giảng đồ họa : Hiển thị đối tượng hai chiều
Lập trình Android cơ bản: Bài 1 Cơ bản Android
Lập trình Android cơ bản: Bài 6 Android SQLite Database
Lập trình Android cơ bản: Bài 7 Android Content Provider
crossorigin="anonymous">
Đã 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.