Вопросы

Набор для практики

Краткие итоги

Ключевые термины

Возвратная рекурсия – это соединение метода перебора с возвратом и рекурсии.

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

Исчерпывающий поиск – это процесс нахождения в некотором множестве всех возможных вариантов, среди которых имеется решение конкретной задачи.

Метод решета – это один из методов организации исчерпывающего поиска, при котором из множества возможных вариантов исключаются все элементы, не являющиеся решениями.

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

Перебор с возвратом (backtracking)– это один из методов организации исчерпывающего поиска, который строится конструктивно последовательным расширением частичного решения.

Полное решение – это набор вариантов, образующий хотя бы одно решение в целом.

Частичное решение – это неполный набор вариантов, который входит в одно или несколько полных решений.

1.Решение переборных задач сводится к определению наличия решения, всех различных вариантов решения или к нахождению одного решения.

2.В зависимости от постановки задачи переборные алгоритмы реализуются методами перебора с возвратом или методом решета.

3.Возвратная рекурсия – это соединение метода перебора с возвратом и рекурсии.

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

5.Для решения задачи о расстановке ферзей на шахматной доске как альтернативный используется метод возвратной рекурсии.

6.При разработке триады для решения задачи о расстановке ферзей вводятся дополнительные параметры при описании процесса расстановки.

7.Базой в данной задаче считается совокупность всех тупиковых ситуаций.

8.Декомпозиция проводится от частичного к полному решению или к снятию ферзя с вертикали (возврат).

1. В чем проявляется рекурсивность метода перебора с возвратом?

2. Почему полный метод перебора с возвратом гарантирует отыскание всех решений задачи?

3. Как формируется рекурсивная база метода возвратной рекурсии?

4. Какие классы задач сводятся к разработке детерминированных алгоритмов, а какие – к недетерминированным? Поясните примерами.

5. Поясните, почему данные описания характеризуют описание действий над ферзем в контексте модели шахматной доски:

a. В позицию можно поставить ферзь, если .

b. Поставить ферзь в позицию равносильно присваиваниям: , , .

c. Убрать ферзь из позиции равносильно присваиваниям: , , .