- •Зміст пояснювальної записки
- •Постановка задачі Організаційно-інформаційна сутність задачі [1]
- •Математична модель задачі [1]
- •Опис методів розв’язання задачі Метод перебору з поверненням [2]
- •Алгоритм перебору з поверненням
- •Зображення даних в оперативній пам’яті [2]
- •Опис алгоритму програмного модуля [2]
- •Оцінка складності алгоритму [2]
- •Опис програми Методи та засоби розробки програми
- •Сценарій роботи програми
- •Функціональна структура програми Специфікація модулів
- •Специфікація функцій
- •Технологія створення програми
- •Алгоритм програми
- •Опис алгоритму методу
- •Алгоритм програми
- •Вхідні та вихідні тести
- •Опис алгоритму методу
- •Алгоритм програми
- •Опис алгоритму методу
- •Алгоритм програми
- •Вхідні та вихідні тести
- •Опис алгоритму методу
- •Алгоритм програми
- •Вхідні та вихідні тести
- •Опис алгоритму методу
- •Алгоритм програми
- •Висновок.
- •Список використаної літератури.
- •Додаток 1 cd та опис його змісту
Математична модель задачі [1]
Опишемо загальну постановку класу задач, до яких застосовують алгоритм перебору з поверненням.
Нехай – скінченних лінійно впорядкованих множин і - сукупність обмежень (умов), що ставлять у відповідність векторам виду ( булеве значення (вираз, який для кожної множини аргументів ставить у відповідність значення «істина», або «хибність»). Вектори , для яких , назвемо частковим розв’язком. Нехай, надалі, існує конкретне правило , в відповідності з яким деякі з часткових розв’язків можуть вважатися повними розв’язками. Тоді можлива постановка наступних пошукових задач:
Знайти всі повні розв’язки або з’ясувати відсутність їх.
Знайти хоча б один повний розв’язок або встановити його відсутність.
Загальний метод розв’язку приведених задач складається з послідовного по компонентного нарощування вектору зліва направо, починаючи з , і послідовних перевірок його обмеженнями і правилом
Вхідні дані
Для задач, що розв’язуються алгоритмом перебору з повернення умову можна виразити за допомогою:
скінченні набори значень , з елементів яких буде формуватися шуканий розв’язок задачі;
-місний предикат , за допомогою якого перевіряється чи є вектор частковим розв’язком;
умова , при виконанні якої, знайдений частковий розв’язок у вигляді вектору буде являти собою повний розв’язок.
Вихідні дані
На виході роботи алгоритму, в залежності від поставленої задачі ми можемо отримати:
вектор який є розв’язком даної задачі;
сукупність всіх векторів , що є розв’язками даної задачі;
один, або сукупність з всіх знайдених розв’язків задачі , для якого виконується спеціальна умова, що вказана в формулюванні задачі;
відсутність розв’язку.
Опис методів розв’язання задачі Метод перебору з поверненням [2]
Дано впорядкованих множин ( – задано ), і необхідно побудувати вектор , де , , … , , задовольняють даній множині умов та обмежень.
В алгоритмі перебору з поверненням вектор будується поелементно зліва направо. Припустимо, що вже знайдені значення перших елементів, тоді задана множина умов обмежує вибір наступного елементу деякою множиною . Якщо (не порожнє), маємо право вибрати в якості найменший елемент і перейти до вибору елемента і так далі. Проте, якщо умови такі, що виявилося порожнім, то повертаємося до вибору елемента, відкидаємо і обираємо в якості нового той елемент , який безпосередньо слідує за тільки що відкинутим. Може виявитися, що для нового умови задачі допускають не порожнє , і тоді намагаємося знову вибрати елемент . Якщо неможливо вибрати , повертаємося ще на крок назад і вибираємо новий елемент і так далі.
Нижче на рис.1 зображена схема роботи алгоритму перебору з поверненням:
Рис.1 Схема роботи алгоритму перебору з поверненням
Алгоритм перебору з поверненням
Даний частковий розв’язок – порожній вектор (довжиною 0).
Обчислити множину - допустимі значення для наступного елемента .
Якщо (не порожнє), вибрати в якості найменший елемент і перейти до пункту 5, інакше перейти до пункту 4.
Відкинути з вектору часткового розв’язку і обрати в якості нового той елемент , який безпосередньо слідує за тільки що відкинутим та переходимо до пункту 2.
Якщо даний вектор є розв’язком , то записати його і кінець алгоритму, інакше перейти до пункту 2.