Cтраница 4
Программа строит решающее дерево ( если таковое существует), рассчитывая на то, что оно окажется оптимальным решением. Будет ли это решение в действительности самым дешевым, зависит от той функции / г, которую использует алгоритм. Существует теорема, в которой говорится о том, как оптимальность решения зависит от А. Эта теорема аналогична теореме о допустимости алгоритма поиска с предпочтением в пространстве состояний ( гл. Обозначим через С ( В) стоимость оптимального решающего дерева для вершины В. Если для каждой вершины В И / ИЛИ-графа эвристическая оценка h ( B) s C ( B), то гарантируется, что процедура и нли найдет оптимальное решение. Если же h не удовлетворяет этому условию, то найденное решение может оказаться субоптимальным. Существует тривиальная эвристическая функция, удовлетворяющая условию оптимальности, а именно А 0 для всех вершин. Ее недостатком является отсутствие эвристической силы. [46]