Вирішено У чому сенс перебору з поверненням?

Alex Alex · 16 · 1

При чому тут рекурсія, в чому полягає її роль в переборі з поверненням? Вона і змушує алгоритм повертатися на попередні кроки? І що таке перебір з поверненням?

Відповіді на питання

Алгоритмічна рекурсія - це за визначенням алгоритм, побудований зі стратегії Розділяй та володарюй (Divide-and-Conquer), в якому для зберігання підзадач використана LIFO структура даних, тобто, попросту кажучи, стек.

У таких алгоритмів натуральним чином є прямий хід, коли задача розбивається на дрібніші підзадачі, які заносяться в стек. Потім підзадачі витягуються зі стека по одній і вирішуються за таким же принципом, тобто розбиваються на ще дрібніші підзадачі. Розбиття триває до тих пір, поки підзадача не стане розв'язуватися тривіально.

А також у рекурсивних алгоритмів є зворотний хід, коли все дрібніші підзадачі вже вирішені і їх рішення тепер можна об'єднати в рішення більше завдання.

Наявність зворотного ходу (backtracking) - відмінна риса саме рекурсивних алгоритмів. Тобто в рекурсії завжди є зворотний хід. Ось, власне, "при чому тут рекурсія".

Не всім рекурсивним алгоритмам потрібен цей зворотний хід - деяким алгоритмам просто нічого не потрібно робити на зворотному ході. Але сам процес зворотного ходу в рекурсивному алгоритмі завжди присутній, хай навіть і незримо.

Тому якщо ви розглядаєте якийсь рекурсивний алгоритм (перебору або чого-небудь ще), то там завжди обов'язково буде і "повернення" (тобто зворотний хід). А вже як він використовується в вашому алгоритмі та чи використовується взагалі - залежить від алгоритму.

У рекурсивному алгоритмі розставлення N ферзів на шахівниці, підзадачею є завдання розставлення  m ферзів що залишилися (m < = N), коли перші N - m ферзів вже якось розставлені. Зворотний хід в цьому алгоритмі використовується тоді, коли ми раптом з'ясували, що підзадача не має рішення - ми повертаємо цей результат на попередній рівень рекурсії в процесі зворотного ходу і тим самим говоримо йому, що треба спробувати якийсь інший варіант розставлення N - m перших ферзів. А також, якщо вам доручено знайти всі можливі розстановки (а не якусь одну), зворотний хід рекурсії буде використовуватися для тих же цілей незалежно від того,  чи успішно  вирішена підзадача, чи ні.


Для відповіді на запитання необхідно авторизуватись

Війти / Зареєструватися