Міністерство освіти Республіки Білорусь
Установа освіти
"Гомельський державний університет ім.Ф. Скорини "
Математичний факультет
Кафедра МПУ
Курсова робота
Бектрекінг
Виконавець:
Студентка групи М-41
Кравченко О.Ю.
Науковий керівник:
Канд. фіз-мат. наук, доцент
Морозова Т.Є.
Гомель 2005
Зміст
Введення
1. Важливе властивість цього завдання
2. Умова задачі
3. Рішення повним перебором
3. Бектрекінг
Висновок
Література
Введення
Існують завдання для яких немає хорошого методу рішення, відповідь на них не можна отримати обчисленням за формулами. Це як пошук скарбу без карти. Треба все чесно перекопати. Такі завдання називаються завданнями повного перебору або комбінаторними завданнями. Але перебір перебору ворожнечу. Очевидно, що немає сенсу копати скельну породу, можуть бути й інші розумні обмеження на дії шукача скарбів. Тобто всі можливі ситуації можна розділити на два класу: що можуть містити рішення і не може себе утримувати рішення. Звичайно це грубе розбиття, але для нас цього достатньо.
Це дуже проста і зрозуміла ідея не шукати там, де рішення немає, але от в чому проблема, як визначити відсутність поклажі не копаючи?
Приклад 1.
Дано безліч чисел. Скласти з них підмножина таке що сума його елементів буде в точності дорівнює заданому числу А.
Рішенням задачі може виявитися будь-яка множина з N - елементів. А тепер уявіть собі, що в пошуках рішення ви склали така безліч, в ньому N - елементів і в сумі вони дають більше ніж А. Очевидно, що додавання до цього безлічі ще одного елемента тільки погіршить ситуацію. Таким чином, в даній задачі дійсно можна іноді встановити відсутність рішення, що не здійснюючи безпосередніх побудов.
речі давайте оцінимо кількість відсікаються варіантів. Нехай у вихідному множині M елементів і ми для безлічі з N - елементів встановили, що його елементи в сумі дають більше ніж А. Це означає, що MN елементів можуть не брати участі в подальших побудовах. Тобто необхідно відмовитися від додавання до нашого поганого підмножині всіх підмножин побудованих на MN елементах.
Комбінаторика говорить, що з До елементів можна побудувати 2 До множин, отже в нашому випадку ми відкидаємо 2 M- N варіантів. Навіть при не дуже великих числах виграш вийде солідний, тому як експонентна функція має дуже високою швидкістю росту.
Сказане вище вже досить добре описує метод бектрекінга. Полягає він у відсіканні відразу групи варіантів в яких шукати рішення безглуздо. Але нам потрібен чіткий алгоритм, тому продовжимо дослідження.
1. Важлива властивість цього завдання
Всі безліч рішень цього завдання можна вибудувати у вигляді дерева варіантів. Причому для будь-якого рішення (підмножини чисел яке передбачається рішенням) крім мінімального знайдеться рішення з якого його можна побудувати. Нехай наприклад в задачі запропонованої вище дано безліч з трьох чисел А, В, С. Побудуємо два рівні дерева рішень.
В
br/>
Звичайно, дерево для реального завдання буде більш гіллясте і більш глибоке, але це вже технічні деталі. Істотно важливо те, що в цьому дереві якщо його побудувати до кінця будуть присутні всі комбінації даних (варіанти) серед яких можливо шукати рішення, а рішення задачі це комбінація даних з деякими заданими властивостями. Завдання такого типу зустрічаються досить часто. Гарантовано їх рішення знаходиться повним перебору або, що те ж саме повним обходом дерева.
Обхід усіх гілок можна здійснити, наприклад, за правилом правої або лівої руки. Це правило визначає гілку, по якій потрібно йти на черговому кроці пошуку. Сформулюємо правило. p> Нехай на деякому кроці роботи алгоритму ми знаходимося в деякої вершині дерева і необхідно прийняти рішення про те по якій гілці йти далі. Врахуємо, що з кожної вершини довільну кількість гілок йде вниз і тільки одна наверх. Можливі такі ситуації:
Усі гілки йдуть вниз вже пройдені. Фізично це може визначаться небудь позначкою встановлюваної на гілки в тому разі якщо за ній здійснюється повернення. Тоді необхідно йти по гілки йде вгору і помітити її як пройдену.
Серед гілок провідних вниз їсти не пройдені. Знайдемо серед них саму ліву і підемо по ній.
Сформульоване правило ніяк не враховує події відбуваються в вершинах дерева. Тим часом вершина від вершини може відрізнятися і не тільки положенням в дереві. Наприклад, у розглянутій вище задачі при переході вниз наростає сума, а при переході вгору та сума зменшується. ...
