Topological Sort là gì
Ngày đăng:
02/01/2022
Trả lời:
0
Lượt xem:
236
Ly thuyet ve thuat toan sắp xếp topo và giải thuậ dijkstraBạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (571.38 KB, 28 trang ) VIỆN ĐÀO TẠO CHẤT LƯỢNG CAO 1. 2. 3. 4. GIỚI THIỆU VỀ SẮP XẾP TOPO4 MƠ TẢ VÀ PHÂN TÍCH ĐỘ PHỨC TẠP...5 CODE MẪU..11 KẾT LUẬN VÀ ĐÁNH GIÁ13 PHẦN III: GIẢI THUẬT DJIKSTRA.14 1. 2. 3. 4. GIỚI THIỆU VỀ GIẢI THUẬT DJIKSTRA14 MƠ TẢ VÀ PHÂN TÍCH ĐỘ PHỨC TẠP...15 CODE MẪU...25 KẾT LUẬN VÀ ĐÁNH GIÁ.27 2|Page PHẦN I: LỜI NÓI ĐẦU Lý thuyết đồ thị là một lĩnh vực nghiên cứu đã có từ lâu đờivà có nhiều ứng dụng hiện đại.Những tư tưởng cơ bản của lý thuyết đồ thị đươc đề xuất từ những năm đầu của thế kỷ 18 bởi nhà toán học lỗi lạc người Thụy Sĩ Leonhard Euler.Chính ơng là người đã sử dụng đồ thị để giải bài toán nổi tiếng về các cái cầu ở thàng phố Konigsberg. Đồ thị được sử dụng để giải quyết các bài toán trong nhiều lĩnh vực khác nhau .Chẳng hạn , đồ thị có thể sử dụng để xác định các mạch vịng trong vấn đề giải tích mạch điện.Chúng ta có thể phân biệt các hợp chất hố học hữu cơ khác nhau với cùng công thức phân tử nhưng khác nhau về cấu trúc phân tử nhờ đồ thị.Chúng ta có thể xác định xem hai máy tính trong mạng có thể trao đổi thơng tin được với nhau hay khơng nhờ mơ hình đồ thị của mạng máy tính. Đồ thị có trọng số trên các cạnh có thể sử dụng để giải các bài tốn như : tìm đường đi ngắn nhất giữa hai thành phố trong cùng một mạng giao thơng . Chúng ta cịn sử dụng đồ thị để giải các bài toán về lập lịch,thời khoá biểu,và phân bố tần số cho các trạm phát thanh và truyền hình.... Mục đích ta tìm hiểu là nhằm giới thiệu các khái niệm cơ bản,các bài toán ứng dụng quan trọng của lý thuyết đồ thị như bài toán cây khung nhỏ nhất , bài tốn tìm đường đi ngắn nhất... và những thuật tốn để giải quyết chúng đã được trình bày chi tiết cùng với việc phân tích và hướng dẫn cài đặt chương trình trên máy tính. 3|Page PHẦN II: SẮP XẾP TOPO 1. GIỚI THIỆU VỀ SẮP XẾP TOPO: - Thông thường đối với một công việc lớn bao giờ ta cũng cần phải chia nó thành nhiều phần để thực hiện. Có những phần việc có thể thực hiện được độc lập nhưng cũng có những phần việc chỉ thực hiện được khi một số phần việc khác đã được làm xong. - Sắp xếp topo (topological sorting) là một trong những bài tốn có tính ứng dụng cao cả trong Tin học lẫn Toán học và đời sống thường ngày. Đây là quá trình sắp xếp một dãy các phần tử sao cho thứ tự mới vẫn đảm bảo được thứ tự cục bộ (một cách nơm na có nghĩa là thứ tự được xác định đối với một vài cặp phần tử chứ không phải là tất cả các phần tử) vốn có của chúng. Nhờ sắp xếp topo mà ta có thể tính được thời gian tối thiểu để thực hiện một chuỗi các công việc. - Ý tưởng sắp xếp topo là dựa trên DFS (tìm kiếm theo độ sâu). Điều kiện để thực hiện topological sorting đó là DAG (đồ thị khơng có chu trình). Thực tế, thơng qua việc sắp xếp, ta có thể kiểm tra xem đồ thị đó có chứa chu trình hay khơng. Một đồ thị khơng có chu trình sẽ có ít nhất 1 sắp xếp topo. - VD: Trong một số trường ĐH ở VN hiện nay, có những học phần gọi là học phần tiên quyết mà sinh viên buộc phải hoàn thành trước khi học các học phần khác. Nếu học phần v là học phần tiên quyết đối với học phần w, kí hiệu là u |