Глава 5. МЕТОДЫ РАСПРОСТРАНЕНИЯ ОГРАНИЧЕНИЙ И ПЕРЕБОРА
Методы перебора традиционно применяются при решений большинства задач. Им посвящена большая часть данной главы, а также последующие гл. 6 и 7.
5.1. Решение задач с помощью перебора
Класс комбинаторных задач
Сущность любой комбинаторной задачи можно сформулировать следующим образом:
«Найти на множестве X элемент х, удовлетворяющий совокупности условий 
в предположении, что пространство поиска X содержит некоторое конечное число различных точек».
Подобные ситуации возникают всегда, когда мы имеем дело с дискретными по природе элементами: логические головоломки; проблемы пополнения запасов на складе; выбор решения из множества возможных; выбор места расположения нового завода; прохождение пути по графу; доказательство теорем. Во всех этих случаях пространство поиска X является конечным и дискретным. Последнее означает, что все точки X отделены друг от друга. Именно при решении таких задач могут использоваться методы перебора.
Метод полного перебора
Когда требуется найти элемент, принадлежащий некоторому конечному множеству, мы можем перебирать все элементы, пока не найдем подходящий. Этот метод надежен, прост и прекрасно работает, если мощность множества не превышает 103 для ручного подсчета или 109 при подсчете на машине. Схема действий следующая:
1. Взять первый еще не рассмотренный элемент 
из множества X.
2. Проверить совокупность условий 
3. Если какое-либо условие не выполнено, начать сначала.
4. Если выполнены все условия, 
является решением (если нужны все решения, вернуться к п. 1).
Такой метод явного перебора можно легко усовершенствовать: вместо рассмотрения всего элемента 
можно ограничиться некоторым его фрагментом, достаточным для проверки выполнения/невыполнения условий 
.
Рис. 5.1. Прохождение лабиринта.
В 1891 г. Э. Люка в «Математических досугах» описал метод решения задач о прохождении лабиринта, представленного на рис. 5.1.
Метод Люка состоит в следующем:
1. Из клетки, в которой мы находимся, надо идти по еще не исследованному пути.
2. Если все пути, ведущие из этой клетки, уже исследованы, надо вернуться на один шаг назад по тому пути, которым мы пришли в данную точку.
Итак, вместо порождения всех подмножеств данного множества 
клетки лабиринта) мы рассматриваем лишь подмножества, образующие допустимые пути, и останавливаемся, когда встречаем тупик. Систематизация этого метода привела к появлению наиболее общей схемы решения задач, комбинаторных по природе: речь идет об имплицитном переборе. Наиболее благоприятным случаем перебора является случай, когда мы можем определить градиент.
