• Гідрологія і Гідрометрія
• Господарське право
• Економіка будівництва
• Економіка природокористування
• Економічна теорія
• Земельне право
• Історія України
• Кримінально виконавче право
• Медична радіологія
• Методи аналізу
• Міжнародне приватне право
• Міжнародний маркетинг
• Основи екології
• Предмет Політологія
• Соціальне страхування
• Технічні засоби організації дорожнього руху
• Товарознавство продовольчих товарів

Контрольні запитання.

Задача про велосипедний замок

Програмування с відходом назад

Метод розробки алгоритму, відомий як програмування с відходом назад, можна описати як організований вичерпний пошук, що часто дозволяє уникнути дослідження всіх можливостей. Цей метод особливо зручний для рішення задач, що вимагають перевірки потенційно великого, але кінцевого числа рішень.

Як приклад розглянемо комбінаційний замок для велосипеда, що складає з набору N перемикачів, кожний з який може бути в положенні «ввімкнено» чи «вимкнуто». Замок відкривається тільки при одному наборі положень перемикачів, з яких не менш [ N/2] знаходяться в положенні «ввімкнено». Припустимо, що ми забули цю комбінацію, а нам треба відімкнути замок. Припустимо також, що ми готові перепробувати (якщо необхідно) усі комбінації. Нам потрібний алгоритм для систематичного генерування цих комбінацій. Якщо проігнорувати умова [ N/2], то для замка існує 2^N можливих комбінацій. Непогані шанси знайти правильну комбінацію можуть бути при N<10. Однак умова [ N/2] дозволить відкинути (чи не генерувати) багато комбінацій.

Змодулюємо кожну можливу комбінацію вектором з N нулів і одиниць. На і-му місці буде 1, якщо і-й перемикач знаходиться в положенні «ввімкнено», і 0, якщо і-й перемикач — у положенні «вимк». Множин усіх можливих N-векторів добре моделюється з допомогою двійкового дерева. Кожна вершина к-ro рівня цього дерева буде відповідати визначеному набору перших к компонент N-вектора. Дві гілки, що йдуть униз з вершини цього рівня, відповідають двом можливим значенням (к+1)-ї компоненти в N-векторі. У дерева буде N рівнів. Рис. 2.9 на прикладі N=4 пояснює основну конструкцію.

Умова, що полягає в тім, що число перемикачів у положенні «ввімкнено» повинне бути не менше [ N/2], дозволяє нам не утворювати частини дерева, що не можуть; привести до правильної комбінації. Наприклад, розглянемо вершину 00 на Рис. 12. Тому що права гілка (до 000) не може привести до припустимої комбінації, немає потреби її формувати. Якщо якісь вершини, що випливають за розглянутою вершиною, не задовольняють обмеженню задачі, то ці вершини не треба розглядати. У даному випадку ніякі з вершин, що знаходяться усередині пунктирних ліній, не потрібно досліджувати і навіть формувати.

Тепер, скориставшись цією моделлю двійкового дерева, можна викласти процедуру відходу назад для утворення тільки тих комбінацій, у яких принаймі

[ N/2] перемикачів знаходяться в положенні «ввімкнено». Алгоритм зводиться до перегляду дерева за допомогою рекурсивного алгоритму перегляду дерева зверху-вниз:

Рис. 2.9.. Двійкове дерево, що представляє N-вектори з нулів і одиниць.

Рухаємося вниз по дереву, дотримуючи лівої гілки, доти, поки це можливо. Досягали кінцевої вершини, випробуємо відповідну комбінацію. Якщо вона не підходить, піднімаємося на один рівень і перевіряємо, чи можемо ми спуститися знову по іншій гілці. Якщо це можливо, беремо саму ліву з недосліджених гілок. Якщо ні, відходимо нагору ще на один рівень і намагаємося спуститися з цієї вершини. Перед спуском перевіряємо, чи можна задовольнити умова про [ N/2] включені перемикачі в наступних вершинах.

Алгоритм зупиняється, коли ми повертаємося до кореня і не залишається непереглянутих гілок.

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

Задача — головоломка «8»

Рис. 2.10. ілюструє так звану головоломку «8». У коробці 3x3 знаходяться вісім рухливих квадратів, одне місце — порожнє (позначене х). Будь-який занумерований квадрат, що прилягає до порожнього місця, можна пересунути на це місце, при цьому порожнє місце виявиться в позиції, займаної до цього занумерованим квадратом. Наприклад, на Рис. 2.10, а квадрат 3 можна пересунути на місце, позначене х, порожнє місце виявиться в позиції, займаної до цього квадратом 3, як показано на Рис. 2.10,б. Спробуємо знайти послідовність пересувань, що перетворює конфігурацію, зображену на Рис2.10, а, у конфігурацію, показану на Рис. 2.10, в.

А Б В Г

Рис.2.10. Головоломка ”8”

Не очевидно, що програмування с відходом назад підходить для головоломки «8». Треба побудувати трохи штучну, але ефективну N-векторну структуру. Кожна вершина дерева буде відповідати конфігурації головоломки. Корінь (на рівні 0) буде відповідати вихідної конфігурації (Рис. 2.10, а), від нього будуть відходити гілки, що ведуть до вершин рівня 1, кожна з який буде відповідати конфігурації, отриманої одним пересуванням з Рис.2.11. Рис.

	х
	6	5

		Рівень 0

Побудова дерева відходів для головоломки «8»,

вихідної. Вершини, що безпосередньо випливають за будь-якою вершиною дерева, будуть упорядковані зліва направо по напрямку, у якому рухається порожня клітка. Сама ліва конфігурація буде відповідати руху порожньої клітки вліво, інші конфігурації будуть відповідати рухам пфожньої клітки нагору, вниз і праворуч. На Рис. 2.11 показані перші два рівня нашого дерева. Помітимо, що пересування порожньої клітки наверх із вихідної конфігурації неможливо.

Вершини рівня к відповідають усім конфігураціям, які можна досягти за к ходів з кореневої конфігурації. Не втрачаючи при цьому ніяких можливих шляхів до бажаної конфігурації, ми не будемо допускати, щоб безпосередньо наступна за який-небудь

вершиною конфігурація повторювала попередню. Наприклад, розглянемо саму праву вершину рівня 1 на Рис. 2.11. Ця вершина могла б мати два наступні, відповідні пересування порожнього квадрата вліво і вниз. Але пересування вліво повторить кореневу конфігурацію і не наблизить нас до остаточного результату.

Таким чином, елементи N-векторів, що відповідають конфігураціям, повинні задовольняти умові, що (к+1)-й елемент повинен виходити з к-го одним ходом і (к+1)-й елемент не може бути таким же, як (к—1)-й. Яке значення N? Глибина дерева j означає максимальну кількість ходів, що ми збираємося розглядати на шляху від вихідної конфігурації до кінцевого. Тому що ми не уявляємо собі, скільки ходів може знадобитися, N повинне бути обране на підставі нашого запасу машинного часу. Наприклад, якщо N=7, то процедура покаже, чи може бути отримана остаточна конфігурація не більш ніж за сім пересувань з вихідної конфігурації.

Тепер ми підготовлені до того, щоб скористатися процедурою с відходами для головоломки «8». Рис. 2.12 ілюструє дерево відходів. Номера, що стоять поруч с конфігураціями, показують порядок генерації вершин у процедурі. Остаточна конфігурація у вершині 20 має бути досягнута через три пересування від вихідного стану.

У найгіршому випадку алгоритми с відходами експонентні, тому що може виявитися необхідним вичерпний пошук на множині рішень с експонентним числом елементів. У раніше розглянутій задачі про велосипедний замок може бути Т вершин на рівні N, тому що пошук бінарний. Процедура с відходами, що відкидають 99% потенційно можливих рішень, є усе ще експонентної, тому що 27100 росте експонентно при N .

Програмування с відходом часто називають «методом на крайній випадок», тому що можна привести аргументи, що показують, що воно усього лише на один рівень ефективніше методів повного перебору.

Рис. 2.12. Дерево відходів, побудоване для одержання конфігурації у вершині 20.

1. Які алгоритми називають евристичними:

2. Коли виникає потреба використовувати евристичні алгоритми.

3. Викласти "жадібний алгоритм" для задачі про комівояжера".

4. Викласти алгоритми розв'язку задачі про процесори.

5. Як оцінюється помилка при використанні евристичних алгоритмів? Привести приклади.

6. Що таке програмування з відходом назад? Яку структуру даних при цьому звичайно використовуємо?

7. Сформулюйте задачу про велосипедний замок та алгоритм її розв'язку.

8. Яке рішення задачі "головоломка 8" Ви знаєте?

9. Як оцінити робочу функцію алгоритму з відходом назад? В яких випадках доцільно цей метод використовувати?

Читайте також:

1. Грошові кошти — готівка, кошти на рахунках у банку та депозити до запитання.
2. Дайте відповіді на контрольні питання
3. Запитання.
4. Запитання.
5. Запитання.
6. ІІ. Контрольні запитання
7. ІІ. ТЕСТОВІ КОНТРОЛЬНІ РОБОТИ.
8. Індивідуальний метод обліку кількості знесених яєць проводять у селекційних стадах, застосовують для цього контрольні гнізда, або утримання в індивідуальних клітках.
9. Конденсатозбірники і контрольні трубки
10. Контрольні відповіді до задач
11. Контрольні відповіді до задач
12. Контрольні відповіді до тестів

Переглядів: 806