ARUBA INSTANT WI-FI: ПРОСТІ, ПОТУЖНІ, ДОСТУПНІ
У статті розглядається класична задача про хід коня, для вирішення якої розроблені ітеративна, рекурсивна і автоматна програми, а також наводяться результати їх дослідження. Побудована автоматна програма породжує ті ж результати, що і ітеративна, але вона більш наочна.
Методи оптимізації
До одного з найбільш цікавих розділів програмування відносяться завдання з області штучного інтелекту, в яких рішення шукається методом проб і помилок [1,2]. При цьому має місце перебір при пошуку рішення, а його тривалість може бути скорочена за рахунок застосування тих чи інших евристичних правил (методи оптимізації).
Клас алгоритмів, що дозволяє вирішувати подібні завдання, в англомовній літературі називається «backtracking algorithms» ( «алгоритми з поверненням»). Такі алгоритми застосовуються тоді, коли не підходять більш «спрямовані» методи [3].
Давайте досліджуємо одну з найбільш відомих задач даного класу - про хід коня [3-5]. Вона полягає в тому, щоб знайти обхід дошки розміром NxM конем, що переміщається по правилам шахової гри. Якщо такий обхід існує, то кожне поле відвідується тільки один раз (виконується NxM-1 кроків). Тут ми проаналізуємо методи оптимізації (скорочення перебору) і досліджуємо роботу итеративной, рекурсивної і автоматною програм. Розглянемо спочатку методи оптимізації, що застосовуються для скорочення перебору в итеративной програмі:
- визначення клітин, обхід з яких неможливий (оптимізація 1);
- виявлення заблокованих клітин (оптимізація 2);
- застосування правила Варнсдорф (оптимізація 3);
- використання різних масивів для ходів коня (оптимізація 4).
Визначення клітин, обхід з яких неможливий
Якщо кількість клітин дошки непарній (число білих і чорних клітин відрізняється на одиницю), то обхід існує тільки з клітин того кольору, яких буде більше. Неважко помітити, що шлях коня проходить по клітинам, що чергується за кольором. Якщо загальне число клітин дошки непарній, то перша і остання клітини шляху, пройденого конем, будуть одного і того ж кольору. Значить, обхід буде існувати тільки тоді, коли він почнеться кліткою того кольору, який мають найбільше число клітин.
Виконання даної умови перевіряється наступною функцією:
Однак наведене правило не охоплює всіх клітин, для яких обходу не існує. Так, для дошки розміром 3x7 клітин крім тих, для яких виконується наведене правило, обхід неможливий також з клітки (2,4).
Виявлення заблокованих клітин
Якщо при черговому ході утворюється клітина, куди можна увійти, але звідки можна вийти, то такий хід неприпустимий, за винятком передостаннього в обході. Як буде показано нижче, даний метод оптимізації дозволяє значно скоротити число повернень, в тому числі і при спільному використанні з правилом Варнсдорф.
Його розвитком стало визначення груп заблокованих клітин, пов'язаних один з одним, але відрізаних від решти дошки. У даній програмі визначаються групи з двох заблокованих клітин, що значно зменшує кількість повернень для невеликих дощок, а при використанні разом з правилом Варнсдорф - і для великих (наприклад, розміром 100x100 клітин).
Застосування правила Варнсдорф
Серед багатьох евристичних методів, використовуваних для скорочення перебору [5], правило Варнсдорф є найбільш простим. Відповідно до нього під час обходу дошки шахового коня слід кожен раз ставити на те поле, з якого він може зробити найменше число ходів по ще не пройденим полях. Якщо таких полів кілька, то можна вибрати будь-який з них, що може, однак, завести коня в глухий кут і зажадати повернення. Відзначимо, що найкращим чином правило Варнсдорф працює для кутових полів.
Використання різних масивів для ходів коня
Ходи коня можуть бути задані, наприклад, у вигляді масиву:
Кожен його елемент визначає один можливий хід коня і містить зміни його координат на дошці при здійсненні ходу. При використанні різних масивів для ходів коня кількість повернень може відрізнятися. У програмі застосовуються п'ять масивів, що містять можливі ходи коня в різному порядку. У ній задається максимальна кількість повернень (GOOD_RET), і коли воно буде досягнуто, пошук шляху починається заново з використанням вже іншого масиву. При пошуку обходу із застосуванням останнього масиву кількість повернень обмежується значенням MAX_RET. Якщо при спільному використанні всіх запропонованих методів оптимізації встановити значення GOOD_RET рівним одиниці, то для дощок, близьких до квадратних, можна будувати обходи без єдиного повернення для всіх клітин, з яких існує обхід. Обхід без єдиного повернення з кожної клітини не вдається отримати для «витягнутих» дощок (наприклад, 14x3 клітини) і для великих (наприклад, 100x100 клітин).
Ітеративна програма
повний перебір
Ідея алгоритму для итеративной програми полягає в наступному:
- на кожному кроці шукається фрагмент шляху, що починається з поточної клітки і не включає вже пройдені;
- при здійсненні ходу з масиву можливих ходів витягується черговий елемент, який приводить в незайняту клітку, що знаходиться в межах дошки;
- якщо хід неможливий, то відбувається повернення в попередню клітку (скасування ходу);
- пошук шляху вважається успішним тоді, коли номер поточного ходу стане рівною кількості клітин на дошці. Якщо з початкової клітини перебрані всі можливі ходи, то шляху не існує.
Структура функції, що виконує перебір, приведена в лістингу 2.
Номер використаного варіанта для кожного з ходів запам'ятовується в масиві, розмір якого вибирається відповідно до розміру дошки. Описаний алгоритм виконує перебір варіантів і знаходить рішення, якщо воно є. Відсутність рішення призводить до повного перебору всіх варіантів. У табл. 1 для ілюстрації виконання повернень наведено протокол обходу дошки розміром 3x4 клітини з клітки (2,4).
Таблиця 1. Протокол обходу дошки розміром 3x4 клітини з клітки (2,4)
Для деяких клітин програма працює надзвичайно повільно вже при невеликих розмірах дошки. Так, для дошки 6x6 клітин при старті з клітки (5,2) пошук шляху вимагає 291 077 505 повернень.
Результати роботи програми з оптимізацією
З роботи [5] відомо, що для дощок розміром NxM і MxN:
- не існує жодного обходу при N, M 7; N> 4, M> 5.
Переходячи до викладу отриманих результатів відзначимо, що вони відносяться до перерахованих вище методів оптимізації та евристичний обраним масивів варіантів для ходу коня. При застосуванні інших методів оптимізації [5] та інших масивів одержувані результати можуть відрізнятися.
Для прикладу розглянемо результати обходу деяких дощок. Для дошки розміром 5x5 клітин наводиться таблиця, де вказується кількість повернень, виконане при знаходженні обходу з відповідною клітини (табл. 2). У разі відсутності обходу в клітці ставиться символ N, а якщо кількість повернень перевищило задається в програмі величину (MAX_RET = 400 000), то пошук шляху припиняється, а у відповідній клітці виводиться скорочення LIM. У таблицях, побудованих для методу оптимізації, коли використовуються різні масиви варіантів для ходу коня, в клітці додатково дається позначення того масиву (від A до E), при застосуванні якого обхід відбувався без повернень (GOOD_RET = 1). Причому якщо результат був отриманий для першого масиву, то відповідний йому символ A не виводиться.
Таблиця 2. Результати роботи програми для дошки розміром 5 x 5 клітин
Для класичної шахової дошки розміром 8x8 клітин отримані такі результати:
- для оптимізацій 1 і 2 в більшості клітин перевищено граничне значення числа повернень. Мінімальна кількість повернень в клітці (5,5) - 2502;
- для оптимізацій 1 і 3 у всіх клітинах вийшов нуль повернень, крім клітин (4,1) і (6,4), де вийшло 9 і 79 повернень відповідно;
- для оптимізацій 1-3 в клітці (6,4) було три повернення, а в інших - нуль повернень;
- для оптимізацій 1-4 у всіх клітинах вийшов нуль повернень, а в клітці (6,4) був використаний другий масив можливих ходів.
Для дошки розміром 100x100 клітин отримані такі результати:
- для оптимізацій 1-3 в більшості клітин отримано нуль повернень, а кількість повернень в інших клітинах варіюється від одиниці до значень, що перевищують заданий межа;
- для оптимізацій 1-4 у всіх клітинах, за винятком клітин (94,24) і (94,79), вийшов нуль повернень.
рекурсивна програма
Найбільш відоме рішення для задачі обходу конем - рекурсивне [2]. При цьому структура функції, що виконує перебір, має такий вигляд:
У цій програмі можуть бути використані всі види оптимізацій, описані вище.
автоматна програма
Якщо дві перші програми для вирішення цього завдання цілком традиційні [2], то автоматні до таких не належать. Відзначимо, що автоматна програма може бути формально побудована з описаної вище итеративной за допомогою методу, викладеного в роботі [7]. Автоматна програма може бути також формально побудована і з поступовим зниженням рекурсивної програми з використанням методу, запропонованого в роботі [8].
Мал. 1. Схема зв'язків автомата
Крім того, можна створити автоматну програму шляхом безпосередньої побудови автомата за умовами завдання. На рис. 1, 2 наведені відповідні схема зв'язків і граф переходів автомата Мілі.
Мал. 2. Граф переходів автомата
Даний автомат використовує функції і змінні, визначені в итеративной програмі, тому в ньому застосовуються всі розглянуті методи оптимізації, а одержувані з його допомогою результати збігаються з результатами роботи итеративной програми.
Спрощений текст функції, що реалізує цей автомат, приведений в лістингу 4.
Що ж краще?
Як було зазначено вище, ітеративна і автоматна програми видають однакові результати, проте автоматна, що виділяється явним виділенням станів, більш зрозуміла.
Результати інших експериментів і повний текст програми, за допомогою якої вони були виконані, будуть приведені на сайтах is.ifmo.ru і www.softcraft.ru в розділі «Автомати».