GIẢI TOÁN RỜI RẠC

Chia sẻ: Nguyễn Đình Chiểu | Ngày: | Loại File: DOCX | Số trang:6

Thêm vào BST

Báo xấu

127
lượt xem 32
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tham khảo tài liệu 'giải toán rời rạc', khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: GIẢI TOÁN RỜI RẠC

__________________________________________________________________________________________ __________________________________________________________________________________________ __________________________________________________________________________________________ __________________________________________________________________________________________ __________________________________________________________________________________________ __________________________________________________________________________________________ __________________________________________________________________________________________ __________________________________________________________________________________________ __________________________________________________________________________________________ __________________________________________________________________________________________ __________________________________________________________________________________________ __________________________________________________________________________________________ __________________________________________________________________________________________ __________________________________________________________________________________________ __________________________________________________________________________________________ __________________________________________________________________________________________ __________________________________________________________________________________________ __________________________________________________________________________________________ __________________________________________________________________________________________ __________________________________________________________________________________________ __________________________________________________________________________________________ __________________________________________________________________________________________ __________________________________________________________________________________________ __________________________________________________________________________________________ __________________________________________________________________________________________ __________________________________________________________________________________________ __________________________________________________________________________________________ __________________________________________________________________________________________ GIẢI TOÁN RỜI RẠC Chương 5: Một số bài toán tối ưu trên đò thị.
Câu 1: Dùng thuật toán Dijkstra tìm đường ngắn nhất từ đỉnh A đến đỉnh E. Ta có ma trận kề có trong số sau: A B C D E G H K A 4 11 2 B 4 4 3 C 4 2 3 2 D 2 7 4 5 E 7 5 12 G 11 3 4 5 7 H 2 5 7 1 K 3 2 12 1 BÀI GIẢI Tìm đường đi ngắn nhất từ A đến E A B C D E G H K LOẠI 1: 0 A 2: 4(A) 11(A) 2(A) H 3: 7(H) 9(H) 3(H) K 4: 4 5(K) 7 15(K) 9 B 5: 5 7 15 9 C 6: 7 15 8(C) D 7: 14(D) 8 G 8: 13(G) E Đường đi từ A đến E nhỏ nhất là : 13. Chu trình đi: A->H->K->C->G->E. Câu 2: cho đồ thị G có các cạnh như sau: Cạnh Trọng số Cạnh Trọng số 12 10 13 5 23 4 24 1 26 8 34 2 35 7 37 14 46 3 47 5
57 9 67 2 Dùng thuật toán Dijkstra tìm đường đi ngắn nhất từ đỉnh 1 đến 7 1 2 3 4 5 6 7 loại 1: 0 1 2: 10(1) 5(1) 3 3: 9(3) 7(3) 12(3) 19(3) 4 4: 8(4) 12 10(4) 12(4) 2 5: 12 10 12 6 6: 12 12 5 7: 12 7 Đường đi ngắn nhất từ đỉnh 1 đến đỉnh 7 có độ dài: 12. Chu trình đi: 1->3->4->7. Câu 3: Cho đồ thị trọng số : Cạnh Trọng số Cạnh Trọng số 12 10 13 5 23 4 24 1 26 8 34 2 35 7 37 14 46 3 47 5 57 9 67 2 58 2 78 3 Dùng thuật toán dijkstra, chỉ ra đường đi ngắn nhất từ đỉnh 1 đến đỉnh 8. Giải. 1 2 3 4 5 6 7 8 Loại 1: 0 1 2: 10(1) 5(1) 3 3: 9(3) 7(3) 12(3) 19(3) 4 4: 8(4) 12 10(4) 12(4) 2 5: 12 10 12 6 6: 12 12 5 7: 12 14(5) 7 8: 14 8 Đường đi ngắn nhất từ đỉnh 1 đến đỉnh 8 có độ dài: 14. Chu trình đi: 1->3->5->8. Câu 4: cho đồ thị trọng số, tìm đường đi ngắn nhất từ A đến N. Ma trận trọng số Có hướng G
A B C D E F G H K I J L M N A 7 4 1 B 3 2 C 8 6 2 D 3 1 E 3 F 3 3 G 2 5 H 2 4 I 5 2 J 2 K 4 4 9 L 3 5 M 2 3 7 N Giải A B C D E F G H I J K L M N Loạ 1: 0 A 2: 7(A) 4(A) 1(A) J 3: 7 3(J) 3(J) F 4: 6(F) 3 K 5: 6 7(K) 12(K) B 6: 9(B) 7 12 G 7: 9 12 C 8: 17(C) 15(C 11(C L 9: 17 14(L 16(L) H 10: 16(H) 16 D 11: 19(E) 18(D) 16 M 12: 19 18 23(M) I 13: 19 20(I) E 14: 20 N Đường đi ngắn nhất từ A đến n là: A -> J-> F->B->C->L->H->D->I->N = 20. A H
L F C B D I N A Câu 5 Tìm đường đi ngắn nhất từ đỉnh A đến đỉnh G Có ma trận trọng số. A B C D E F G A 3 6 B 3 2 4 C 6 2 1 4 2 D 4 1 2 4 E 4 2 2 1 F 2 2 4 G 4 1 4 GIẢI A B C D E F G LOẠI
1: 0 A 2: 3(A) 6(A) B 3: 5(B) 7(B) C 4: 6(C) 9(C) 7(C) D 5: 8(D) 7 10(D) F 6: 8(F) 10 E 7: 9(E) G Đường đi ngắn nhất từ A đến G là: A->B->C->F->E->G. Độ dài :9