Зображення даних в оперативній пам’яті [2]

Розв’язання задачі перебору з поверненням можна представити в оперативній пам’яті комп’ютера у вигляді дерева пошуку. Корінь дерева (0 рівень) є пустий вектор. Його сини являються множиною кандидатів для вибору , і , в загальному випадку, вузли -того рівня являються кандидатами на вибір при умові, що вибрали так, як вказують предки цих вузлів. Питання про те, чи має задача розв’язок, рівносильне питанню, являється які-небудь вузли дерева розв’язками. Шукаючи всі розв’язки, ми хочемо одержати всі такі вузли.

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

Опис алгоритму програмного модуля [2]

Розв’язання задачі можливо продемонструвати за допомогою рекурсивної схеми реалізації алгоритму:

void Backtrack (< вектор , >) // - розмірність вектора

{

if (< вектор є розв’язком >)

< записати його >;

else

{

< обчислити >;

for (int k=0; k<n; n++) // n – кількість елементів в

Backtrack (< вектор , +1 >); //маючи

// додавання до вектора елементів

}

}

При виконанні такої функції будуть знайдені всі розв’язки задачі.

Оцінка складності алгоритму [2]

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

Опис програми Методи та засоби розробки програми

Прикладні задачі даної розрахунково-графічної роботи реалізовані за допомогою високорівневої мови програмування C++ в середовищі Microsoft Visual Studio 2008. Кожна прикладна задача була виконано в новому проекті та виконується окремим exe-файлом. Графічне меню розрахунково-графічної роботи, з якого користувач може вибрати реалізацію прикладної задачі, було зроблено за допомогою мови гіпертекстової розмітки HTML та каскадних таблиць стилів CSS в середовищі Adobe Dreamweaver CS5.

Сценарій роботи програми

1. Користувач знаходиться в головному меню програми, зробленого за допомогою HTML. Йому доступні такі пункти меню:

• Теоретичні відомості (опис роботи алгоритму перебору з поверненням та його застосування)

• Прикладні задачі (список виконаних прикладних задач за даним алгоритмом)

• Відомості про виконавця.

2. При виборі пункту «Теоретичні відомості», користувачу буде доступна інформація з наглядним описом роботи алгоритму і його використання в прикладних задачах.

3. При виборі певної задачі з пункту «Прикладні задачі», користувачеві буде доступна її умова, опис роботи програми, спосіб її реалізації, код програми з коментарями, тести(вхідні та вихідні дані) та можливість її запустити й перевірити правильність виконання.

4. При виборі пункту «Відомості про виконавця» користувачу буде доступна інформація про виконавця даної розрахунково-графічної роботи та список використаної літератури.