- •Зміст пояснювальної записки
- •Постановка задачі Організаційно-інформаційна сутність задачі [1]
- •Математична модель задачі [1]
- •Опис методів розв’язання задачі Метод гілок та границь
- •Алгоритм гілок і границь [1]
- •Зображення даних в оперативній пам’яті [2]
- •Опис алгоритму програмного модуля [2]
- •Оцінка складності алгоритму
- •Метод решета [2]
- •Алгоритм решета [2]
- •Зображення даних в оперативній пам’яті [2]
- •Опис алгоритму програмного модуля [2]
- •Оцінка складності алгоритму
- •Опис програми Методи та засоби розробки програми
- •Сценарій роботи програми
- •Функціональна структура програми Специфікація модулів
- •Специфікація функцій
- •Технологія створення програми
- •Опис алгоритму методу[2]
- •Алгоритм програми
- •Вхідні та вихідні тести
- •Опис алгоритму методу
- •Алгоритм програми
- •Опис алгоритму методу
- •Алгоритм програми
- •Висновок.
- •Список використаної літератури.
- •Додаток 1 cd та опис його змісту
Алгоритм гілок і границь [1]
Першим кроком є обов’язково розбиття початкової множини допустимих розв’язків на підмножини так, щоб потім для кожної підмножини визначити оцінку найліпшого можливого результату або знайти точно найліпший для цієї підмножини розв’язок . Якщо для якоїсь -ї підмножини вдалося знайти точний розв’язок, визначаємо міру його оптимальності функцією . Якщо таких розв’язків кілька, вибираємо(тимчасово) той з них, що має найліпшу . Усі множини, що мають оцінку , гіршу за тимчасову , відкидають з подальшого розгляду.
Наступні кроки повторюють доти, доки є не відкинуті підмножини з незнайденими на них точними найліпшими розв’язками. Кожен з кроків полягає у наступному.
Вибираючи підмножину з найліпшою оцінкою і розбивають на підмножини . Над цими підмножинами виконують усі ті дії, що виконували над множинами на першому кроці, тобто знаходять нові оцінки або точні розв’язки . Якщо якийсь із цих розв’язків виявиться ліпшим за , то цей розв’язок стає «тимчасово» оптимальним, і слід відкинути усі підмножини, чия оцінка гірша за нове значення .
Розв’язком буде останнє знайдене значення , після досягнення умови припинення пошуку( тобто знайдуть точні найліпші розв’язки на всіх невідкинутих підмножинах)
Зображення даних в оперативній пам’яті [2]
Розв’язання задачі методом гілок та границь можна представити в оперативній пам’яті комп’ютера у вигляді дерева пошуку. Корінь дерева (0 рівень) є початкова множина . Його сини являються множинами кандидатів для вибору , і , в загальному випадку, вузли -того рівня являються кандидатами на вибір при умові, що вибрали так, як вказують предки цих вузлів. Шукаючи розв’язки, ми хочемо одержати всі такі вузли, відкидаючи з подальшого розгляду вузли множин з гіршою оцінкою.
Інколи немає необхідності зберігати все дерево. В цих випадках можна обійтися масивом, або чергою, тільки для зберігання поточного часткового розв’язку.
Опис алгоритму програмного модуля [2]
Розв’язання задачі можливо продемонструвати за допомогою рекурсивної схеми реалізації алгоритму:
void Bound (< вектор , >) // - розмірність вектора
{
< Знайти частковий розв’язок>
< Розбити множину по ньому >;
<Заповнити ліве піддерево >;
<Заповнити праве піддерево >;
<Оцінити нижні границі піддерев >;
if(<якщо границя лівого піддерева менша мінімальної оцінки> )
{
Bound(<ліве піддерево>); // запустити гілкування лівого дерева
}
if(<якщо границя правого піддерева менша мінімальної оцінки> )
{
Bound(<праве піддерево>); // запустити гілкування правого дерева
}
}
При виконанні даної функції будуть знайдені всі оптимальні розв’язки задачі.
Оцінка складності алгоритму
Оцінимо часову складність алгоритму. Дана схема реалізації методу гілок та границь дозволяє значно скоротити час розрахунків, але в часткових випадках може працювати як повний перебір, часова складність якого дорівнює
Метод решета [2]
Метод решета є одним з небагатьох загальних методів, що дозволяють вирішувати різноманітні завдання теорії чисел . Найдавніший з відомих методів решета належить Ератосфену. Цей метод пошуку отримав назву "Решето Ератосфена", на честь давньогрецького математика Ератосфена Киренського. А "решето" тому, що ми як би просіваємо масив чисел, залишаючи в ньому тільки прості числа.
Якщо потрібно знайти всі прості числа менші за певне число , виписуються всі числа від . Потім в цьому ряду викреслюються всі числа, які діляться на і так далі до . Числа, які залишилися невикресленими після цієї процедури – прості, тобто є кратними самому собі та одиниці.