Tìm kiếm theo chiều sâu trong Python: Duyệt đồ thị và cây

Hãy tưởng tượng bạn đang khám phá một hệ thống hang động rộng lớn. Bạn chọn một đường hầm và đi theo nó sâu dần, sâu dần cho đến khi gặp ngõ cụt. Sau đó, bạn quay lại ngã rẽ gần nhất và thử một đường hầm mới. Cách khám phá theo chiều sâu này, chỉ quay lại khi cần thiết, rất giống với tìm kiếm theo chiều sâu (DFS), một thuật toán nền tảng để điều hướng các cấu trúc dữ liệu như đồ thị và cây.

Nếu bạn quan tâm đến cấu trúc dữ liệu, thuật toán và giải quyết vấn đề, DataCamp có đầy đủ cho bạn: Tìm hiểu thêm về các cấu trúc dữ liệu khác nhau và những thuật toán tốt nhất để khám phá chúng trong khóa học Data Structures and Algorithms in Python và bài hướng dẫn Data Structures: A Comprehensive Guide With Python Examples.

Tìm kiếm theo chiều sâu là gì?

Tìm kiếm theo chiều sâu (DFS) là một thuật toán dùng để duyệt hoặc tìm kiếm trong một cấu trúc dữ liệu, như đồ thị hoặc cây. Ý tưởng cốt lõi của DFS là khám phá xuống sâu nhất có thể theo một nhánh của đồ thị hoặc cây trước khi quay lui để khám phá các nhánh thay thế. Cách tiếp cận này trái ngược với tìm kiếm theo bề rộng, vốn khám phá tất cả các nút ở mức độ sâu hiện tại trước khi chuyển sang mức tiếp theo. Bạn có thể đọc về tìm kiếm theo bề rộng TẠI ĐÂY.

Hãy coi tìm kiếm theo chiều sâu như cách bạn khám phá một mê cung: bạn chọn một lối đi và đi theo cho đến khi gặp ngõ cụt. Khi đến cuối con đường đó, bạn quay lại điểm quyết định gần nhất và thử một hướng khác. Sự khám phá sâu này khiến DFS trở thành lựa chọn tuyệt vời khi mục tiêu là khám phá toàn diện một cấu trúc, đặc biệt là cấu trúc có nhiều đường đi tiềm năng.

DFS đặc biệt hữu ích trong các bài toán mà bạn cần khám phá mọi khả năng có thể.

Một vài ví dụ gồm:

• Điều hướng cây quyết định trong AI, nơi mỗi nhánh đại diện cho một chuỗi lựa chọn, và mục tiêu là đánh giá mọi kết quả có thể.
• Các bài toán tìm đường, như di chuyển trên bàn cờ hoặc tìm tuyến đường trên bản đồ, yêu cầu tìm kiếm toàn diện.

DFS đảm bảo mỗi nút được thăm một lần và thuật toán bao phủ toàn bộ đồ thị hoặc cây.

Các đặc trưng chính của tìm kiếm theo chiều sâu trong Python

Tìm kiếm theo chiều sâu có cách tiếp cận có hệ thống để khám phá các nút và chỉ quay lui khi cần. Hãy cùng xem một số đặc điểm chính của nó.

Tính đệ quy

Cốt lõi của DFS hoạt động theo kiểu đệ quy, nghĩa là nó giải quyết vấn đề bằng cách tự gọi lặp lại khi đi sâu hơn vào cấu trúc. Khi DFS đi vào một nhánh, nó khám phá nhánh đó sâu nhất có thể trước khi quay lại để khám phá các nhánh khác. Quá trình đi sâu theo một đường và quay lui khi không còn lựa chọn nào nữa được xử lý lý tưởng thông qua đệ quy. Hãy xem Understanding Recursive Functions in Python để tìm hiểu sâu về hàm đệ quy và khi nào chúng hữu ích.

Quay lui (Backtracking)

Quay lui là thành phần thiết yếu của DFS. Khi thuật toán gặp một nút không còn láng giềng chưa thăm nào, nó lần theo dấu quay lại nút trước đó và kiểm tra xem ở đó còn láng giềng chưa thăm nào khác không. Nếu có, nó sẽ khám phá các nút đó; nếu không, nó tiếp tục quay lui. Chu trình đi sâu và quay lại này tiếp diễn cho đến khi mọi đường đi có thể đều được bao phủ hoặc một điều kiện dừng được đáp ứng.

Xử lý chu trình

Đồ thị có thể chứa chu trình, tức là các đường đi quay trở lại chính nó. Nếu không có biện pháp thích hợp, DFS có thể lặp lại các nút trong những chu trình này vô tận. Bằng cách đánh dấu mỗi nút là đã thăm ngay lần đầu gặp, DFS có thể tránh việc lần theo dấu không cần thiết. Nhờ vậy, ngay cả trong đồ thị có chu trình, DFS vẫn hiệu quả và tránh được vòng lặp vô hạn.

Khám phá toàn diện

Một trong những điểm nổi bật của DFS là khả năng khám phá toàn bộ cấu trúc. Thuật toán tiếp tục cho đến khi mọi nút đều được thăm. Điều này đặc biệt hữu ích khi bạn cần đảm bảo không bỏ sót bất kỳ lời giải tiềm năng nào, như khi giải đố, khám phá cây quyết định hoặc điều hướng mê cung.

Triển khai tìm kiếm theo chiều sâu trong Python

Có hai cách chính để triển khai tìm kiếm theo chiều sâu trong Python: đệ quy và lặp. Mỗi cách có ưu và nhược điểm riêng, và lựa chọn thường phụ thuộc vào kích thước của đồ thị và vấn đề bạn đang giải.

Để minh họa cả hai phương pháp, hãy tạo một cây quyết định đơn giản và dùng DFS để duyệt nó. Chúng ta sẽ dùng Python cho ví dụ. Bạn luôn có thể xem lộ trình kỹ năng Python Programming để ôn lại kỹ năng Python của mình.

Hãy lấy một cây quyết định nhị phân làm ví dụ. Đây là một cấu trúc cây đơn giản nơi mỗi nút có hai nhánh con:

Hãy định nghĩa rõ cây quyết định này trong Python dưới dạng một dictionary.

# Define the decision tree as a dictionary
tree = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F', 'G'],
    'D': ['H', 'I'],
    'E': ['J', 'K'],
    'F': ['L', 'M'],
    'G': ['N', 'O'],
    'H': [], 'I': [], 'J': [], 'K': [],
    'L': [], 'M': [], 'N': [], 'O': []
}Được hỗ trợ bởi

DFS đệ quy

DFS thường được triển khai đệ quy. Tại mỗi nút, DFS tự gọi trên các nút con của nó cho đến khi không còn nút nào để thăm, rồi quay lui. Dưới đây là một hàm DFS đệ quy để duyệt cây.

# Recursive DFS function
def dfs_recursive(tree, node, visited=None):
    if visited is None:
        visited = set()  # Initialize the visited set
    visited.add(node)    # Mark the node as visited
    print(node)          # Print the current node (for illustration)
    for child in tree[node]:  # Recursively visit children
        if child not in visited:
            dfs_recursive(tree, child, visited)

# Run DFS starting from node 'A'
dfs_recursive(tree, 'A')Được hỗ trợ bởi

Trong phiên bản đệ quy này, chúng ta bắt đầu tại nút gốc A và khám phá xuống từng nhánh trước khi quay lui để khám phá các lựa chọn khác. Nếu chạy đoạn mã này, nó sẽ in ra đường đi mà nó đã thực hiện khi khám phá cây:

A
B
D
H
I
E
J
K
C
F
L
M
G
N
OĐược hỗ trợ bởi

DFS lặp

Với những cây quyết định rất lớn, giới hạn độ sâu đệ quy của Python có thể gây ra vấn đề. Trong những trường hợp đó, chúng ta có thể triển khai DFS theo cách lặp, dùng một ngăn xếp để quản lý các nút cần thăm. Dưới đây là cách chúng ta có thể triển khai DFS lặp cho cùng cây quyết định:

# Iterative DFS function
def dfs_iterative(tree, start):
    visited = set()  # Track visited nodes
    stack = [start]  # Stack for DFS

    while stack:  # Continue until stack is empty
        node = stack.pop()  # Pop a node from the stack
        if node not in visited:
            visited.add(node)  # Mark node as visited
            print(node)        # Print the current node (for illustration)
            stack.extend(reversed(tree[node]))  # Add child nodes to stack

# Run DFS starting from node 'A'
dfs_iterative(tree, 'A')Được hỗ trợ bởi

Cách tiếp cận lặp này tránh giới hạn độ sâu đệ quy bằng cách xử lý ngăn xếp thủ công, hữu ích cho các cây lớn hoặc cấu trúc sâu. Chạy đoạn mã này cho kết quả giống như trên.

Khi nào dùng DFS đệ quy so với DFS lặp

Cả hai cách tiếp cận đệ quy và lặp cho tìm kiếm theo chiều sâu đều là công cụ hữu ích, nhưng lựa chọn giữa chúng phụ thuộc vào cấu trúc của đồ thị và nhu cầu cụ thể của bạn. Hãy xem kỹ hơn điểm mạnh và hạn chế của từng cách.

DFS đệ quy

Tôi thường ưu tiên DFS đệ quy vì sự đơn giản và thanh thoát. Cách tiếp cận này trực quan và gọn gàng.

Ưu điểm:

• Đơn giản: Mã ngắn gọn và phản ánh tốt bản chất vấn đề.
• Dễ đọc: Dễ hiểu hơn, đặc biệt với các bài toán nhỏ đến vừa.

Nhược điểm:

• Giới hạn độ sâu đệ quy: Với đồ thị lớn, bạn có thể chạm tới giới hạn độ sâu đệ quy của Python.

Đệ quy lý tưởng cho các bài toán mà cây hoặc đồ thị tương đối nhỏ và nằm trong giới hạn độ sâu đệ quy của Python.

DFS lặp

Dù viết phức tạp hơn đôi chút, DFS lặp linh hoạt hơn và có thể xử lý bài toán lớn mà không lo giới hạn đệ quy. Thay vì dựa vào call stack của Python, DFS lặp quản lý tường minh các nút cần khám phá thông qua một ngăn xếp.

Ưu điểm:

• Không bị giới hạn đệ quy: Tự quản lý ngăn xếp giúp tránh giới hạn độ sâu đệ quy của Python.

Nhược điểm:

• Nhiều mã: DFS lặp cần nhiều thiết lập hơn và có thể kém trực quan.
• Tính dễ đọc: Mã thường dài dòng hơn đôi chút, khiến khó theo dõi hơn.

Cách tiếp cận lặp phù hợp nhất cho các bài toán lớn hoặc phức tạp khi lo ngại về độ sâu đệ quy. Nó cũng hữu ích khi bạn cần kiểm soát nhiều hơn việc duyệt.

Độ phức tạp thời gian và bộ nhớ

DFS là một thuật toán hiệu quả, nhưng hiệu năng của nó bị ảnh hưởng bởi kích thước và cấu trúc của đồ thị đang khám phá. Thời gian chạy và lượng bộ nhớ sử dụng phụ thuộc vào số lượng nút được thăm cũng như các kết nối giữa chúng.

Chúng ta dùng ký hiệu Big O để bàn về độ phức tạp. Để ôn lại ký hiệu Big O, hãy xem Big O Notation and Time Complexity Guide: Intuition and Math.

Độ phức tạp thời gian

Độ phức tạp thời gian của DFS là O(V + E), trong đó V là số nút và E là số kết nối (gọi là "cạnh"). DFS thăm mỗi nút và mỗi kết nối một lần. Vì vậy, tổng thời gian phụ thuộc vào số lượng nút và kết nối.

Độ phức tạp bộ nhớ

Bộ nhớ dùng trong DFS phụ thuộc vào số lượng nút mà thuật toán theo dõi tại một thời điểm. Cả DFS đệ quy và lặp đều dùng một ngăn xếp để theo dõi các nút đang được khám phá. Ở kịch bản xấu nhất, bộ nhớ dùng có thể chứa tất cả các nút trong đồ thị, dẫn tới độ phức tạp bộ nhớ O(V).

Khám phá các cách khác để đo độ phức tạp thuật toán trong bài hướng dẫn Analyzing Complexity of Code through Python.

Ứng dụng thực tế của tìm kiếm theo chiều sâu

DFS hữu ích trong nhiều lĩnh vực, bao gồm khoa học máy tính, AI và phát triển game. Xem bảng dưới đây để biết một số ứng dụng phổ biến của DFS.

Tìm kiếm theo chiều sâu so với các thuật toán tìm kiếm khác

Hãy so sánh DFS với các thuật toán nổi tiếng khác như tìm kiếm theo bề rộng, Dijkstra và A*.

Tìm kiếm theo chiều sâu và tìm kiếm theo bề rộng

Tìm kiếm theo bề rộng (BFS) khám phá đồ thị theo từng tầng, thăm tất cả các nút ở độ sâu hiện tại trước khi chuyển sang tầng tiếp theo. BFS đặc biệt hữu ích khi mục tiêu là tìm đường đi ngắn nhất trong đồ thị không trọng số. Tuy nhiên, BFS có thể dùng nhiều bộ nhớ, nhất là trong đồ thị rộng, vì nó phải theo dõi tất cả các nút ở mỗi tầng. BFS là lựa chọn tuyệt vời cho phân tích mạng xã hội hoặc các bài toán định tuyến đơn giản.

Ngược lại, tìm kiếm theo chiều sâu hữu ích khi mục tiêu là khám phá mọi đường đi hoặc lời giải, như giải đố hoặc tìm chu trình trong đồ thị. Không giống BFS, DFS không đảm bảo đường đi ngắn nhất. Nhưng nó tiết kiệm bộ nhớ hơn, vì chỉ theo dõi đường đi hiện tại.

Bạn có thể tìm hiểu thêm về tìm kiếm theo bề rộng trong Breadth-First Search: A Beginner’s Guide with Python Examples.

DFS và thuật toán Dijkstra

Thuật toán Dijkstra được thiết kế để tìm đường đi ngắn nhất trong đồ thị có cạnh mang trọng số, nơi mỗi liên kết giữa các nút có chi phí đi kèm. Dijkstra hoạt động bằng cách luôn khám phá đường đi có chi phí thấp nhất trước, đảm bảo tìm được đường tối ưu từ nút bắt đầu đến bất kỳ nút nào khác. Tuy nhiên, trong một số duyệt đồ thị đơn giản, nó có thể chậm hơn DFS. Dijkstra rất phù hợp cho các tác vụ mà trọng số cạnh quan trọng, như mạng đường bộ hoặc các bài toán định tuyến phức tạp hơn.

Tìm kiếm theo chiều sâu không xét trọng số cạnh, nên sẽ không đảm bảo đường đi tối ưu. Tuy nhiên, nó nhanh hơn Dijkstra trong đồ thị không trọng số hoặc khi trọng số cạnh không liên quan.

Bạn có thể tìm hiểu thêm về thuật toán Dijkstra trong Implementing the Dijkstra Algorithm in Python: A Step-by-Step Tutorial.

DFS và A*

A* (đọc là “A-star”) là một thuật toán cải tiến dựa trên Dijkstra bằng cách kết hợp một heuristic để dẫn hướng tìm kiếm. Điều này khiến nó nhanh hơn và hiệu quả hơn trong nhiều trường hợp. A* cân bằng giữa việc khám phá các đường đi có chi phí thấp nhất (như Dijkstra) và tiến thẳng về phía mục tiêu, sử dụng một heuristic như khoảng cách thẳng đến mục tiêu. Điều này làm A* rất hiệu quả cho các tác vụ như định vị GPS hoặc tìm đường trong trò chơi.

Tìm kiếm theo chiều sâu không dùng bất kỳ heuristic nào, nghĩa là thiếu “định hướng” mà A* dùng để đến mục tiêu hiệu quả. DFS phù hợp hơn cho các bài toán cần tìm kiếm kỹ lưỡng toàn bộ đồ thị hoặc cây quyết định, trong khi A* tốt hơn khi cần tìm đường đi ngắn nhất một cách hiệu quả với sự hỗ trợ của heuristic.

Những sai lầm thường gặp và cách tránh

Khi dùng tìm kiếm theo chiều sâu, một số vấn đề phổ biến có thể xảy ra, đặc biệt với các đồ thị lớn.

Không theo dõi các nút đã thăm

Một vấn đề phát sinh khi quên theo dõi những nút đã được thăm. Điều này có thể dẫn đến vòng lặp vô hạn, nhất là trong đồ thị có chu trình. Khi DFS quay lại các nút mà không kiểm tra xem chúng đã được khám phá hay chưa, nó có thể bị kẹt trong vòng lặp vô hạn. Để tránh điều này, hãy đảm bảo duy trì một danh sách (tập) các nút đã thăm. Trước khi thăm một nút mới, kiểm tra xem nó đã có trong tập đã thăm chưa. Nếu có, bạn có thể bỏ qua an toàn và tránh bị mắc kẹt.

Tràn ngăn xếp trong DFS đệ quy

Trong Python, độ sâu đệ quy mặc định bị giới hạn khoảng 1.000 mức, nghĩa là các lời gọi đệ quy lồng nhau sâu trong đồ thị lớn có thể gây ra RecursionError. Để ngăn điều này, chúng ta có thể dùng triển khai DFS lặp cho đồ thị lớn. Bằng cách duy trì ngăn xếp dưới dạng một danh sách, chúng ta tránh được giới hạn độ sâu đệ quy và có thể xử lý an toàn các đồ thị lớn hơn nhiều.

Nhầm lẫn một lời giải với đường đi ngắn nhất

Cũng quan trọng để nhớ rằng DFS không đảm bảo đường đi ngắn nhất giữa hai nút. Vì DFS đi sâu theo một đường trước khi quay lui để khám phá đường khác, nó có thể tìm ra một lời giải, nhưng có thể không phải là đường đi trực tiếp nhất.

Kết luận

Tìm kiếm theo chiều sâu là một thuật toán mạnh mẽ để khám phá và duyệt đồ thị và cây. Với khả năng đi sâu vào các đường đi và khám phá mọi khả năng, nó rất phù hợp cho nhiều bài toán như giải mê cung, giải đố và khám phá cây quyết định.

Nếu bạn quan tâm đến các thuật toán tìm kiếm, hãy xem các bài viết khác trong loạt này của tôi: Binary Search in Python: A Complete Guide for Efficient Searching và Breadth-First Search: A Beginner’s Guide with Python Examples. Bạn cũng có thể quan tâm đến AVL Tree: Complete Guide With Python Implementation, và Introduction to Network Analysis in Python.