TAILIEUCHUNG - Giáo trình toán rời rạc - Chương 5: MỘT SỐ BÀI TOÁN TỐI ƯU TRÊN ĐỒ THỊ

Trong đời sống, chúng ta thường gặp những tình huống như sau: để đi từ địa điểm A đến địa điểm B trong thành phố, có nhiều đường đi, nhiều cách đi; có lúc ta chọn đường đi ngắn nhất (theo nghĩa cự ly), có lúc lại cần chọn đường đi nhanh nhất (theo nghĩa thời gian) và có lúc phải cân nhắc để chọn đường đi rẻ tiền nhất (theo nghĩa chi phí), . | CHƯƠNG V MỘT SỐ BÀI TOÁN TỐI ƯU TRÊN ĐỒ THỊ . ĐỒ THỊ CÓ TRỌNG SỐ VÀ BÀI TOÁN ĐƯỜNG ĐI NGẮN NHẤT. . Mở đầu Trong đời sống chúng ta thường gặp những tình huống như sau để đi từ địa điểm A đến địa điểm B trong thành phố có nhiều đường đi nhiều cách đi có lúc ta chọn đường đi ngắn nhất theo nghĩa cự ly có lúc lại cần chọn đường đi nhanh nhất theo nghĩa thời gian và có lúc phải cân nhắc để chọn đường đi rẻ tiền nhất theo nghĩa chi phí . Có thể coi sơ đồ của đường đi từ A đến B trong thành phố là một đồ thị với đỉnh là các giao lộ A và B coi như giao lộ cạnh là đoạn đường nối hai giao lộ. Trên mỗi cạnh của đồ thị này ta gán một số dương ứng với chiều dài của đoạn đường thời gian đi đoạn đường hoặc cước phí vận chuyển trên đoạn đường đó . Đồ thị có trọng số là đồ thị G V E mà mỗi cạnh hoặc cung eeE được gán bởi một số thực m e gọi là trọng số của cạnh hoặc cung e. Trong phần nà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 đó. Mỗi đường đi từ đỉnh u đến đỉnh v có chiều dài là m u v bằng tổng chiều dài các cạnh mà nó đi qua. Khoảng cách d u v giữa hai đỉnh u và v là chiều dài đường đi ngắn nhất theo nghĩa m u v nhỏ nhất trong các đường đi từ u đến v. Có thể xem một đồ thị G bất kỳ là một đồ thị có trọng số mà mọi cạnh đều có chiều dài 1. Khi đó khoảng cách d u v giữa hai đỉnh u và v là chiều dài của đường đi từ u đến v ngắn nhất tức là đường đi qua ít cạnh nhất. . Bài toán tìm đường đi ngắn nhất Cho đơn đồ thị liên thông có trọng số G V E . Tìm khoảng cách d u0 v từ một đỉnh u0 cho trước đến một đỉnh v bất kỳ của G và tìm đường đi ngắn nhất từ u0 đến v. Có một số thuật toán tìm đường đi ngắn nhất ở đây ta có thuật toán do E. Dijkstra nhà toán học người Hà Lan đề xuất năm 1959. Trong phiên bản mà ta sẽ trình bày người ta giả sử đồ thị là vô hướng các trọng số là dương. Chỉ cần thay đổi đôi chút là có thể giải được bài toán tìm đường đi ngắn nhất trong đồ thị có hướng. Phương pháp của thuật toán Dijkstra là xác định tuần tự

Như Anh 49 20 pdf

Upload

Không thể tạo bản xem trước, hãy bấm tải xuống

Tải xuống

TÀI LIỆU LIÊN QUAN

Giáo trình Xây – trát – láng (Trình độ sơ cấp nghề)

253 239 10

Tiểu luận: Tình hình chung của giáo dục đại học, giáo dục đại học ngoài công lập. Hãy phân tích về: Chương trình – Giáo trình

32 730 15

Giáo trình tiếng Hàn: Chữ cái tiếng Hàn quốc

13 288 0

Giáo trình tiếng Hàn: Tổng hợp ngữ pháp tiếng Hàn thực dụng

29 279 0

Giáo trình tiếng Hoa: Đề thi đọc hiểu

4 303 0

Giáo trình tiếng Hoa: Giới thiệu chào hỏi

7 306 0

Giáo trình tiếng Nhật: 完全掌握 2 级日本语能力考试语法对策

1 376 0

Giáo trình tiếng Nhật: Meguro Language Center

12 328 0

Luận văn Thạc sĩ Giáo dục học: Quản lý việc nâng cao trình độ đội ngũ giáo viên tiểu học huyện Phú Giáo, Bình Dương

74 292 1

Mẫu Đăng ký viết giáo trình

3 263 2

TÀI LIỆU XEM NHIỀU

Một Case Về Hematology (1)

8 462336 61

Giới thiệu :Lập trình mã nguồn mở

14 25928 79

Tiểu luận: Tư tưởng Hồ Chí Minh về xây dựng nhà nước trong sạch vững mạnh

13 11335 542

Câu hỏi và đáp án bài tập tình huống Quản trị học

14 10544 466

Phân tích và làm rõ ý kiến sau: “Bài thơ Tự tình II vừa nói lên bi kịch duyên phận vừa cho thấy khát vọng sống, khát vọng hạnh phúc của Hồ Xuân Hương”

3 9835 108

Ebook Facts and Figures – Basic reading practice: Phần 1 – Đặng Tuấn Anh (Dịch)

249 8885 1161

Tiểu luận: Nội dung tư tưởng Hồ Chí Minh về đạo đức

16 8499 426

Mẫu đơn thông tin ứng viên ngân hàng VIB

8 8098 2279

Giáo trình Tư tưởng Hồ Chí Minh - Mạch Quang Thắng (Dành cho bậc ĐH - Không chuyên ngành Lý luận chính trị)

152 7710 1789

Đề tài: Dự án kinh doanh thời trang quần áo nữ

17 7241 268

TỪ KHÓA LIÊN QUAN

TÀI LIỆU MỚI ĐĂNG

Báo cáo nghiên cứu khoa học " KẾT QUẢ NGHIÊN CỨU BƯỚC ĐẦU VỀ THIÊN ĐỊCH CHÂN KHỚP TRÊN CÂY THANH TRÀ Ở THỪA THIÊN HUẾ "

7 275 4 24-12-2024

Báo cáo nghiên cứu khoa học " HÃY LÀM CHO HUẾ XANH HƠN VÀ ĐẸP HƠN "

6 180 3 24-12-2024

Chương 10: Các phương pháp tính quá trình quá độ trong mạch điện tuyến tính

57 232 7 24-12-2024

Báo cáo y học: "The Factors Influencing Depression Endpoints Research (FINDER) study: final results of Italian patients with depressio"

9 147 1 24-12-2024

Báo cáo " Thẩm quyền quản lí nhà nước đối với hoạt động quảng cáo thực trạng và hướng hoàn thiện "

7 204 7 24-12-2024

ĐỀ TÀI " ĐÁNH GIÁ HIỆU QUẢ HOẠT ĐỘNG KINH DOANH NGOẠI HỐI CỦA NGÂN HÀNG THƯƠNG MẠI CỔ PHẦN XUẤT NHẬP KHẨU VIỆT NAM "

51 149 3 24-12-2024

Báo cáo nghiên cứu khoa học " Vai trò chính quyền địa phương trong phát triển kinh tế : khu chuyên doanh gốm sứ ( Trung Quốc ) và Bát Tràng ( Việt Nam )("

11 212 1 24-12-2024

báo cáo khoa học: "Malignant peripheral nerve sheath tumor arising from the greater omentum: Case report"

4 140 1 24-12-2024

Báo cáo nghiên cứu khoa học " Đại hội XVI thông qua điều lệ Đảng cộng sản Trung Quốc những sửa đổi bổ sung mới "

4 161 1 24-12-2024

Lịch sử Trung Quốc 5000 năm tập 3 part 2

54 148 1 24-12-2024

TÀI LIỆU HOT

Mẫu đơn thông tin ứng viên ngân hàng VIB

8 8098 2279

Giáo trình Tư tưởng Hồ Chí Minh - Mạch Quang Thắng (Dành cho bậc ĐH - Không chuyên ngành Lý luận chính trị)

152 7710 1789

Ebook Chào con ba mẹ đã sẵn sàng

112 4406 1371

Ebook Tuyển tập đề bài và bài văn nghị luận xã hội: Phần 1

62 6273 1266

Ebook Facts and Figures – Basic reading practice: Phần 1 – Đặng Tuấn Anh (Dịch)

249 8885 1161

Giáo trình Văn hóa kinh doanh - PGS.TS. Dương Thị Liễu

561 3835 680

Giáo trình Sinh lí học trẻ em: Phần 1 - TS Lê Thanh Vân

122 3917 609

Giáo trình Pháp luật đại cương: Phần 1 - NXB ĐH Sư Phạm

274 4703 565

Tiểu luận: Tư tưởng Hồ Chí Minh về xây dựng nhà nước trong sạch vững mạnh

13 11335 542

Bài tập nhóm quản lý dự án: Dự án xây dựng quán cafe

35 4501 490