Brute-force search là gì?

Trong khoa học máy tính (computer science), tìm kiếm brute-force (brute-force search) là một kỹ thuật giải quyết vấn đề đơn giản nhưng rất chung chung, bao gồm liệt kê một cách có hệ thống tất cả các ứng viên có thể có cho giải pháp và kiểm tra xem từng ứng viên có đáp ứng yêu cầu của bài toán hay không. Ví dụ: một thuật toán brute-force để tìm các ước của một số tự nhiên n là liệt kê tất cả các số nguyên từ 1 đến căn bậc hai của n và kiểm tra xem mỗi ước trong số chúng có chia cho n mà không có dư hay không. Ví dụ khác, hãy xem xét câu đố tám quân hậu phổ biến, yêu cầu đặt tám quân hậu trên một bàn cờ tiêu chuẩn để không có quân hậu nào tấn công con nào khác. Cách tiếp cận brute-force sẽ kiểm tra tất cả các cách sắp xếp có thể có của 8 quân trong 64 ô vuông, và đối với mỗi cách sắp xếp, kiểm tra xem có quân hậu nào tấn công quân nào khác hay không.

Tìm kiếm brute-force (brute-force search) rất dễ thực hiện và sẽ luôn tìm ra giải pháp nếu nó tồn tại. Tuy nhiên, chi phí của nó tỷ lệ thuận với số lượng các ứng viên, trong nhiều vấn đề thực tế, có xu hướng phát triển rất nhanh khi quy mô của bài toán tăng lên. Do đó, tìm kiếm brute-force (brute-force search) thường được sử dụng khi kích thước bài toán bị giới hạn hoặc khi có heuristics của từng bài toán cụ thể có thể được sử dụng để giảm tập hợp các ứng viên xuống kích thước có thể quản lý được.