Механізм бектрекінга

[ виправити ] текст може містити помилки, будь ласка перевіряйте перш ніж використовувати.

скачати

Міністерство освіти Республіки Білорусь
Установа освіти
"Гомельський державний університет ім.Ф. Скорини"
Математичний факультет
Кафедра МПУ
Курсова робота
Бектрекінг
Виконавець:
Студентка групи М-41
Кравченко О.Ю.
Науковий керівник:
Канд. фіз-мат. наук, доцент
Морозова Т.Є.
Гомель 2005

Зміст
Введення
1. Важлива властивість цього завдання
2. Умова задачі
3. Рішення повним перебором
3. Бектрекінг
Висновок
Література

Введення

Існують задачі для яких немає хорошого методу рішення, відповідь на них не можна отримати обчисленням за формулами. Це як пошук скарбу без карти. Треба все чесно перекопати. Такі завдання називаються завданнями повного перебору або комбінаторними завданнями. Але перебір перебору ворожнечу. Очевидно, що немає сенсу копати скельну породу, можуть бути й інші розумні обмеження на дії шукача скарбів. Тобто всі можливі ситуації можна розділити на два класи: що можуть містити рішення і не може себе утримувати рішення. Звичайно це грубе розбиття, але для нас цього достатньо.
Це дуже проста і зрозуміла ідея не шукати там, де рішення немає, але от в чому проблема, як визначити відсутність скарбу не копаючи?
Приклад 1.
Дано безліч чисел. Скласти з них підмножина таке що сума його елементів буде в точності дорівнює заданому числу А.
Рішенням завдання може виявитися будь-яка множина з N - елементів. А тепер уявіть собі, що в пошуках рішення ви склали така безліч, в ньому N - елементів і в сумі вони дають більше ніж А. Очевидно, що додавання до цього безлічі ще одного елемента тільки погіршить ситуацію. Таким чином, в даній задачі дійсно можна іноді встановити відсутність рішення, не здійснюючи безпосередніх побудов.
До речі давайте оцінимо кількість відсікаються варіантів. Нехай у вихідному множині M елементів і ми для безлічі з N - елементів встановили, що його елементи в сумі дають більше ніж А. Це означає, що MN елементів можуть не брати участь в подальших побудовах. Тобто необхідно відмовитися від додавання до нашого поганого підмножині всіх підмножин побудованих на MN елементах.
Комбінаторика говорить, що з К елементів можна побудувати 2 До множин, отже в нашому випадку ми відкидаємо 2 M-N варіантів. Навіть при не дуже великих числах виграш вийде солідний, тому як експонентна функція володіє дуже високою швидкістю росту.
Сказане вище вже досить добре описує метод бектрекінга. Полягає він у відсіканні відразу групи варіантів в яких шукати рішення безглуздо. Але нам потрібен чіткий алгоритм, тому продовжимо дослідження.

1. Важлива властивість цього завдання

Всі безліч рішень цього завдання можна вибудувати у вигляді дерева варіантів. Причому для будь-якого рішення (підмножини чисел яке передбачається рішенням) крім мінімального знайдеться рішення з якого його можна побудувати. Нехай наприклад в задачі запропонованої вище дано багато з трьох чисел А, В, С. Побудуємо два рівні дерева рішень.
Початок
А
У
З
АВ
АС
ВА
НД
СА
СВ


Звичайно, дерево для реального завдання буде більш гіллясте і більш глибоке, але це вже технічні деталі. Істотно важливо те, що в цьому дереві якщо його побудувати до кінця будуть присутні всі комбінації даних (варіанти) серед яких можливо шукати рішення, а рішення задачі це комбінація даних з деякими заданими властивостями. Завдання такого типу зустрічаються досить часто. Гарантовано їх рішення знаходиться повним перебору або, що те ж саме повним обходом дерева.
Обхід усіх гілок можна здійснити, наприклад, за правилом правої або лівої руки. Це правило визначає гілку, якою треба йти на черговому кроці пошуку. Сформулюємо правило.
Нехай на деякому кроці роботи алгоритму ми знаходимося в деякій вершині дерева і необхідно прийняти рішення про те по якій гілці йти далі. Врахуємо, що з кожної вершини довільну кількість гілок йде вниз і тільки одна нагору. Можливі наступні ситуації:
Усі гілки йдуть вниз вже пройдені. Фізично це може визначаться який-небудь позначкою встановлюється на гілки в тому випадку якщо по ній здійснюється повернення. Тоді необхідно йти по гілці йде вгору і позначити її як пройдену.
Серед гілок провідних вниз є не пройдені. Знайдемо серед них саму ліву і підемо по ній.
Сформульоване правило ніяк не враховує події відбуваються у вершинах дерева. Між тим вершина від вершини може відрізнятися і не тільки положенням в дереві. Наприклад, у розглянутій вище завданню при переході вниз наростає сума, а при переході вгору та сума зменшується. Таким чином, існує клас задач, для яких до дерева комбінацій даних може бути прив'язана деяка величина змінюється закономірним чином. Звичайно, це не обов'язково збільшення. Спробуємо описати поведінку цієї величини в загальному вигляді. Назвемо її характеристикою дерева.
Характеристика змінюється усередині деякого числового інтервалу.
Ця зміна має властивість монотонності при русі по дереву вниз.
Існує критичне значення (ліва або права межа інтервалу), таке, що якщо характеристика досягає цього критичного значення, то подальший пошук рішення втрачає сенс.
З урахуванням такої характеристики описане вище правило обходу дерева трохи змінюється і тепер виглядає ось так:
Усі гілки йдуть вниз вже пройдені. Тоді необхідно йти по гілці йде вгору і позначити її як пройдену.
Серед гілок провідних вниз є не пройдені, але характеристика досягла своєї критичної величини. Тоді необхідно йти по гілці йде вгору і позначити її як пройдену.
Серед гілок провідних вниз є не пройдені і характеристика не досягла критичного значення. Знайдемо серед них саму ліву і підемо по ній.
Обхід дерева комбінацій відповідно до описаного вище правилом і є метод бектрекінга (BackTracking - зворотний хід). Сформульоване правило досить загальне і під нього підходить досить багато завдань, але все-таки це не найбільш загальне формулювання. Думаю, існує багато можливостей розширити правило. Наприклад, можна покласти, що характеристик кілька і вони залежать один від одного складним чином. Можна якось змінити поняття характеристики. Але ми зараз займатися цим не будемо, Якщо є бажання спробуйте самостійно сформулювати більш широке правило. А ми зараз розглянемо приклад застосування Бектрекінга.

2. Умова задачі

Хтось, назвемо його покупцем, зайшов в магазин маючи на руках певну суму грошей. Його мета придбати якомога більшу кількість товару (на вагу) в межах наявної суми грошей. Для кожного товару задана ціна і вага. Іменувати товари будемо для простоти номером.
Попередні зауваження.
Завдання очевидно комбінаторна, тому цілком достатньо перебрати всі можливі комбінації товарів і для кожної комбінації з'ясовувати сумарна вага і загальну вартість і стежити за тим, щоб загальна вартість на перевищила готівкову суму грошей.
Зі сказаного вище випливає, що завдання можна вирішити звичайним повним перебором. Так ми і поступимо, а потім у переборного рішення додамо механізм бектрекінга.
Неважко також помітити, що завдання очевидно має гарне рекурсивне рішення, але ми будемо шукати не рекурсивне рішення, щоб не створювати проблем тим, для кого рекурсія бути може новий метод програмування.

3. Рішення повним перебором

Думаю, покупець буде вести себе таким чином: візьме перший товар (а всі товари пронумеровані), потім наступний з решти, потім наступний з решти і т.д. поки не забере всі товари.
Потім він викладе останній і знову спробує збільшити кількість товарів, але це не має сенсу, оскільки останній товар він тільки що виклав. Тоді він викладе передостанній і покладе в сумку останній, і у нього вийде нова сукупність товарів.
Діючи, таким чином, покупець буде отримувати все нові і нові сукупності і для кожної перевіряти, а чи може він цю сукупність товарів оплатити і якщо може, то чи буде вона за масою більше тієї яку він вже запам'ятав як найважчу.
Тепер те ж саме але трохи більш строго.
Припустимо, що у покупця є сумка в якій стільки ж відділів скільки товарів і ці відділи пронумеровані. Кожен раз коли покупець кладе в сумку новий товар, утвориться нова сукупність товарів яка може виявитися шуканої. Для того, щоб це з'ясувати покупець після того, як поклав товар, зважує сумку і з'ясовує дві речі: чи може він це сплатити і якщо так, то важить чи сумка більше, ніж запомненний вагу. А спочатку сумка не важить нічого.
У покупця дві проблеми:
Велика. Як забезпечити повний перебір всіх допустимих сукупностей товарів. Маленька. Як зробити так, щоб не було повторів. Адже може так вийде, що він візьме одні й ті ж товари, але в різному порядку. Це звичайно не біда, але зайва робота. Я вважаю, що ці дві проблеми вирішуються наступним чином:
У першому відділі повинні побувати всі товари. У відділі з номером i повинні побувати всі товари з номерами на меншим ніж i. Таким чином для кожного відділу з номером i будуть отримані всі допустимі комбінації товарів в інших відділах з номерами великими чим i і відповідно для відділу з номером 1 будуть отримані взагалі всі можливі комбінації.
Напевно варто навести конкретний приклад робіт алгоритму. Візьмемо наступне безліч: 1, 2,3. Для цього безлічі алгоритм дасть наступні комбінації:
(1), (1,2), (1, 2,3), (1, 2,3), (1,3)
(2), (2,3)
(3)
щоб виключити можливість повтору, перед тим як покласти товар у сумку будемо перевіряти чи немає його в сумці вже. Звучить безглуздо звичайно, але справа в тому, що реально ми будемо працювати не в магазині з сумкою, а з масивами і знищувати елемент масиву "магазин", а потім його відновлювати - це зайва робота, простіше здійснювати названу вище перевірку.

program example;
uses crt;
var
b, s: array [1. .100] Of word;
a: array [1. .100] Of record
cost, ves: word;
end; {Масив магазин}
sum_ves, sum_cost, max, money, level, i, n: integer;
function add_element (d: integer): integer;
var
i: integer;
q: boolean;
begin
repeat
{Шукаємо поки не знайдемо}
q: = true;
{Перевірка є такий товар чи ні}
for i: = 1 to level do
if s [i]> = d then q: = false;
if q then add_element: = d
else
begin
d: = d +1;
{Перевірка, чи не вийшли ми за допустимі межі}
if d> n then
begin
add_element: = 0;
q: = true;
end;
end;
until q
end;
begin
clrscr;
read (n);
for i: = 1 to n do
begin
writeln ('Елемент номер -', i);
write ('Введіть його вага -'); read (a [i]. ves);
write ('Введіть його ціну -'); read (a [i]. cost);
b [i]: = i;
end;
write ('Скільки грошей у наявності -'); read (money);
clrscr;
level: = 1; max: = 0;
while b [1] <n do
begin
{Пошук елемента не використаного на цьому рівні}
b [level]: = add_element (b [level]);
if b [level]> 0
then
begin
s [level]: = b [level];
level: = level +1;
sum_ves: = 0; sum_cost: = 0;
for i: = 1 to n do
if s [i] <> 0 then
begin
sum_ves: = sum_ves + a [s [i]]. ves;
sum_cost: = sum_cost + a [s [i]]. cost;
end;
if (max <sum_ves) and (sum_cost <= money) then max: = sum_ves;
end
else
begin
{Звільняємо відділ}
s [level]: = 0;
b [level]: = level;
level: = level-1;
end;
end;
write ('Найбільшу вагу -', max);
end.

3. Бектрекінг

Реалізувати механізм бектрекінга дуже легко. Згадаймо, що його суть в тому, щоб організувати відскік в переборі варіантів тому коли з'ясується, що йти вперед не можна. Такий відскік у нас вже є. Ось ця група операторів:
{Звільняємо відділ}
s [level]: = 0;
b [level]: = level;
level: = level-1;

Зауважте, що цій групі операторів абсолютно не має значення причина по якій до неї звертаються. Тому додамо до програми ще одну причину звернення до цієї групи. А саме
Якщо сума набраного товару більше наявної готівки
ТО звільняємо відділ.
Зауважимо, також, що група операторів "Звільняємо відділ" повторюється двічі тому є сенс організувати її у вигляді процедури. А ось як виглядає тепер програма:
program example;
uses crt;
var
b, s: array [1. .100] Of word;
a: array [1. .100] Of record
cost, ves: word;
end;
sum_ves, sum_cost, max, money, level, i, n: integer;
procedure back;
begin
s [level]: = 0;
b [level]: = level;
level: = level-1;
end;
function add_element (d: integer): integer;
var
i: integer;
q: boolean;
begin
repeat
q: = true;
for i: = 1 to level do
if s [i]> = d then q: = false;
if q then add_element: = d
else
begin
d: = d +1;
if d> n then
begin
add_element: = 0;
q: = true;
end;
end;
until q
end;
begin
clrscr;
read (n);
for i: = 1 to n do
begin
writeln ('Елемент номер -', i);
write ('Введіть його вага -'); read (a [i]. ves);
write ('Введіть його ціну -'); read (a [i]. cost);
b [i]: = i;
end;
write ('Скільки грошей у наявності -'); read (money);
clrscr;
level: = 1; max: = 0;
while b [1] <n do
begin
{Пошук елемента не використаного на цьому рівні}
b [level]: = add_element (b [level]);
if b [level]> 0
then
begin
s [level]: = b [level];
level: = level +1;
sum_ves: = 0; sum_cost: = 0;
for i: = 1 to n do
if s [i] <> 0 then
begin
sum_ves: = sum_ves + a [s [i]]. ves;
sum_cost: = sum_cost + a [s [i]]. cost;
end;
if sum_cost> money then back
else
if (max <sum_ves) then max: = sum_ves;
end
else back;
end;
write ('Найбільшу вагу -', max);
end.

Висновок

Описаний метод виглядає досить специфічно і здається, що не так багато завдань підходять під його можливості. Однак розглянемо задачу, яка як здається на перший погляд досить далека від описаної вище.
Умова: Дано фігура з картону. Чи можна її розрізати на задані фігури (і за формою і за розміром)
Визначимо поняття розрізу таким чином: розріз це лінія певної довжини проведена по фігурі з початком у певній точці і в певному напрямі. Додаткові знання форми вихідної фігури і форм необхідних фігур дозволять скоротити безліч допустимих розрізів і зробити його нехай великим, але кінцевим.
Тоді завдання стає завданням повного перебору. Бектрекінг накладається на неї дуже просто і природно. Нехай ми провели черговий розріз. Перевіримо, чи дав він у сукупності з іншими розрізами фігуру. Якщо так, то перевіримо, чи входить ця вирізана фігура в безліч шуканих. Якщо ні, то дане безліч розрізів тупикове.

Література

1. Вострикова З.П. та ін "Програмування на мові" БЕЙСІК "для персональних ЕОМ". Машинобудування, 1993р.
2. Гохман А.В. та ін "Збірник задач з математичної логіки і алгебри множин", видавництво Саратовського Університету, 1969р.
3. Гусєв В.В. Основи імпульсної техніки. М. Радянське радіо, 1975
4. Касаткін В.М. "Інформація, алгоритми, ЕОМ", М. Освіта, 1991р.
5. Машовця В.А. Вступні іспити з інформатики / / Інформатика. 1997, № 13
6. Орлов В.О. Про вступні іспити з інформатики / / Інформатика, 1997, № 15
7. Яснева Г.Г. Логічні основи ЕОМ / / Інформатика та освіта, 1998, № 2
8. Лискова В.Ю., Ракітіна Є.А. Логіка в інформатиці, М. Інформатика та освіта 1999
9. Шауцкова Л.З. "Рішення логічних задач засобами алгебри логіки", газета Інформатика 1999, № 5.
Додати в блог або на сайт

Цей текст може містити помилки.

Програмування, комп'ютери, інформатика і кібернетика | Реферат
29.7кб. | скачати


Схожі роботи:
Механізм держави 3
Фінансовий механізм
Механізм народовладдя
Механізм пологів
Механізм важіля
Механізм держави 2
Програмний механізм
Механізм страхування
Механізм держави 2
© Усі права захищені
написати до нас