Отримання знань

Пошук у ширину.

Минулий урок було присвячено стратегії пошуку всіх розв'язків задачі "в глибину". Якщо необхідно знаходити всі розв'язки певної задачі, така стратегія дає можливість згенерувати ці розв'язки, причому у лексикографічному порядку. Але якщо потрібно знайти лише один, але оптимальний розв'язок задачі, стратегія пошуку в глибину досить неефективна. У розглянутому прикладі з восьми розв'язків  лише сьомий виявився оптимальним. Розглянемо, як можно отримати розв'язки за іншою стратегією, яку називають пошуком у ширину. Описуватимемо цю стратегію для тієї ж самої задачі про посудину та на тому самому прикладі.

Отже, посудина вміщує 10 літрів рідини, наливати або виливати можна або 2, або 7 літрів. Спочатку розв'яжемо задачу знаходження оптимального (тобто за мінімальну кількість переливань) способу. Початковий стан - 0. За один хід можна перейти лише до станів 2 та 7. Зобразимо це на малюнку.

Але стан 0 в обох випадках повторюється, тому немає сенсу їх далі розглядати. Стан 9 можна отримати двома  різними способами.

За три переливання переходимо до таких станів. Випадки, коли стан повторюється, не малюємо.

На цьому кроці один з отриманих станів є цільовим. Шлях до нього від початкового стану  і буде оптимальним. В даному прикладі це +7 -2 -2 +7. Щоб отримати решту способів переливання, продовжимо будову дерева. Зауважимо, що наступні кроки дадуть неоптимальні розв'язки. Так, після п'ятого переливання отримаємо наступне. 

Отримали другий розв'язок, при якому мету досягнуто за 5 переливань.

Наступний крок.

Наступний крок.

Наступні два кроки.

Останній крок.

На цьому етапі всі стани, які отримано, не призводять до нових станів. Тому процес побудови дерева закінчується. Дерево, яке побудовано за стратегією "в ширину", ідентично до побудованого "в глибину", але розв'язки генеруються в порядку оптимальності.