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