Cтраница 2
Отметим также, что методы локальной оптимизации являются эффективными лишь в том случае, когда допустимое решение задачи (5.1.1) находится достаточно просто. Если же нахождение допустимого решения является сложной задачей, то алгоритмы локальной оптимизации малоэффективны. [16]
Эти методы широко применяются при решении задач вида (1.1.1), так как нахождение точного решения может потребовать значительных вычислительных ресурсов. Современные приближенные методы обычно являются комбинированными, т.е. содержат в себе элементы различных методов. В приближенных методах решение задачи производится обычно в два этапа: построение начального решения и улучшение начального решения. При этом на первом этапе широко используются эвристические алгоритмы - алгоритмы, основанные на правдоподобных, но не обоснованных строго предположениях о свойствах оптимального решения задачи. Примером эвристического алгоритма может быть алгоритм решения задачи коммивояжера, в котором на каждом шаге реализуется переход в ближайшую из оставшихся точку. Эти алгоритмы на каждом шаге решают локальную задачу оптимизации; полученное решение может быть сколь угодно далеким от оптимума. На втором этапе используются алгоритмы локальной оптимизации, связанные с введенным понятием окрестности; при этом можно использовать несколько алгоритмов этого типа, изменяя правила выбора окрестности. [17]