Повна версія

Головна arrow Природознавство arrow ІНТЕЛЕКТУАЛЬНІ СИСТЕМИ

  • Увеличить шрифт
  • Уменьшить шрифт


<<   ЗМІСТ   >>

ЕВРИСТИЧНИЙ ПОШУК

Стратегії пошуку в глибину і в ширину доцільно використовувати для побудови вирішальних шляхів в просторі станів тоді, коли пошук здійснюється без додаткової інформації про розв'язуваної задачі. Інакше кажучи, коли єдиною інформацією, наявною в розпорядженні, є списки вершин N = {n b п 2 , ..., я ,.} і дуг ? = {/ ,, / 2 , I s ] простору станів і більше нічого. Тут 1 до = (%, n jk ) позначає ребро, спрямоване з вершини п, до в вершину n jk .

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

У багатьох випадках є можливість використовувати деяку додаткову інформацію, що стосується даної задачі, щоб сприяти скороченню пошуку, т. Е. Скорочення часу і обсягу пам'яті, необхідних для виконання пошуку. Інформацію такого роду (будь-яка додаткова до множинам N і L інформація) називають евристичної. Стратегія пошуку, яка використовує евристичну інформацію, називається евристичним пошуком. Процедура вибору альтернативних вершин, що враховує евристичну інформацію про завдання, називається евристикою. Часто евристичну інформацію знаходять, проводячи поглиблене дослідження умов завдання, будуючи теорію рішення відповідних завдань.

Додаткова (евристична) інформація про завдання в деяких випадках може бути виражена чисельно в формі оціночної функції / ( «), визначеної на вершинах простору станів, т. Е. На безлічі N. Оціночна функція / (•) вершині п простору станів зіставляє дійсне число f (n), що розглядається як оцінка перспективності (перевагу) продовження пошуку з вершини п. чим менше (а в деяких завданнях - чим більше) значення f (n), тим краще (перспективніше) продовження пошуку з вершини п. Ось чому еврістічес кий пошук іноді називають пошуком з перевагою.

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

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

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

Існує цілий ряд методів евристичного пошуку, заснованих на використанні оцінної функції і об'єднаних в одну групу, звану градієнтними методами. Іноді градієнтні методи називають «взбіранія на гору» ( «підйом в гору»). Суть градієнтних методів пояснимо двома прикладами:

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

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

 
<<   ЗМІСТ   >>