Tìm Kiếm Theo Chiều Sâu - .vn

Donate to VNFoundation Project name

• Trang chủ
• Tra cứu tài liệu
• Đóng góp
• Giới thiệu

• • 
• Đăng ký
• Đăng nhập

Đăng nhập

• Ghi nhớ
• Quên mật khẩu?

Đăng nhập Bạn chưa có tài khoản? Hãy đăng ký. Tên đăng nhập hoặc mật khẩu chưa đúng TÀI LIỆU Tìm kiếm theo chiều sâu Science and Technology 0

Tìm kiếm ưu tiên chiều sâu hay tìm kiếm theo chiều sâu (tiếng Anh: Depth-first search - DFS) là một thuật toán duyệt hoặc tìm kiếm trên một cây hoặc một đồ thị. Thuật toán khởi đầu tại gốc (hoặc chọn một đỉnh nào đó coi như gốc) và phát triển xa nhất có thể theo mỗi nhánh.

Thông thường, DFS là một dạng tìm kiếm thông tin không đầy đủ mà quá trình tìm kiếm được phát triển tới đỉnh con đầu tiên của nút đang tìm kiếm cho tới khi gặp được đỉnh cần tìm hoặc tới một nút không có con. Khi đó giải thuật quay lui về đỉnh vừa mới tìm kiếm ở bước trước. Trong dạng không đệ quy, tất cả các đỉnh chờ được phát triển được bổ sung vầo một ngăn xếp LIFO.

Độ phức tạp không gian của DFS thấp hơn của BFS (tìm kiếm ưu tiên chiều rộng). Độ phức tạp thời gian của hai thuật toán là tương đương nhau và bằng O(|V| + |E|).

Tìm kiếm ưu tiên chiều sâu bắt đầu thăm đỉnh A, đi theo cạnh trái, tiếp tục tìm kiếm xong ở cây con trái mới chuyển sang tìm kiếm ở cây con phải. Thứ tự thăm viếng các đỉnh là:

Quá trình viếng thăm các đỉnh diễn ra như sau: Sau khi thăm đỉnh A, vì B chưa được thăm nên theo cạnh AB ta thăm B, tiếp tục theo cạnh BD tới viếng thăm D. Từ D không thê tiếp tục đi xa hơn, ta quay lại B. Từ B, theo BF đến thăm BF, từ F đến thăm E. Từ E vì A đã viếng thăm nên ta quay lại F, rồi quay lại B. Tại B vì tất cả các khả năng từ B đã xem xét nên ta quay lại A. Từ A, quá trình tiếp tục với các đỉnh C và G.

Một cách tự nhiên, kết quả của giải thuật tìm kiếm theo chiều sâu là một cây phủ qua tất cả các đỉnh được duyệt của đồ thị.

Duyệt các đỉnh

Có thể dùng giải thuật này để tạo một danh sách tuyến tính các đỉnh của một đồ thị (hoặc cây). Có ba cách hiện thực phương pháp này:

Duyệt tiền thứ tự (preordering): tạo ra một danh sách mà trong đó các định xuất hiện theo đúng trật tự nó được thăm đến khi chạy thuật toán. Đây chính là biểu diễn tự nhiên của quá trình thực hiện giải thuật tìm kiếm theo chiều sâu. Một biểu thức ở dạng tiền thứ tự được gọi là kí pháp tiền tố.

Duyệt hậu thứ tự (postordering): tạo ra một danh sách mà trong đó các đỉnh xuất hiện theo thứ tự của lần duyệt đến sau cùng khi thực hiện giải thuật. Một lần suyệt hậu thứ tự một cây biểu thức sẽ cho ra một kí pháp hậu tố.

Duyệt đảo hậu thứ tự (reverse postordering): kết quả của cách duyệt này là sự đảo ngược lại thứ tự trong kết quả duyệt hậu thứ tự. Thông thường, khi duyệt cây, cách này cho ra cùng kết quả với duyệt tiền thứ tự, nhưng xét tổng quát, khi duyệt một đồ thị, tiền thứ tự và đảo hậu thứ tự cho ra kết quả khác nhau. Với các đồ thị có hướng và không có vòng, cách duyệt đảo hậu thứ tự cho ra một trật tự tô-pô của đồ thị đó.

Ứng dụng

Nhiều giải thuật sử dụng tìm kiếm theo chiều sâu:

Xác định các thành phần liên thông của đồ thị

Sắp xếp tô-pô cho đồ thị

Xác định các thành phần liên thông mạnh của đồ thị có hướng

Kiểm tra một đồ thị có phải là đồ thị phẳng hay không

0 TẢI VỀ TÁI SỬ DỤNG

• Tài liệu PDF
• Tài liệu EPUB

• Wikipedia
• 0 GIÁO TRÌNH | 5753 TÀI LIỆU

NỘI DUNG CÙNG TÁC GIẢ

• Bù 1 (hệ nhị phân)
• Axít oxalic
• Chi Kniphofia
• Bộ Cá vược
• Cá sấu Ấn Độ giả
• Sông Lô
• Khí đồng hành
• Họ Cá tuyết sông
• Hồ Thang Hen
• Lớp Cá vây thùy

×

VOER message

×

VOER message

Thư viện Học liệu Mở Việt Nam (VOER) được tài trợ bởi Vietnam Foundation và vận hành trên nền tảng Hanoi Spring. Các tài liệu đều tuân thủ giấy phép Creative Commons Attribution 3.0 trừ khi ghi chú rõ ngoại lệ.

•