Пошук грубою силою

Вичерпний пошук (англ. exhaustive search) або метод грубої сили (англ. brute-force) - загальний метод розв'язання задач та алгоритмічна парадигма^[en], суть якого в систематичному перенумерованні всіх можливих кандидатів на розв'язок і перевірці кандитата на виконання умов.

Для прикладу, алгоритм повного перебору для пошуку дільників натурального числа n. Перераховуємо всі натуральні числа від 1 до n, і перевіряємо кожен з них чи буде він ділити n без остачі. У задачі про вісім ферзів повний перебір полягає в тому, щоб розглянути всі можливі розташування 8 місць з 64 клітин шахової дошки, і, для кожного з них, перевірити, чи може кожна (королева) місце атакувати будь-яке інше.

Хоча повний перебір легко реалізувати і він завжди буде знаходити відповідь (за умови її існування), час виконання при цьому буде пропорційним кількості кандидатів на розв'язок. А в більшості пратичних задач це призводить до дуже швидкого зростання кількості кандидатів, коли зростає розмір задачі (це називається комбінаторним вибухом)^[1]. Тому пошук повним перебором зазвичай використовується, тільки для задач невеликого розміру. Наприклад, евристичний алгоритм може скоротити кількість кандидатів на розв'язок до прийнятного розміру. Також метод повного перебору можна використовувати коли простота реалізації важливіше за швидкість.

Примітки

1. Complexity of brute force search. coursera. Процитовано 14 червня 2018.

Див. також

• Атака повного перебору