Комбинаторные методы с оценочными функциями

У.5. КОМБИНАТОРНЫЕ МЕТОДЫ l ot] С ОЦЕНОЧНЫМИ ФУНКЦИЯМИ [c.143]

К таким комбинированным методам относятся методы, предложенные в работах [42, 51 ]. Разница между работами состоит в том, что на нижнем уровне применяются различные комбинаторные подходы. В работе [42] применяется метод поиска на дереве вариантов с оценочной функцией. На этом методе мы подробно остановимся в разд. 1У.5.7. В работе [51 ] на нижнем уровне решается задача о назначениях. На верхнем уровне интервал температур от до Гк делится на т подинтервалов Т ,. .., Гг т-1, г.к и [c.147]

Как было показано в разд. IV.5.4, дальнейшего сокращения дерева вариантов по сравнению с методом, который использует граничную оценку (IV.52), можно достичь, используя более точную, чем (IV.52), оценку для (Эб.шх в данной вершине s). Как правило, для комбинаторных задач оценка более точная, чем граничная оценка, теряет свойство быть границей. Если бы для какой-то комбинаторной задачи удалось построить достаточно точную оценку критерия оптимизации, да еще являющуюся верхней (или нижней) границей для значений критерия оптимизации, тогда решение этой задачи методом, изложенным в разд. IV.5.7 (см. рис. IV.33), могло бы происходить за один проход . Иными словами, на каждом уровне дерева вариантов выбиралась бы одна вершина с максимальной оценочной функцией, уменьшение оценочной функции по мере увеличения глубины дерева было бы маловероятным, поэтому маловероятным был бы и возврат на предыдущие уровни дерева к вершинам с большим, чем текущее, значением оценочной функции. Другими словами, число висячих вершин было бы равно минимальному iVvmm. дерево имело бы минимальное число ветвей, а целенаправленность поиска Р = N /N ,т была бы максимально высока для данного алгоритма поиска. [c.167]

Справочник химика 21

Химия и химическая технология