Отримання знань
дистанційна підтримка освіти школярів
Пошук у ширину.
Для реалізації стратегії пошуку в ширину доцільно використовувати чергу. Черга - це лінійний список, до якого елемент додається з одного кінця, а вилучається з іншого. Покажемо, як за допомогою черги здійснити пошук у ширину для задачі про посудину.
Перш за все започаткуємо чергу. Для цього запишемо в неї початкову позицію. "Голова" черги - це той її елемент, що вилучатиметься першим, "хвіст" - щойно доданий елемент. На початку черга містить єдиний елемент - початковий стан, тобто 0.
Зі стану 0 можна отримати лише стани 2 та 7. Додамо їх до черги, а оброблений елемент 0 вилучимо. Черга матиме такий вигляд.
0
0-2 {голова}
0-7 {хвіст}
У черзі знаходяться всі послідовності переливань довжиною 1.
Опрацьовуємо наступний стан 0-2. Послідовність переливань 0-2 можна продовжити як 0-2-4 або 0-2-9. Додамо отримані послідовності до черги, а запис 0-2 вилучаємо. Після обробки стану 0-2 отримуємо таку чергу.
0
0-2
0-7 {голова}
0-2-4
0-2-9 {хвіст}
Наступний крок - обробка шляху 0-7. Продовжити послідовність 0-7 можна як 0-7-9 або 0-7-5. Черга виглядатиме так:
0
0-2
0-7
0-2-4{голова}
0-2-9
0-7-9
0-7-5 {хвіст}
На цьому кроці з черги вилучено всі послідовності довжиною 1, у черзі знаходяться тільки послідовності довжиною 2. Продовжуємо будувати чергу для трьох переливань. Стани, отримані за одне переливання, не наводимо.
0-2-4
0-2-9 {голова}
0-7-9
0-7-5
0-2-4-6 {хвіст}0-2-4
0-2-9
0-7-9 {голова}
0-7-5
0-2-4-6
0-2-9-7 {хвіст}
Послідовність 0-2-9-2 теж некоректна.
0-2-4
0-2-9
0-7-9
0-7-5 {голова}
0-2-4-6
0-2-9-7
0-7-9-2{хвіст}
Наступний крок.
0-2-4
0-2-9
0-7-9
0-7-5
0-2-4-6{голова}
0-2-9-7
0-7-9-2
0-7-5-3{хвіст}
Оброблено повністю два переливання, в черзі записано всі коректні послідовності переливань довжиною 3.
На наступних кроках отримаємо всі послідовності переливнь довжиною 4.
Зауважимо, що саме на цьому кроці одна з послідовностей призведе до знаходження оптимального розв'язку.
Отже, для 4 переливань:
Перший крок.
0-2-4-6
0-2-9-7 {голова}
0-7-9-2
0-7-5-3
0-2-4-6-8{хвіст}
Другий крок.
0-2-4-6
0-2-9-7
0-7-9-2 {голова}
0-7-5-3
0-2-4-6-8
0-2-9-7-5 {хвіст}
Третій крок.
0-2-4-6
0-2-9-7
0-7-9-2
0-7-5-3 {голова}
0-2-4-6-8
0-2-9-7-5
0-7-9-2-4{хвіст}
Четвертий крок.
0-2-4-6
0-2-9-7
0-7-9-2
0-7-5-3
0-2-4-6-8 {голова}
0-2-9-7-5
0-7-9-2-4
0-7-5-3-10 {оптимальний розв'язок}
0-7-5-3-1 {хвіст}
Якщо задача вимагає знаходження одного оптимального розв'язку, алгоритм повинен закінчити роботу. Якщо ж потрібно знайти всі розв'язки, продовжуємо будувати чергу, доки не отримаємо всі розв'язки.
Зауважимо, що знайдений розв'язок та "глухий кут" нового запису до черги не додають. Тому алгоритм пошуку в ширину завжди закінчить роботу, якщо в задачі неможлива ситуація "зациклювання". В задачі про посудину зациклювання можливе, якщо допустити, що стани посудини можуть повторюватись. Продовжимо будувати чергу.
Для 5 переливань черга змінюється таким чином.
Перший крок.
0-2-4-6-8
0-2-9-7-5 {голова}
0-7-9-2-4
0-7-5-3-10 {оптимальний розв'язок}
0-7-5-3-1
0-2-4-6-8-10 {другий розв'язок}
0-2-4-6-8-1 {хвіст}
Другий крок.
0-2-4-6-8
0-2-9-7-5
0-7-9-2-4{голова}
0-7-5-3-10 {оптимальний розв'язок}
0-7-5-3-1
0-2-4-6-8-10 {другий розв'язок}
0-2-4-6-8-1
0-2-9-7-5-3 {хвіст}
Третій крок.
0-2-4-6-8
0-2-9-7-5
0-7-9-2-4
0-7-5-3-10 {голова} {оптимальний розв'язок}
0-7-5-3-1
0-2-4-6-8-10 {другий розв'язок}
0-2-4-6-8-1
0-2-9-7-5-3
0-7-9-2-4-6 {хвіст}
Четвертий крок. Оскільки в голові черги знаходиться розв'язок, з якого перехід до нового стану неможливий, нова послідовність не додається.
0-7-5-3-10
0-7-5-3-1 {голова}
0-2-4-6-8-10 {другий розв'язок}
0-2-4-6-8-1
0-2-9-7-5-3
0-7-9-2-4-6 {хвіст}
П'ятий крок.
0-7-5-3-1
0-2-4-6-8-10 {голова} {другий розв'язок}
0-2-4-6-8-1
0-2-9-7-5-3
0-7-9-2-4-6
0-7-5-3-1-8 {хвіст}
Отже, 5 переливань розглянуто повністю. Знайдено ще один (але не оптимальний за кількістю передивань) спосіб наповнити посудину. Переходимо до 6 переливань.
Перший крок.
0-2-4-6-8-10
0-2-4-6-8-1 {голова}
0-2-9-7-5-3
0-7-9-2-4-6
0-7-5-3-1-8 {хвіст}
Другий крок.
0-2-4-6-8-1
0-2-9-7-5-3 {голова}
0-7-9-2-4-6
0-7-5-3-1-8
0-2-4-6-8-1-3 {хвіст}
Третій крок.
0-2-4-6-8-1
0-2-9-7-5-3
0-7-9-2-4-6 {голова}
0-7-5-3-1-8
0-2-4-6-8-1-3
0-2-9-7-5-3-10 {розв'язок}
0-2-9-7-5-3-1 {хвіст}
Четвертий крок.
0-2-4-6-8-1
0-2-9-7-5-3
0-7-9-2-4-6
0-7-5-3-1-8 {голова}
0-2-4-6-8-1-3
0-2-9-7-5-3-10 {розв'язок}
0-2-9-7-5-3-1
0-7-9-2-4-6-8 {хвіст}
П'ятий крок.
0-2-4-6-8-1
0-2-9-7-5-3
0-7-9-2-4-6
0-7-5-3-1-8
0-2-4-6-8-1-3{голова}
0-2-9-7-5-3-10 {розв'язок}
0-2-9-7-5-3-1
0-7-9-2-4-6-8
0-7-5-3-1-8-10 {розв'язок}
0-7-5-3-1-8-6 {хвіст}
Вкажіть першу послідовність довжиною 7, яка додаватиметься до черги.
Так отримається наступний розв'язок. Подальшу поведінку черги для 7 переливань наводимо без розділення на кроки.
0-2-4-6-8-1-3
0-2-9-7-5-3-10 {розв'язок}
0-2-9-7-5-3-1
0-7-9-2-4-6-8
0-7-5-3-1-8-10 {розв'язок}
0-7-5-3-1-8-6
0-2-4-6-8-1-3-5 {голова}
0-2-4-6-8-1-3-10 {розв'язок}
0-2-9-7-5-3-1-8
0-7-9-2-4-6-8-10 {розв'язок}
0-7-9-2-4-6-8-1
0-7-5-3-1-8-6-4 {хвіст}
Для 8 переливань маємо:
0-2-4-6-8-1-3-5
0-2-4-6-8-1-3-10 {розв'язок}
0-2-9-7-5-3-1-8
0-7-9-2-4-6-8-10 {розв'язок}
0-7-9-2-4-6-8-1
0-7-5-3-1-8-6-4
0-2-4-6-8-1-3-5-7{голова}
0-2-9-7-5-3-1-8-10 {розв'язок}
0-2-9-7-5-3-1-8-6
0-7-9-2-4-6-8-1-3
0-7-5-3-1-8-6-4-2 {хвіст}
І, нарешті, для 9 переливань.
0-2-4-6-8-1-3-5-7
0-2-9-7-5-3-1-8-10 {розв'язок}
0-2-9-7-5-3-1-8-6
0-7-9-2-4-6-8-1-3
0-7-5-3-1-8-6-4-2
0-2-4-6-8-1-3-5-7-9 {голова}
0-2-9-7-5-3-1-8-6-4
0-7-9-2-4-6-8-1-3-5
0-7-9-2-4-6-8-1-3-10 {розв'язок}
0-7-5-3-1-8-6-4-2-9 {хвіст}
Наступний перехід (до 10 переливань) призведе до стану черги, коли в ній не буде жодного запису. Це означає, що алгоритм завершено - знайдено всі можливі розв'язки.
Опишемо стратегію пошуку в ширину шкільною алгоритмічною мовою.
Алг Пошук_у_ширину
Поч
започаткувати чергу (розмістити початковий стан у голові черги)
повтори
Створити всі коректні продовження послідовності, що знаходиться у голові черги
Додати ці продовження у хвіст черги
Якщо продовження є розв'язком
То видати результат
Все
Вилучити послідовність з голови черги
до черга порожня
Кін
Якщо немає необхідності знаходити всі розв'язки, умова виходу з циклу дещо ускладнюється.