TAILIEUCHUNG - GIÁO TRÌNH LÝ THUYẾT ĐỒ 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ị | 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 . . 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Ừ KHÓA LIÊN QUAN
Đã 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.