13.6 Упражнения¶
13.6.1 Вопросы для самопроверки¶
1. Пропустит ли этот алгоритм некоторые перестановки¶
Алгоритм поиска с возвратом пытается построить все перестановки, перебирая числа в порядке 1, 2, 3. Выбрав число x, он:
- добавляет
xв конец текущего пути; - помечает
xкак «использованное»; - рекурсивно заполняет следующую позицию.
После возврата из рекурсии ученик удалил x только из конца пути и перешел к следующему числу.
- Какую перестановку алгоритм получит первой? Сможет ли он получить все 6 перестановок?
- Достаточно ли перед возвратом на предыдущий уровень удалить число из конца пути? Если нет, что еще нужно сделать и почему?
Ответ
-
Первой получится перестановка
[1, 2, 3], но алгоритм не сможет получить все перестановки. Хотя после возврата путь становится короче, числа 1, 2 и 3 по-прежнему помечены как «использованные», поэтому в последующих ветвях не останется доступных чисел. -
Нет. После удаления
xиз конца пути нужно также снова пометитьxкак «неиспользованное». Текущий путь и отметки «использовано» вместе описывают состояние поиска. При выборе изменяются обе части состояния, поэтому при возврате нужно восстановить обе, чтобы другие ветви могли снова выбратьx.
2. Важен ли порядок выбора чисел¶
Дан упорядоченный массив [2, 3, 5] и целевое значение 5. Каждое число разрешено выбирать повторно.
Алгоритм требует, чтобы числа в каждом пути поиска располагались только в неубывающем порядке.
- Какие различные комбинации можно получить?
- Почему один и тот же набор чисел не нужно повторно перебирать в разном порядке? Какую роль играет ограничение «по неубыванию»?
- Текущий путь равен
[3], до цели не хватает 2, а следующий возможный элемент равен 3. Почему теперь можно прекратить проверку всех следующих элементов на этом уровне?
Ответ
-
Различные комбинации:
[2, 3]и[5]. -
В этой задаче
[2, 3]и[3, 2]считаются одной комбинацией: порядок выбора чисел не влияет на ответ. Требование располагать числа в пути по неубыванию позволяет сразу исключить из поиска повторные комбинации наподобие[3, 2]. -
До цели осталось 2, а возможный элемент 3 уже больше 2. Поскольку массив упорядочен, все последующие элементы будут еще больше и также не смогут войти в текущую комбинацию. Поэтому проверку этого уровня можно сразу завершить.
3. Куда можно поставить следующего ферзя¶
Ферзи расставляются по строкам на доске 4 × 4; индексы строк и столбцов начинаются с 0.
Ферзи уже стоят на позициях (0, 1) и (1, 3). Следующего ферзя нужно поставить в строке 2.
- Какие столбцы исключаются из-за того, что в них уже есть ферзь?
- Какие из оставшихся позиций исключаются из-за расположения на одной диагонали с другим ферзем?
- Какие позиции в строке 2 еще можно попробовать?
Ответ
-
В столбцах 1 и 3 уже стоят ферзи, поэтому позиции
(2, 1)и(2, 3)исключаются. -
Среди оставшихся позиций
(2, 2)находится на одной диагонали с(1, 3), поэтому ее также нужно исключить. Позиция(2, 0)не совпадает по столбцу ни с одним из уже поставленных ферзей и не лежит с ними на одной диагонали. -
В строке 2 можно попробовать только позицию
(2, 0).Этот шаг показывает лишь, что текущее расположение допустимо. Если завершить доску затем не удастся, потребуется вернуться и попробовать другие, более ранние варианты.
13.6.2 Задачи по программированию¶
1. Все перестановки различных элементов¶
Массив целых чисел nums содержит хотя бы один элемент, и все его элементы попарно различны.
Перечислите все возможные порядки, в которых каждый элемент используется ровно один раз, и верните каждый порядок как отдельный массив.
Порядок самих перестановок в результате не имеет значения.
Используйте поиск с возвратом и булев массив, отмечающий, выбран ли элемент из каждой позиции входного массива в текущую перестановку.
Подсказки
- Глубина рекурсии показывает, какую по счету позицию перестановки нужно заполнить
- На каждом уровне пробуйте только еще не использованные элементы
- Когда длина пути станет равна длине
nums, добавьте в ответ копию пути