Пошук в просторі станів

  Ми продовжуємо серію постів про штучний інтелект, написаних за мотивами виступу в «Технопарку» Mail.ru Костянтина Онисимовича — директора департаменту розробки технологій ABBYY. Друга стаття буде присвячена алгоритмам пошуку.
 
 Навігатор по серії постів: Штучний інтелект для програмістів
 • Застосування знань: алгоритми пошуку в просторі станів
• Отримання знань: інженерія знань і машинне навчання
 
Залежно від того, який спосіб представлення знань ми вибрали — декларативний або продукційний — ми визначаємо спосіб застосування знань. З продукционной системою все досить просто: ми безпосередньо інтерпретуємо продукції.
 
Якщо ж ми вибрали декларативне подання знань, то все відбувається дещо складніше. Для цього нам потрібно реалізувати пошук в просторі станів . Справа в тому, що структуроване уявлень знань організовано ієрархічно. А якщо ми намагаємося застосувати ієрархічний опис до вхідних даних, то ми на кожному його рівні отримаємо можливі варіанти інтерпретації даних — гіпотези.
 
Для того щоб ефективно вибирати одну або декілька кращих гіпотез, уникаючи комбінаторного вибуху, використовуються алгоритми пошуку в просторі станів.
 
Простір станів виникає при розбитті рішення задачі на окремі кроки. Тут виділяється початковий стан, коли ми ще не вибрали гіпотезу, а також кінцевий стан, коли ми знайшли гіпотезу, яка є допустимим рішенням нашої задачі. У процесі пошуку цієї гіпотези є операції переходу в наступний стан. При цьому не складно помітити, що просторове стан має експонентну складність залежно від числових кроків. Якщо задатися метою обійти простір станів цілком, буде потрібно експоненціальне час.
 
Щоб уникнути цієї проблеми, застосовуються різні алгоритми пошуку. Вони діляться на два типи — повний перебір і евристичний пошук. Як уже ясно, повний перебір в переважній більшості випадків не годиться (якщо тільки ми не вирішуємо дуже маленьку задачу), але має якусь навчальну цінність. Тому ми розглянемо спочатку його, а ви, якщо добре з ним знайомі, можете відразу перейти до евристичному типом .
 
 
Пошук за допомогою повного перебору
Існують наступні види повного перебору : пошук в ширину, пошук в глибину і пошук з ітеративним поглибленням.
Під час пошуку в ширину ми робимо всі можливі кроки в просторовому стані початкового стану і отримуємо нове безліч станів. Далі з кожного стану цієї множини знову робимо все всілякі кроки, отримуємо таке безліч станів і так далі — поки не знайдемо рішення. Графічно пошук в ширину можна представити у вигляді руху фронту в просторі станів.
 
Пошук в глибину означає, що з початкового стану ми робимо один якийсь крок, далі з нового стану робимо ще один крок і т.д., поки не дійдемо до кінцевого стану або до стану, з якого не можна більше зробити жодного кроку. У цьому випадку ми рекурсивно повертаємося назад і знову робимо кроки з того стану, в яке повернулися, поки не знайдемо рішення.
Нескладно помітити, що такий пошук в ширину має експонентну складність як за часом, так і по пам'яті. А пошук в глибину має експонентну складність за часом. Звичайно, нам може пощастити, і рішення знайдеться відразу, але на практиці це малоймовірно.
 
Пошук з ітеративним поглибленням — це оптимізація пошуку в глибину і в ширину, яка гарантовано дозволяє знайти саме близьке до початкового стану рішення, уникаючи експоненційної складності. Яким чином реалізується цей алгоритм? Ми шукаємо в глибину з обмеженням глибини константою N. Знайшли рішення — добре. Не знайшли — повторюємо пошук в глибину з константою N +1 і так далі, поки не знайдеться. Цей алгоритм, хоча і нескладний у реалізації, придатний тільки для самих найпростіших завдань.
 
 
Евристичний пошук
Найчастіше практичні завдання вирішуються за допомогою евристичного пошуку. Евристичний пошук заснований на функції оцінки стану. На відміну від алгоритмів повного перебору, евристичний пошук дозволяє ранжувати просторові стану на основі їх «перспективності». Евристичний пошук шукає в просторі станів більш цілеспрямовано, ніж алгоритми повного перебору. Важливо, що в багатьох задачах оцінка стану є найкраща оцінка шляхи досягнення даного стану з початкового. Якщо в нашій задачі можлива така оцінка, то алгоритми евристичного пошуку значно спрощуються.
 
Основний клас алгоритмів евристичного пошуку — це пошук від найкращого стану. Він включає три основних алгоритму: це жадібний пошук, променевої пошук і А *. Загальна їх ідея заснована на підтримці в процесі пошуку безлічі досягнутих станів і виборі на кожному кроці одного або декількох кращих станів.
 
Найпростіший з них — жодній пошук . Якщо його застосувати в задачі пошуку найкращого шляху в графі, це дасть відомий алгоритм Дейкстри . Жадібний пошук, вибираючи стан, з якого буде продовжуватися пошук, шукає стан з найкращою оцінкою шляху від початкового в дане. Тому він і називається «жадібним» — оскільки «вистачає» найкраще на даний момент стан, не думаючи про наслідки. Природно, як і багато жадібні алгоритми, така стратегія не призводить до оптимального рішення. Кінцеві стану часто досягаються занадто довгим, неоптимальним шляхом. Крім того, жадібний пошук постійно повинен підтримувати безлічі всіх досягнутих станів, яких може бути занадто багато, від чого надмірно витрачається пам'ять.
 
 Алгоритм променевого пошуку і алгоритм А * — це спроби поліпшити поведінку жодного пошуку і виправити ці дві властиві йому проблеми. Променевої пошук працює таким чином: на кожному кроці ми підтримуємо деякий безліч з N кращих станів. Далі з кожного з цих станів робимо всі можливі кроки і отримуємо безліч станів наступного покоління. У цій безлічі ми видаляємо дублікати, тобто однакові стану. Оцінюємо залишилися і сортуємо в порядку погіршення оцінки. Далі вибираємо N кращих, і так до тих пір, поки ми не знайдемо цікавить нас кінцевий стан.
 
У променевого пошуку є свої достоїнства і недоліки. Основною його мінус в тому, що, на відміну від жодного, променевої пошук не гарантує знаходження кінцевого стану з найкращою якістю, тому що в процесі руху фронту кращий стан може з нього випасти. На практиці з цим можна боротися, налаштовуючи ширину фронту. Чим фронт вже, тим швидше працює алгоритм, але тим частіше він помиляється. Чим ширше фронт, тим алгоритм працює краще, але довше. Це одне з його важливих переваг — можливість легко балансувати між швидкістю і якістю. Променевої пошук дуже популярний в академічному середовищі, особливо серед китайських вчених. Він простий у реалізації і працює досить непогано.
 
Ідея алгоритму А * полягає у тому, що ми вибираємо на кожному кроці не найкраще, а найбільш перспективне на даний момент стан. Той стан, через яке з найбільшою ймовірністю проходить шлях до кращого кінцевого стану.
 
До оцінки поточного стану в алгоритмі А * додається евристична оцінка знизу залишку шляху до кінцевого стану. Якщо евристична оцінка знизу досить хороша, то А * працює ефективно і швидко знаходить найкращий стан. У цьому випадку А * буде поліномінальної по числу кроків, а не експоненціальним. А * — це дійсно хороший алгоритм, у своїй роботі я використовую його набагато частіше, ніж променевої пошук.
<Img src="http://habrastorage.org/getpro/habr/post_images/5d2/f89/f84/5d2f89f84538cb75f598125725ea0711.gif" title = "Пошук шляху за допомогою алгоритму А *" />
Недоліком алгоритму А * є необхідність придумати евристику. Справедливості заради треба сказати, що в багатьох задачах ця евристика знаходиться досить легко і природно. У таких завданнях і рекомендується використовувати А *. Якщо евристику придумати не виходить, тоді на допомогу вам приходить променевої пошук.
 
У третьому пості даної серії мова піде про способи отримання знань, використовуваних при створенні штучного інтелекту, а також про машинному навчанні — зокрема, про ті методи, які використовуються в FineReader.
  
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.