Пошук за критерієм вартості: відмінності між версіями

Пошук в ширину є [[Оптимальність|оптимальним]], якщо вартості всіївсіх етапів однакові, оскільки в ньому завжди розгортається найбільшповерхневийнайбільш поверхневий нерозгорнутий вузол.<br />

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

При пошуку за критерієм вартості враховується не кількість етапів, що вже наявні в шляху, а тільки їх сумарна вартість. Тому процедура цього пошуку може ввійтиувійти в нескінченний [[Цикл (програмування)|цикл]], якщо виявиться, що в ній розгорнутий вузол, що має дію з нульовою вартістю, які знову вказують на той же стан (наприклад, дія NoOp). Можна гарантувати [[Повнота алгоритмів пошуку|повноту пошуку]] за умови, що вартість кожного етапу більше або дорівнює деякій невеликій додатній константі ε. Ця умова є також і достатньою для забезпечення [[Необхідна і достатня умова|оптимальностідостатньою]] для забезпечення оптимальності. Вона означає, що вартість шляху завжди зростає по мірі проходження по цьому шляху.<br />

Із заданої властивості легко визначити, що такий алгоритм розгортає шляхи в порядку зростання вартості шляху. Тому перший цільовий вузол, обраний для розгортання, представляє собою оптимальний розв'язок. (Нагадаємо, що в процедурі [[Дерева пошуку|Tree-Searchпошуку в дереві]] перевірка цілі застосовується лише до тих вузлів, які обрані для розгортання.)<br />

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