Подразделы

Другие разделы

Дата и время

12/03/2025 22:14:43

Авторизация

Зарегистрироваться
Восстановить пароль

Классы сложности задач. Методы решения трудных задач

Классы сложности задач Сравнение методов решения трудных задач Метод поиска с возвратом Метод ветвей и границ

Метод поиска с возвратом

Задача о ферзях

Задача заключается в размещении $n$ ферзей на шахматной доске размером $n x n$ так, чтобы никакие два ферзя не угрожали друг другу, находясь на одной горизонтали, вертикали или диагонали. Для $n = 1$ задача имеет тривиальное решение; легко убедиться, что для $n = 2$ и $n = 3$ решений не существует.

float:right;width:150px|задача Решим задачу для $n=4$ с помощью поиска с возвратом. Поскольку каждый ферзь должен находиться на собственной горизонтали, все, что надо, — это указать вертикаль для каждого ферзя на доске.

Начинаем с пустой доски и помещаем ферзя 1 в первую возможную позицию на его горизонтали; это позиция на вертикали 1. Затем мы размещаем ферзя 2 в первую допустимую позицию (после неудачных попыток размещения на вертикалях 1 и 2) на вертикали 3, в квадрате (2,3). Это тупиковая позиция, поскольку при ней оказывается невозможно разместить третьего ферзя так, чтобы он не был под боем. Соответственно, алгоритм осуществляет возврат к предыдущему состоянию и помещает ферзя в позицию (2,4). После этого третий ферзь может быть помещен только в позицию (3,2), что приводит к очередному тупику После этого алгоритм осуществляет возврат к ферзю 1 и помещает его в очередной допустимой позиции (1,2). Ферзь 2 может быть размещен только в позиции (2,4), ферзь 3 — только в позиции (3,1), а ферзь 4 — в позиции (4,3), что дает решение поставленной задачи.

width:500px|дерево

Задача о гамильтоновом цикле

Без потери общности можно считать, что если гамильтонов цикл существует, то он начинается в вершине $a$ . Соответственно, мы делаем вершину $a$ корнем дерева пространства состояний. Используя алфавитный порядок для разрешения неоднозначности при выборе вершин, смежных с вершиной $a$ , мы выбираем вершину $b$ . После вершины $b$ алгоритм обращается к вершинам $c$ , $d$ , $e$ и, наконец, к $f$ , которая является тупиком. Соответственно алгоритм возвращается к вершине $c$ — первой вершине, которая позволяет получить отличное от рассмотренного решение. Переход от $c$ к $e$ не приводит к решению, и алгоритм должен вернуться к вершине $b$ . Из вершины $b$ мы попадаем в вершину $f$ , а за ней — в вершины $e$ , $c$ и $d$ , из которой можно вполне законным путем вернуться в $a$ , что дает гамильтонов цикл $a-b-f-e-c-d-a$ . Если мы хотим найти еще какой-то гамильтонов цикл, то можем продолжить процесс возврата из листа, соответствующего найденному решению.

width:600px|дерево

Задача о подмножестве с заданной суммой

Требуется найти подмножество данного множества $S = {s_1,...,s_n}$ , состоящего из $n$ натуральных чисел, такое, что сумма его элементов равна заданному натуральному числу $d$ . Например, для $S = {1,2,5,6,8}$ и $d = 9$ имеется два решения — {1,2,6} и {1,8}.

Удобно отсортировать элементы множества в возрастающем порядке. Будем считать, что $s_1<=s_2<=...<=s_n$ .

Дерево пространства состояний может быть построено как бинарное дерево. Корень дерева представляет начальную точку, в которой не принято решение ни по одному из элементов множества. Его левый и правый дочерние узлы представляют, соответственно, включение $s_1$ в искомое подмножество и отсутствие в нем этого элемента. Аналогично, переход влево от узла на первом уровне означает включение $s_2$ в искомое подмножество, а переход вправо — отсутствие этого элемента в искомом множестве. Таким образом, путь от корня к узлу на $i$ -ом уровне дерева указывает, какие из первых $i$ чисел будут включены в подмножество, представленное этим узлом.

width:550px|дерево

Полное дерево пространства состояний (для поиска всех решений).

Запишем значение $r$ суммы этих чисел, в узле. Если $r$ равно $d$ , мы получаем решение поставленной задачи. Мы можем либо сообщить о нем и прекратить работу алгоритма, либо, если надо найти все решения, выполнить очередной возврат к родительскому узлу и продолжить работу. Если $r$ не равно $d$ , мы можем завершить работу с узлом как с бесперспективным при выполнении любого из двух условий:

$r+s_{i+1}>d$ (сумма слишком велика)

$r + sum_{j=i+1}^n s_j < d$ (сумма слишком мала)

Поиск с возратом применяется для сложных комбинаторных задач, для точного решения которых не существует эффективных алгоритмов.

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

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

Задания для практики

а) Примените поиск с возвратом для решения следующего экземпляра задачи о сумме подмножества: $S ={1,3,4,5}$ и $d = 11$ .
б) Будет ли алгоритм поиска с возвратом корректно работать при использовании только одного из двух неравенств для завершения обработки узла как бесперспективного?
Получить все представления натурального числа $N=10$ суммой натуральных чисел. Перестановка слагаемых нового способа представления не даёт.

Назад