Kata DepthFirstSearch

Giới thiệu kata

Cấp độ của Kata: Dễ

Dùng để luyện về Đệ quy

Kata liên quan: KataBreadthFirstSearch

Mô tả bài toán

Depth-first search (tìm kiếm theo chiều sâu) không chỉ là một kĩ thuật AI mà còn là một tiêu chuẩn để duyệt qua các cây (tree – được dùng phổ biến trong khoa học máy tính).

Hướng dẫn

Mức dễ nhất của depth-first search là làm theo hướng function-call stack thay vì hướng stack data structure.

Tránh triển khai một lớp như Graph, Maze hoặc Problem (dù chỉ để làm mocked interface) làm depth-first-searcher để duyệt. Thay vào đó hãy đặt câu hỏi như một “người” dùng (ví dụ: standard in/standard out hoặc theo ngôn ngữ của bạn). Ví dụ: “Các lối ra là gì?” và “Chúng ta đang ở đâu?”. Điều này sẽ tạo ra được các kiểm thử thăm dò rất thú vị. Nếu xây dựng Graph hoặc Maze bằng cách khởi tạo dữ liệu hoặc phân tích một file thì sẽ làm chậm nhóm và mất ý nghĩa của bài Kata.

Tất nhiên, bạn nên giả lập các cuộc hội thoại trong các kiểm thử đơn vị của mình. Điều này chứng tỏ rằng kiểm thử thăm dò có thể được ghi lại trong các kiểm thử tự động có khả năng lặp lại, thứ có giá trị.

Gợi ý các ca kiểm thử

• One-node graph.
• Two-node graph.
• 2×2 maze.
• Cây nhị phân đầy đủ 2 cấp độ (full two-level binary tree).
• 3×3 maze.

Nguồn Kata: http://codingdojo.org/kata/DepthFirstSearch/