Математична модель задачі [1]

Опишемо загальну постановку класу задач, до яких застосовують алгоритм перебору з поверненням.

Нехай – скінченних лінійно впорядкованих множин і - сукупність обмежень (умов), що ставлять у відповідність векторам виду ( булеве значення (вираз, який для кожної множини аргументів ставить у відповідність значення «істина», або «хибність»). Вектори , для яких , назвемо частковим розв’язком. Нехай, надалі, існує конкретне правило , в відповідності з яким деякі з часткових розв’язків можуть вважатися повними розв’язками. Тоді можлива постановка наступних пошукових задач:

• Знайти всі повні розв’язки або з’ясувати відсутність їх.

• Знайти хоча б один повний розв’язок або встановити його відсутність.

Загальний метод розв’язку приведених задач складається з послідовного по компонентного нарощування вектору зліва направо, починаючи з , і послідовних перевірок його обмеженнями і правилом

Вхідні дані

Для задач, що розв’язуються алгоритмом перебору з повернення умову можна виразити за допомогою:

• скінченні набори значень , з елементів яких буде формуватися шуканий розв’язок задачі;

• -місний предикат , за допомогою якого перевіряється чи є вектор частковим розв’язком;

• умова , при виконанні якої, знайдений частковий розв’язок у вигляді вектору буде являти собою повний розв’язок.

Вихідні дані

На виході роботи алгоритму, в залежності від поставленої задачі ми можемо отримати:

• вектор який є розв’язком даної задачі;

• сукупність всіх векторів , що є розв’язками даної задачі;

• один, або сукупність з всіх знайдених розв’язків задачі , для якого виконується спеціальна умова, що вказана в формулюванні задачі;

• відсутність розв’язку.

Опис методів розв’язання задачі Метод перебору з поверненням [2]

Дано впорядкованих множин ( – задано ), і необхідно побудувати вектор , де , , … , , задовольняють даній множині умов та обмежень.

В алгоритмі перебору з поверненням вектор будується поелементно зліва направо. Припустимо, що вже знайдені значення перших елементів, тоді задана множина умов обмежує вибір наступного елементу деякою множиною . Якщо (не порожнє), маємо право вибрати в якості найменший елемент і перейти до вибору елемента і так далі. Проте, якщо умови такі, що виявилося порожнім, то повертаємося до вибору елемента, відкидаємо і обираємо в якості нового той елемент , який безпосередньо слідує за тільки що відкинутим. Може виявитися, що для нового умови задачі допускають не порожнє , і тоді намагаємося знову вибрати елемент . Якщо неможливо вибрати , повертаємося ще на крок назад і вибираємо новий елемент і так далі.

Нижче на рис.1 зображена схема роботи алгоритму перебору з поверненням:

Рис.1 Схема роботи алгоритму перебору з поверненням

Алгоритм перебору з поверненням

1. Даний частковий розв’язок – порожній вектор (довжиною 0).

2. Обчислити множину - допустимі значення для наступного елемента .

3. Якщо (не порожнє), вибрати в якості найменший елемент і перейти до пункту 5, інакше перейти до пункту 4.

4. Відкинути з вектору часткового розв’язку і обрати в якості нового той елемент , який безпосередньо слідує за тільки що відкинутим та переходимо до пункту 2.

5. Якщо даний вектор є розв’язком , то записати його і кінець алгоритму, інакше перейти до пункту 2.