Пошук за критерієм вартості: відмінності між версіями
[неперевірена версія] | [неперевірена версія] |
Вилучено вміст Додано вміст
мНемає опису редагування |
IvanBot (обговорення | внесок) м →Складність алгоритму: replaced: більш корисні → корисніші |
||
Рядок 13:
Пошук за критерієм вартості направляється з врахуванням вартості шляхів, а не значень глибини в [[Дерева пошуку|дереві пошуку]], тому його [[Обчислювальна складність|складність]] не може бути легко охарактеризована в термінах b (коєфіцієнт розглалудження або максимальна кількість нащадків будь-якого вузла) і d (глибина найбільшповерхневого цільового вузла). Замість цього припустимо, що С — вартість оптимального розв'язку, і припустимо, що вартість кожної дії складає, меншою мірою, ε.
Це означає, що [[Обчислювальна складність|часова і просторова складність цього алгоритму]] в найгіршому випадку складає O(b<sup>1+[c/8]</sup>), тобто може бути набагато більша, ніж b<sup>4</sup>. Це пов'язано з тим, що процедури пошуку за критерієм вартості можуть і часто виконують перевірку великих дерев, що складаються з дрібних етапів, перш ніж перейти до дослідження шляхів, в які входять великі, і, можливо,
== Посилання ==
|