Пошук за критерієм вартості

По́шук за крите́рієм ва́ртості — це модифікація алгоритму пошуку в ширину.

Суть алгоритму

Пошук в ширину є оптимальним, якщо вартості всіх етапів однакові, оскільки в ньому завжди розгортається найбільш поверхневий нерозгорнутий вузол.

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

При пошуку за критерієм вартості враховується не кількість етапів, що вже наявні в шляху, а тільки їх сумарна вартість. Тому процедура цього пошуку може увійти в нескінченний цикл, якщо виявиться, що в ній розгорнутий вузол, що має дію з нульовою вартістю, які знову вказують на той же стан. Можна гарантувати за умови, що вартість кожного етапу більше або дорівнює деякій невеликій додатній константі ε. Ця умова є також і достатньою для забезпечення оптимальності. Вона означає, що вартість шляху завжди зростає по мірі проходження по цьому шляху.

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

Складність алгоритму

Пошук за критерієм вартості направляється з врахуванням вартості шляхів, а не значень глибини в дереві пошуку, тому його складність не може бути легко охарактеризована в термінах b (коефіцієнт розгалуження або максимальна кількість нащадків будь-якого вузла) і d (глибина найбільшповерхневого цільового вузла). Замість цього припустимо, що С — вартість оптимального розв'язку, і припустимо, що вартість кожної дії складає, меншою мірою, ε.

Це означає, що часова і просторова складність цього алгоритму в найгіршому випадку складає O(b^1+[c/8]), тобто може бути набагато більша, ніж b⁴. Це пов'язано з тим, що процедури пошуку за критерієм вартості можуть і часто виконують перевірку великих дерев, що складаються з дрібних етапів, перш ніж перейти до дослідження шляхів, в які входять великі, і, можливо, корисніші етапи. Безумовно, якщо всі вартості етапів однакові, то вираз b^1+[c/8] дорівнює bd.

Посилання

• «История компьютера — Поиск по критерию стоимости» (рос.)

Див. також

• Список алгоритмів
• Обхід дерева
• Пошук в глибину
• Пошук у ширину
• Теорія графів