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

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

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

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

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

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

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