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

Алгоритм

(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] і закінчився виходом збірника Фейгенбаума і Фельдмана. Найбільш істотні результати, отримані в цей період,можна сформулювати в такий спосіб:

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

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

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

Дата добавления: 2014-01-11