46749 (571861), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

Рассмотрим задачу нахождения оптимума функции f(x) на допустимом множестве G. Пусть х* – оптимальное решение этой задачи. Говорят, что допустимое решение х является -приближенным, если

(3)

где > 0 - заданное число (f(x*j ≠ 0).

Величина > 0 есть гарантированная характеристика приближенного алгоритма и, если для любой реализации задачи алгоритм дает приближенное решение х и выполняется неравенство (3). Сравнение приближенных алгоритмов проводится на основании гарантированных характеристик, которые позволяют выбрать оптимальный в определенном смысле эвристический алгоритм решения задачи.

Различные типы экстремальных задач из класса NPC ведут себя при нахождении -приближенного решения по-разному. Например, поиск -приближенного решения задачи коммивояжера снова представляет собой задачу класса NPC; дня задачи же о ранце и некоторых других приближенных задач существуют алгоритмы поиска -приближенного решения с полиномиальной сложностью. Таким образом, перспективным направлением повышения эффективности комбинаторных алгоритмов является выявление подклассов задач из класса NPC, для которых поиск -приближенных решений переводит их в класс Р.

Для задач массового счета перспективным является применение статистически эффективных алгоритмов. Такие алгоритмы в подавляющем большинстве случаев оптимальны ( -приближенное решение). Иначе говоря, с ростом размерности задачи доля точно оптимизируемых задач ( -оптимизируемых) среди всех задач стремится к 1.

При оценке эффективности алгоритмов теоретическими методами следует иметь в виду, что полученные результаты дают представление о поведении задач в наихудших возможных случаях, тогда как для вычислительной практики существенно более важно их поведение в среднем. Действительно, экспериментально известно, что для решения задачи линейного программирования с m ограничениями и п переменными обычно требуется от m до 3т итераций; как правило, для задач не слишком больших размеров число итераций близко к 3m/2. Кроме того, теоретические результаты практически ничего не говорят о том, как будет вести себя конкретный алгоритм на конкретной задаче. Например, среднее время прямого поиска в списке пропорционально N/2, где N - число элементов списка, а двоичного поиска (список упорядочен по ключу) – пропорционально log₂N. Однако двоичный поиск неэффективен для небольших списков, которые подлежат частому изменению, так как введение нового элемента может вызвать переписывание всех элементов. Разработка алгоритмов является в основном творческой деятельностью, хотя существует множество типовых методов и алгоритмов, которые могут применяться для решения задач, возникающих в АСУ. К таким методам прежде всего относятся методы исследования операций.

Наиболее разработанными приближенными методами решения экстремальных задач являются комбинаторные методы, основная идея которых состоит в использовании конечности множества решений и в замене полного перебора направленным перебором. При этом главную роль в сокращении перебора играет оценка и отбрасывание неперспективных (т.е. заведомо не содержащих оптимума) подмножеств решений. Общая схема комбинаторных методов (методы типа схемы "ветвей и границ") применима практически ко всем задачам дискретного программирования независимо от их линейности или иных свойств. Эта схема может быть применена непосредственно к исходной естественной формулировке экстремальной задачи, без сведения ее к целочисленной задаче линейного программирования. Кроме того, эти методы чаще всего обеспечивают конечность вычислительного процесса по самому своему построению.

Долгое время единственным способом оценки эффективности комбинаторных методов являлось численное экспериментирование. Основной тенденцией, выявленной в достаточно представительных сериях экспериментов, является тенденция к экспоненциальному возрастанию трудоемкости вычислений при росте числа переменных. Теоретические исследования комбинаторных задач также приводят к заключению об экспоненциальной трудоемкости решения комбинаторных задач. Однако практика показывает, что комбинаторные методы позволяют решать задачи АСУ достаточно больших размеров.

Использование комбинаторных методов типа "ветвей и границ" положено в основу стандартного пакета ЛП АСУ (для решения задач линейного программирования).

Характеристики

Список файлов ответов (шпаргалок)