Алгоритмические стратегии
Поиск с возвратом (backtracking)
Алгоритмы полного перебора
Найти на конечном множестве X элемент x, удовлетворяющий совокупности условий K(x). Алгоритм: 1. Взять из множества X еще не рассмотренный элемент и проверить совокупность условие K(x). 2. Если какое-либо условие не выполнено, то перейти к п.1. 3. Если выполнены все условия, то x является решением. Если возможно несколько решений и требуется найти все их, то вернуться к п.1, пока не будут перебраны все элементы из множества X.
Пример 1.
Поиск элемента A в массиве A1,A2,…,An. В наихудшем случае (элемента в массиве нет или он находится на последнем месте) необходимо выполнить n сравнений T(n)=c*n, с – время одного сравнения. В среднем Tср(n) ~ c*n/2. В лучшем случае достаточно произвести только одно сравнение, когда элемент находится в начале массива. Таким образом, число операций сравнения в наихудшем случае растет линейно в зависимости от n.
Пример 2.
Подсчитать число счастливых билетов, если номера билетов заданы к-значными (k четное целое десятичное число) десятичными числами. М – число всех возможных вариантов, N – число счастливых билетов. k = 2, N = 10, M = 100 k = 4, N = 670, M = 10 000 k = 6, N = 55252, M = 1 000 000 k = 8, N = 4816030, M = 100 000 000 ………………………………………………………….. Получаем «комбинаторный взрыв», т.е. количество возможных вариантов, из которых нужно выбрать требуемые, растет очень быстро с ростом размерности задачи (k).
Поиск с возвратом
Многие задачи трудно решить полным перебором даже на очень мощных компьютерах. В то же время многие из них настолько важны, что мы не можем просто оставить все как есть и ничего не предпринимать. Поиск с возвратом зачастую делает возможным решение как минимум некоторых больших экземпляров комбинаторных задач. Эту стратегию можно рассматривать как усовершенствование исчерпывающего перебора.
Поиск с возвратом
В отличие от исчерпывающего перебора здесь решение строят по одному компоненту и оценивают частично построенные решения: если потенциальных значений оставшихся компонент, которые могли привести к корректному решению, не имеется, то оставшиеся компоненты решения не генерируются. Такой подход делает возможным решение некоторых больших экземпляров сложных комбинаторных задач, хотя в наихудшем случае мы все равно сталкиваемся с экспоненциальным ростом, присушим исчерпывающему перебору.
Поиск с возвратом
Метод основан на построении дерева пространства состояний (state-space tree), узлы которого отражают конкретные выборы, сделанные для компонентов решения. Метод останавливается в узле, если можно гарантировать, что невозможно получить решение, рассматривая решения, соответствующие потомкам данного узла. Его корень представляет начальное состояние перед началом поиска. Узлы на первом уровне дерева представляют варианты выбора, сделанные для первого компонента решения, узлы на втором уровне – варианты выбора второго компонента и т.д.
Поиск с возвратом
Узел дерева пространства состояний называется обещающим, если он соответствует частично построенному решению, которое может привести к полному решению; в противном случае он называется бесперспективным. Листья представляют собой либо бесперспективные тупики, либо полные решения, найденные алгоритмом. В большинстве случаев дерево пространства состояний для алгоритма поиска с возвратом строится способом поиска в глубину.
Поиск с возвратом
Пример 1. Задача о сумме подмножеств. Требуется найти подмножество данного множества, состоящего из n натуральных чисел, такое, что сумма его элементов равна заданному натуральному числу d. Само собой, некоторые экземпляры данной задачи могут не иметь решений. Удобно отсортировать элементы множества в возрастающем порядке. Здесь используется прием, который позволяет снизить размер дерева пространства состояний – перегруппировка данных экземпляра задачи. Еще одна возможность воспользоваться часто присущей комбинаторным задачам симметрией.
Поиск с возвратом
Поиск с возвратом
Пример 3. Задача о n ферзях. Задача заключается в размещении n ферзей на шахматной доске размером n*n так, чтобы никакие два ферзя не угрожали друг другу, находясь на одной горизонтали, вертикали или диагонали. Для n = 1 задача имеет тривиальное решение; легко убедиться, что для n = 2 и n = 3 решений не существует.
Поиск с возвратом
Поиск с возвратом не всегда может быть эффективным. В наихудшем случае ему может потребоваться сгенерировать всех возможных кандидатов из экспоненциально (или еще быстрее) растущего пространства состояний решаемой задачи. Надежда остается на то, что алгоритм поиска с возвратом будет способен обрезать достаточное количество ветвей дерева пространства решений до того, как исчерпается отведенное ему время или память (или и то, и другое). Успешность этой стратегии колеблется в очень широких пределах, и не только от задачи к задаче, но и между экземплярами одной и той же задачи
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.
