Cтраница 1
Задачи дискретной оптимизации - это задачи нахождения экстремума функции, заданной на дискретном ( чаще всего - конечном) множестве точек. Если область определения функции состоит из конечного числа точек, то задачу дискретной оптимизации всегда, в принципе, можно решить перебором всего этого множества. Однако на практике это множество хоть и конечно, но может быть очень велико, так что методы перебора не эффективны. Рассмотрим несколько общих подходов к решению задач дискретной оптимизации. [1]
Задачи дискретной оптимизации часто встречаются во всех сферах практической деятельности. Ограничимся здесь одним примером ( другие см. в гл. [2]
Для большинства задач дискретной оптимизации явный вид всех граней до настоящего времени не найден. Наиболее интересные результаты получены для многогранников задачи об упаковке, задачи о максимальном паро-сочетании графа, задачи коммивояжера, задачи о рюкзаке ( все они приводятся в гл. На принципиальную возможность получения такого описания указывает еще теорема Гильберта о конечном базисе кольца многочленов, однако эффективные методы до сих пор не получены. IV излагается подход к построению методов аналитического и параметрического описания целых точек многогранников, основанный на выделении порождающих множеств полугрупп. [3]
Z называется задачей дискретной оптимизации. [4]
В [13] рассматриваются задачи дискретной оптимизации, для решения которых применяется аппроксимационно-комбинаторный метод. [5]
Рассмотрим примеры двух задач дискретной оптимизации: задачу о ранце и задачу о коммивояжере. Эти задачи часто рассматриваются как тестовые при разработке алгоритмов решения задач дискретной оптимизации. [6]
Например, сложными являются задачи дискретной оптимизации, где точные алгоритмы имеют обычно экспоненциальную сложность и нереализуемы за приемлемое время. [7]
Алгоритмы и программы решения задач дискретной оптимизации / Сост. [8]
Существует несколько схем решения задач дискретной оптимизации. [9]
Очевидно, что в задачах дискретной оптимизации область допустимых решений ( или область работоспособности) D является невыпуклой и несвязной. [10]
Ограниченность возможностей точных методов решения задач дискретной оптимизации естественным образом приводит к идее разработки комбинированных алгоритмов, в которых объединялись преимущества методов и, по возможности, отсутствовали их недостатки. [11]
Как следует из общей постановки задач дискретной оптимизации, основное влияние на формальную постановку таких задач имеет пространство X, в котором рассматривается данная конкретная задача, что естественным образом отражается на способе ( алгоритме) ее решения. [12]
Учет ограничений типа неравенств в задаче дискретной оптимизации незначительно усложняет процедуру случайного поиска. [13]
Излагаются современные комбинаторные алгоритмы для решения задач дискретной оптимизации с применением компьютерных средств. Основное внимание уделяется вычислительной реализации алгоритмов. Приводятся результаты вычислительного исследования алгоритмов для классических задач дискретной оптимизации - задачи о ранце и задачи о коммивояжере. Приведено много примеров для самостоятельной работы. [14]
Одним из наиболее мощных методов решения задач дискретной оптимизации является метод последовательного анализа ваоиантов. В настоящем параграфе приводится общее описание метода последовательного анализа вариантов, придерживаясь работ [19, 20, 84], и иллюстрируются возможности его применения к некоторым задачам геометрического проектирования. [15]