Повна версія

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

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


<<   ЗМІСТ   >>

АЛГОРИТМ / 4 *

Цей алгоритм є різновидом евристичного пошуку, коли евристична інформація виражена у формі оціночної функції / (•), визначеної на множині вершин графа, що представляє простір станів. Нехай N = {л ,, п 2 , ..., п г } - безліч вершин, a L = {/ ,, / 2 , / 5 } - безліч дуг графа, що представляє собою простір станів розв'язуваної задачі. Будемо вважати, що для будь-якої дуги / = (л " nj) е L визначено число з (л" tij), яке назвемо вартістю цієї дуги. Початкову вершину позначимо символом п 0 , а цільову вершину - символомt або t h якщо є кілька цільових вершин.

Визначимо оціночну функцію / (•) таким чином, щоб її значення / (/?) Для вершини п було оцінкою суми двох величин: мінімальної вартості шляху від вихідної вершини п 0 до вершини п і мінімальної вартості шляху від вершини п до деякої цільової вершині t або t r Якщо першу з вартостей позначити # * (я), а другу - а * (л), то наше припущення про визначення оціночної функції f (n) полягає в тому, щоб вважати / (я) деякої оцінкою для «ідеальної» оціночної функції f * (n) = g * (n) + h * (n). Функція / * (я), отже, дорівнює мінімальній вартості вирішального шляху за умови, що цей шлях проходить через вершину п. Функції g * (n) і І * {п) можна визначити через функцію c (n h п) наступним чином:

Тут у формулі для g * (n) мінімум обчислюється за всіма шляхами {1 а } пп, що починається в початковій вершині п 0 і закінчується в вершині л, а у формулі h * (л) зовнішній мінімум обчислюється по всіх цільових вершин t h а внутрішній мінімум - за всіма шляхами {/ «}" '', що починається в вершині п і закінчується в цільової вершині t r Позначення {1 а } " використовується для довільного шляху, який починається в вершині т і закінчується в вершині п.

Використання цих двох формул для обчислення значень функцій # * (л) і А * ( п ) в довільній вершині п на практиці, на жаль, виявляється недоцільним через необхідність реалізації повного перебору вершин і шляхів до виконання самого евристичного пошуку. Правда, в деяких рідкісних випадках вони можуть бути обчислені a priori , без виконання повного перебору, виходячи з умов розв'язуваної задачі. У цих рідкісних випадках в якості оціночної функції / (•) слід використовувати функцію / * (-). Тоді евристичний пошук забезпечує розкриття найменшого числа вершин-кандидатів і найбільш швидко призводить до побудови оптимального вирішального шляху.

У загальному випадку оціночну функцію визначимо співвідношенням / (і) = -g (n) + h (n), де ^ (л) є деякою оцінкою (наближенням) функції g * (n), а І (п) - оцінкою (наближенням ) функції h * (n). В якості оцінки g (n) можна вибрати сумарну вартість дуг шляху {1 а } "" про , що веде з вершини п 0 в вершину п, т. Е. Можна покласти

У цьому способі завдання g (n) передбачається, що шлях {1 а } "" про - це той самий шлях, який реально був побудований в результаті евристичного пошуку. Ця величина g (n) можливо не є найменшою, так як # (п )> g * (n) щодо визначення функції g * (n), але вона цілком може бути прийнята в якості оцінки функції g * (n).

Що стосується функції h (n), що є оцінкою функції /? * ( «), То саме для обчислення h (n) слід скористатися тією додатковою інформацією про завдання, яке називають евристичної інформацією. З цієї причини функція І (п) називається евристичної функцією. Як правило, про значення І (п) буває складно сказати щось певне до закінчення пошуку, так як до моменту досягнення вершини п в ході евристичного пошуку про шляхи, що ведуть з вершини п, практично буває нічого не відомо. Способи обчислення евристичної функції h (n) можуть бути різними в залежності від умов конкретної розв'язуваної задачі.

Якщо в умовах задачі достатньо інформації для обчислення відстані Хеммінга - «відстані» між даною вершини п і цільової вершиною t, - то доцільно відстань Хеммінга прийняти в якості значень евристичної функції h (n). Наведемо два приклади, що пояснюють поняття «відстань Хеммінга».

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

У другому прикладі розглянемо гру «Вісім», в якій потрібно перейти від деякого початкового розташування фішок S 0 до кінцевого розташуванню фішок S, за найменше число ходів. За відстань Хеммінга тут можна прийняти число фішок в поточному їх розташуванні S, що стоять не на своїх місцях в порівнянні з кінцевим розташуванням фішок S ,. Якщо в обох цих прикладах як І (п) прийняти відстань Хеммінга, то евристичний пошук пройде успішно і найкоротший вирішальний шлях буде знайдений, якщо взагалі існує хоч який-небудь вирішальний шлях. Зауважимо, що в цих прикладах евристична функція І {п) оцінює ідеальну евристичну функцію h * (n) знизу, т. Е. Виконується співвідношення h (n)

У загальному випадку відстань Хеммінга - це метрика в деякому метричному просторі. Для випадку алгоритму А * відстань Хеммінга - це метрика, визначена на множині N всіх вершин графа, що представляє простір станів, тобто функція d (n, т), де neN і m & N, що володіє властивостями:

1) d (n, т) > 0 для всіх neNі meN,

d (n, т) = 0 тоді і тільки тоді, коли п = т,

  • 2) d (n, т) = d (т, п) для всіх n & N і meN (симетричність),
  • 3) d (i 1 , m)для всіх л, т, psN (нерівність трикутника).

Евристичний пошук, який використовує оціночну функцію /) /;) = g (n) +

+ H (n), в якій /; ( «) </; * («) для всіх нецільових вершин, називається алгоритмом А *. Цей же пошук за відсутності обмеження h (n) <h * (n) називається алгоритмом А. В алгоритмах А і А * функція g (n) є деякою оцінкою функції g * (n). В обох алгоритмах з безлічі альтернативних вершин-кандидатів для продовження пошуку вибирається та, для якої значення /) /;) є найменшим.

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

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

 
<<   ЗМІСТ   >>