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