Поиск по критерию стоимости

Поиск в ширину является оптимальным, если стоимости всех этапов равны, поскольку в нем всегда развертывается самый поверхностный неразвернутый узел. С помощью простого дополнения можно создать алгоритм, который является оптимальным при любой функции определения стоимости этапа. Вместо развертывания самого поверхностного узла поиск по критерию стоимости обеспечивает развертывание узла п с наименьшей стоимостью пути. Обратите внимание на то, что, если стоимости всех этапов равны, такой поиск идентичен поиску в ширину.
При поиске по критерию стоимости учитывается не количество этапов, имеющихся в пути, а только их суммарная стоимость. Поэтому процедура этого поиска может войти в бесконечный цикл, если окажется, что в ней развернут узел, имеющий действие с нулевой стоимостью, которое снова указывает на то же состояние (например, действие NoOp). Можно гарантировать полноту поиска при условии, что стоимость каждого этапа больше или равна некоторой небольшой положительной константе 8. Это условие является также достаточным для обеспечения оптимальности. Оно означает, что стоимость пути всегда возрастает по мере прохождения по этому пути. Из данного свойства легко определить, что такой алгоритм развертывает узлы в порядке возрастания стоимости пути. Поэтому первый целевой узел, выбранный для развертывания, представляет собой оптимальное решение. (Напомним, что в процедуре Tree-Search проверка цели применятся только к тем узлам, которые выбраны для развертывания.) Рекомендуем читателю попытаться воспользоваться этим алгоритмом для поиска кратчайшего пути до Бухареста.
Поиск по критерию стоимости направляется с учетом стоимостей путей, а не значений глубины в дереве поиска, поэтому его сложность не может быть легко охарактеризована в терминах Ь и d. Вместо этого предположим, что С* — стоимость оптимального решения, и допустим, что стоимость каждого действия составляет, по меньшей мере, 8. Это означает, что временная и пространственная сложность этого алгоритма в наихудшем случае составляет 0(b v ), т.е. может быть намного больше, чем bd. Это связано с тем, что процедуры поиска по критерию стоимости могут и часто выполняют проверку больших деревьев, состоящих из мелких этапов, прежде чем перейти к исследованию путей, в которые входят крупные, но, возможно, более полезные этапы. Безусловно, если все стоимости этапов равны, то выражение ь1+1-с*/е-1 равняется bd.







Материалы

Яндекс.Метрика