Повна версія

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

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


<<   ЗМІСТ   >>

ПОРІВНЯННЯ ВАРІАНТІВ АЛГОРИТМУ Л *

Розглянемо два варіанти алгоритму А * для одного і того ж простору станів деякої задачі:

  • - алгоритм А, * з оціночної функцією f (n) = g t (n) + Л, (л), / г, (я) < h * (n),
  • - алгоритм А 2 * з оціночної функцією / 2 (і) = g 2 (n) + h 2 (n), h 2 (n)

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

Визначення. Алгоритм А 2 * називається більш поінформованим, ніж алгоритм А якщо для всіх нецільових вершин виконується нерівність / 7, (і) 2 (п).

Наступна теорема констатує велику ефективність більш інформованого варіанту алгоритму А *.

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

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

Прикладом, що підтверджує цю теорему, може служити гра «Вісім», якщо для алгоритму А, * прийняти h, (S) = 0, а для алгоритму А 2 * прийняти h 2 (S), що дорівнює кількості фішок в стані S, стояти не на своїх місцях в порівнянні з цільовим станом S ,. Тоді алгоритм А, * представляє собою звичайний пошук в ширину. Це означає, що кожна вершина, розкрита алгоритмом Л 2 *, виявляється обов'язково розкритою також алгоритмом А, *, так як пошук в ширину розкриває абсолютно всі вершини простору станів, якщо відшукуються всі вирішальні шляхи.

 
<<   ЗМІСТ   >>