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Ị - CHƯƠNG 3
Đang chuẩn bị liên kết để tải về tài liệu:
GIÁO TRÌNH LÝ THUYẾT ĐỒ THỊ - CHƯƠNG 3
Mỹ Nga
108
20
pdf
Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
CÁC THUẬT TOÁN TÌM KIẾM TRÊN ĐỒ THỊ VÀ ỨNG DỤNG Rất nhiều thuận toán trên đồ thị được xây dựng trên cơ sở duyệt tất cả các đỉnh của đồ thị sao cho mỗi đỉnh của nó được viếng thăm đúng một lần. Vì vậy, việc xây dựng những thuật toán cho phép duyệt một cách hệ thống tất cả các đỉnh của đồ thị là một vấn đề quan trọng thu hút sự quan tâm nghiên cứu của nhiều tác giả. Những thuật toán như vậy chúng ta sẽ gọi là thuật toán tìm kiếm trên đồ thị | CHƯƠNG 3. CÁC THUẬT TOÁN TÌM KIẾM TRÊN ĐÒ THỊ VÀ ỨNG DỤNG Rất nhiều thuận toán trên đồ thị được xây dựng trên cơ sở duyệt tất cả các đỉnh của đồ thị sao cho mỗi đỉnh của nó được viếng thăm đúng một lần. Vì vậy việc xây dựng những thuật toán cho phép duyệt một cách hệ thống tất cả các đỉnh của đồ thị là một vấn đề quan trọng thu hút sự quan tâm nghiên cứu của nhiều tác giả. Những thuật toán như vậy chúng ta sẽ gọi là thuật toán tìm kiếm trên đồ thị. Trong mục này chúng ta sẽ giới thiệu hai thuật toán tìm kiếm cơ bản trên đồ thị Thuật toán tìm kiếm theo chiều sâu Depth Firt Search và Thuật toán tìm kiếm theo chiều rộng Breadth First Search và ứng dụng của chúng vào việc giải một số bài toán trên đồ thị. Trong mục này chúng ta sẽ xét đồ thị vô hướng G V E với đỉnh n và m cạnh. Chúng ta sẽ quan tâm đến việc đánh giá hiệu quả của các thuật toán trên đồ thị màmột trong những đặc trưng quan trọng nhất là độ phức tạp tính toán tức là số phép toán mà thuật toán cần phải thực hiện trong tình huống xấu nhất được biểu diễn như hàm của kích thước đầu vào của bài toán. Trong các thuật toán trên đồ thị đầu vào là đồ thị G V E vì vậy kích thước của bài toán là số đỉnh n và số cạnh m của đồ thị. Khi đó độ phức tạp tính toán của thuật toán sẽ được biểu diễn như là hàm của hai biến số f n m là số phép toán nhiều nhất cần phải thực hiện theo thuật toán đối với mọi đồ thị n đỉnh và m cạnh. Khi so sánh tốc độ tăng của hai hàm nhận giá trị không âm f n và g n chúng ta sẽ sử dụng ký hiệu sau f n O g n U tìm được các hằng sô C N 0 sao cho f n C g n với mọi n N. Tương tự như vậy nếu f n1 n2 . . . nk g ưi n2 . . . nk là các hàm nhiều biến ta viết f ni n2 . . . nk O g ni n2 . . . nk U tìm được các hằng số C N 0 sao cho f n1 n2 . . . nk C g n1 n2 . . . nk với mọi n1 n2 . . . nk N. Nếu độ phức tạp tính toán của thuật toán là O g n thì ta sẽ còn nói là nó đòi hỏi thời gian tính cỡ O g n . 3.1. Tìm kiếm theo chiều sâu trên đồ thị Ý tưởng chính của thuật toán có thể trình bày như sau. Ta sẽ bắt .
TÀI LIỆU LIÊN QUAN
Giáo trình Lý thuyết đồ thị: Phần 1 - PGS. Nguyễn Cam, PTS. Chu Đức Khánh
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)
Giáo trình Lý thuyết tài chính - tiền tệ (Nghề Kế toán doanh nghiệp - Trình độ Trung cấp) - CĐ GTVT Trung ương I
Quản lý môi trường đô thị và khu công nghiệp
Giáo trình Toán rời rạc và lý thuyết đô thị
Giáo trình Mô hình toán ứng dụng (Có hướng dẫn sử dụng phần mềm): Phần 1
Kiến trúc sư làm gì để biến đổi đô thị?
Giáo án môn lý thuyết đồ thị
Bài tập về lý thuyết đồ thị
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.