4. Переборные задачи
 

Методы перебора применяются при решении многих задач. Суть переборной задачи заключается в том, что необходимо найти на конечном множестве X элемент х, удовлетворяющий совокупности условий К(х), в предположении, что пространство поиска X содержит некоторое конечное число различных точек.

1. Алгоритм решения переборной задачи можно представить в следующем виде: Взять из множества X еще не рассмотренный элемент X₀.
2. Проверить совокупность условий К(х₀).
3. Если какое-либо условие не выполнено, то перейти к п.1.
4. Если выполнены все условия, то х₀ является решением задачи. Если же возможно несколько решений и требуется найти все их, то вернуться к п.1, пока не будут перебраны все элементы множества X.

Сложность алгоритма будет определяться во многом тем, как представлены элементы, в каком порядке их перебирать, в чем заключается проверка условий K(X₀) И сколько элементов нужно найти.

Рассмотрим задачу поиска элемента с заданным значением в двухмерном массиве, элементами которого являются значения скалярного типа. Для выборки элемента достаточно задать его индексы, организовав вложенные циклы. Обработка элемента сводится к сравнению его значения с заданным числом. При их равенстве поиск прекращается, результатом являются индексы найденного элемента. При неудачном поиске, когда элемента с заданным значением нет в массиве, перебираются все элементы; поиск прекращается после обработки последнего элемента. Результатом является возврат некоторого признака «элемент не найден». Поиск в массиве, упорядоченном по возрастанию значений элементов, несколько упрощается. Если искомого элемента нет, то поиск прекращается тогда, когда заданное значение элемента будет меньше значения выбранного элемента.

В этой задаче множество X включает все n элементов массива, условием К(х) является проверка на равенство значения выбранного элемента и заданного значения. Обработка одного элемента никак не связана со значениями других элементов массива. Поэтому сложность алгоритма равна О(n).

В задаче поиска наибольшего или наименьшего элемента массива приходится перебирать все элементы, результат поиска зависит от соотношения значений всех элементов. Более сложной является задача поиска минимального элемента среди максимальных элементов строк массива или задача поиска седловой точки, когда минимальный элемент в строке одновременно является максимальным элементом в столбце массива.

Задачи подобного типа решаются применением циклов, и их программирование особых затруднений не вызывает. Такие задачи обычно не относят к переборным задачам. Задача усложняется, когда элементами множества X являются некоторые последовательности. Такие задачи можно решить методом перебора.

В теории перебора используются два фундаментальных понятия: номер хода i и номер варианта j. Для каждого хода i перебираются варианты j, пока не будет найдено «подходящее решение». Особенности решения конкретной задачи перебора вариантов определяются этим «подходящим решением» (совокупностью условий К(х)). Им может быть первое найденное решение; все возможные решения; оптимальное среди всех возможных решений т.д. В любом случае задача должна быть решена, если не за минимально возможное время, то по крайней мере за приемлемое для данной задачи.