2.2. Алгоритм a*

Існує добре відомий алгоритм пошуку, який відноситься до групи перший кращий, що одержав назву А* (вимовляється "А з зірочкою"). Основна ідея алгоритму складається у використанні для кожного вузла на графі простору станів оцінної функції виду:

f(n)=g(n)+(n)

Тут g (п) відповідає відстані на графі від вузла n до початкового стану, a h(n) — оцінка відстані від n до вузла, який представляє кінцевий (цільовий) стан. Чим менше значення оцінної функції f(n), тим "краще", тобто вузол п лежить на більш короткому шляху від вихідного стану до цільового. Ідея алгоритму полягає в тому, щоб за допомогою f(n) відшукати найкоротший шлях на графі від вихідного стану до цільового

Звідси випливає що якщо h(n) — нижня оцінка дійсної відстані до цільового стану, тобто якщо h(n) ніколи не дає завищеної оцінки відстані то алгоритм А* завжди відшукає оптимальний шлях до мети за допомогою оцінної функції f(n). Алгоритм, який володіє такою властивістю, називається розв'язним (більш докладне обговорення цього питання читач знайде в спеціальній літературі, зокрема в роботах Нільсона [Nilsson, 1980, Chapter 2] і Перла [Pearl, 1984, Chapter2]).

Позначення:

s-вузол початкового стану,

g-вузол цільового стану,

OPEN — список, що містить обрані, але неопрацьовані вузли;

CLOSED—список, що містить оброблені вузли;

Алгоритм

(1) OPEN={s}

(2) Якщо OPEN =(} то припинити виконання шляху до цільового стану на графі не існує.

(3) Видалити зі списку OPEN вузол n, для якого f(n)sf(mj для будь-якого вузла т, що уже присутні у списку OPEN, і перенести його в список CLOSED

(4) Сформувати список чергових вузлів, у який можливий перехід з вузла n, і видалити з нього усі вузли, що утворять петлі; з кожним із що залишилися i пов’язати показник на вузол п.

(5) Якщо в сформованому списку чергових вузлів присутній g, то завершити виконання. Сформувати результат — шлях, породжений простежуванням покажчиків від вузла n до вузла s.

(6) У противному випадку для кожного чергового вузла n, включеного в список, виконати наступну послідовність операцій.

Обчислити f(n')

• Якщо n' не є присутнім ні в списку OPEN, ні в списку CLOSED, додати його в список, приєднати до нього оцінку f(n') і встановити зворотний показник на вузол n.

• Якщо n' уже є присутнім у списку OPEN чи в списку CLOSED, порівняти нове значення f(n')=new c колишнім f(n')=old.

Якщо old<new, припинити обробку нового вузла.

Якщо new<old, замінити новим вузлом колишній у списку, причому, якщо колишній вузол був у списку CLOSED, перенести його в список OPEN.

Кінець алгоритму

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

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

Достатньо скурпульозні результати перших досліджень в області програмування ігор і машинного доказу теорем описані в збірнику статей за редакцією Фейгенбаума і Фельдмана [Feigenbaum and Feldman, 1963]. Я схильний до того, щоб вважати "класичним" в історії штучного інтелекту період, що почався з публікації в 1950 році статті Шеннона про гру в шахи [Shannon, 1950] і закінчився виходом збірника Фейгенбаума і Фельдмана. Найбільш істотні результати, отримані в цей період, можна сформулювати в такий спосіб:

• проблему будь-якої складності, в принципі, можна звести до проблеми пошуку в просторі станів, якщо тільки вдається з неї формалізувати в термінах початкового стану, кінцевого стану й операцій переходу в просторі станів;

• пошук у просторі станів повинен направлятися певним чином представленими знаннями про конкретну предметну область.

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