Пошук у просторі станів
Залежно від того, який спосіб подання знань ми вибрали – декларативний чи продукційний – ми визначаємо спосіб застосування знань. З продукційною системою все досить просто: ми безпосередньо інтерпретуємо продукцію.
Якщо ж ми вибрали декларативне подання знань, то все відбувається дещо складніше. Для цього нам потрібно реалізуватипошук у просторі станів. Справа в тому, що структуроване уявлення знань організоване ієрархічно. А якщо ми намагаємося застосувати ієрархічний опис до вхідних даних, ми на кожному його рівні отримаємо можливі варіанти інтерпретації даних — гіпотези.
Для того щоб ефективно вибирати одну або кілька кращих гіпотез, уникаючи комбінаторного вибуху, використовуються алгоритми пошуку простору станів.
Простір станів виникає при розбитті розв'язання завдання окремі кроки. Тут виділяється початковий стан, коли ми ще не вибрали гіпотезу, а також кінцевий стан, коли ми знайшли гіпотезу, яка є допустимим розв'язанням нашого завдання. У процесі пошуку цієї гіпотези є операції переходу до наступного стану. При цьому не складно помітити, що просторовий стан має експоненційну складність, залежно від числових кроків. Якщо поставити собі за мету обійти простір станів цілком, знадобиться експоненційний час.
Щоб уникнути цієї проблеми, застосовуються різні алгоритми пошуку. Вони поділяються на два типи – повний перебір та евристичний пошук. Як зрозуміло, повний перебір у переважній більшості випадків годиться (якщо ми вирішуємо дуже маленьку завдання), але має якусь навчальну цінність. Тому ми розглянемо спочатку його, а ви, якщо добре з ним знайомі, можете одразу перейти до евристичного типу.
Пошук за допомогою повного перебору
Існують такі види повного перебору: пошук завширшки, пошук у глибину та пошук з ітеративним поглибленням. Під час пошуку в ширину ми робимо всі можливі кроки у просторовому стані початкового стану та отримуємо нову безліч станів. Далі з кожного стану цієї множини знову робимо всілякі кроки, отримуємо таку безліч станів і так далі - поки не знайдемо рішення. Графічно пошук завширшки можна як руху фронту у просторі станів.
Пошук у глибину означає, що з початкового стану ми робимо один крок, далі з нового стану робимо ще один крок і т.д., поки не дійдемо до кінцевого стану або до стану, з якого не можна більше зробити жодного кроку. У цьому випадку ми рекурсивно повертаємось назад і знову робимо кроки з того стану, в який повернулися, доки не знайдемо рішення. Нескладно помітити, що такий пошук завширшки має експоненційну складність як за часом, так і з пам'яті. А пошук углиб має експоненційну складність за часом. Звичайно, нам може пощастити, і рішення знайдеться одразу, але на практиці це є малоймовірним.
Пошук з ітеративним поглибленням - це оптимізація пошуку в глибину і в ширину, яка гарантовано дозволяє знайти найближче до початкового стану рішення, уникаючи експоненційної складності. Яким чином реалізується цей алгоритм? Ми шукаємо у глибину з обмеженням глибини константою N. Знайшли рішення – добре. Не знайшли - повторюємо пошук у глибину з константою N+1 і так далі, поки не знайдеться. Цей алгоритм, хоч і нескладний у реалізації, придатний лише найпростіших завдань.
Евристичний пошук
Найчастіше практичні завдання вирішуються за допомогою евристичногопошуку. Евристичний пошук ґрунтується на функції оцінки стану. На відміну від алгоритмів повного перебору, евристичний пошук дозволяє ранжувати просторові стани на основі їхньої «перспективності». Евристичний пошук шукає просторі станів більш цілеспрямовано, ніж алгоритми повного перебору. Важливо, що у багатьох завданнях оцінка є найкраща оцінка шляху досягнення цього стану з початкового. Якщо у нашій задачі можлива така оцінка, то алгоритми евристичного пошуку значно спрощуються.
Основний клас алгоритмів евристичного пошуку – пошук від найкращого стану. Він включає три основні алгоритми: це жадібний пошук, променевий пошук та А*. Загальна їх ідея полягає в підтримці у процесі пошуку безлічі досягнутих станів і виборі кожному кроці однієї чи кількох кращих станів.
Найпростіший з них -жадібний пошук. Якщо його застосувати у задачі пошуку найкращого шляху у графі, це дасть відомий алгоритм Дейкстри. Жадібний пошук, вибираючи стан, з якого буде продовжуватися пошук, шукає стан з найкращою оцінкою шляху від початкового в даний. Тому він і називається «жадібним» — оскільки «вистачає» найкращий стан, не думаючи про наслідки. Природно, як і багато жадібних алгоритмів, така стратегія не призводить до оптимального рішення. Кінцеві стани найчастіше досягаються надто довгим, неоптимальним шляхом. Крім того, жадібний пошук постійно повинен підтримувати безліч усіх досягнутих станів, яких може бути занадто багато, через що надмірно витрачається пам'ять.
У променевого пошуку є свої переваги та недоліки. Основний його мінус у тому, що, на відміну від жадібного, променевий пошук не гарантує знаходження кінцевого стану з найкращою якістю, тому що в процесі руху фронту найкращий стан може випасти з нього. Насправді з цим можна боротися, налаштовуючи ширину фронту. Чим фронт уже, тим швидше працює алгоритм, але тим частіше він помиляється. Чим ширший фронт, тим алгоритм працює краще, але довше. Це одна з його важливих переваг – можливість легко балансувати між швидкістю та якістю. Променевий пошук дуже популярний в академічному середовищі, особливо серед китайських вчених. Він простий у реалізації та працює досить непогано.
Ідея алгоритму А* полягає в тому, що ми вибираємо на кожному кроці не кращий, а найбільш перспективний стан. Той стан, через який із найбільшою ймовірністю проходить шлях до кращого кінцевого стану.
До оцінки поточного стану алгоритмі А* додається евристична оцінка знизу залишку шляху до кінцевого стану. Якщо евристична оцінка знизу досить хороша, то А* працює ефективно та швидко знаходить найкращий стан. І тут А* буде поліномінальним за кількістю кроків, а чи не експоненціальним. А* - це дійсно хороший алгоритм, у своїй роботі я використовую його набагато частіше, ніж променевий пошук.
У третьому пості цієї серії мова йтиме про способи отримання знань, що використовуються при створенні штучного інтелекту, а також про машинне навчання — зокрема, про методи, які використовуються в FineReader.