Комбинаторный алгоритм

Cтраница 2

В наибольшей степени структуре задач размещения и компоновки соответствуют комбинаторные алгоритмы: переборные, последовательные, итерационные, смешанные и эвристические. [16]

Предполагается, что в процессе решения задачи каким-либо из комбинаторных алгоритмов вычисляется значение функции f ( x) для всех х GO С G, GQ NQ, G N, 0 N0 N. Все точки ( варианты) из множества G Go отбракованы по каким-либо правилам отсева. Обозначим через SQ время, необходимое для вычисления одного значения / ( ж), через si среднее время реализации отсева одного варианта ( точки) х 6 G Go; Т ( Go), Т ( G Go) и Т ( G) - времена для вычисления всех значений / ( ж), х GO, для реализации отсева всех х G Go и для полного перебора соответственно. [17]

Итак, основной целью данного учебного пособия является изложение современных комбинаторных алгоритмов для практического решения задач дискретной оптимизации. При этом вовсе не ставится цель разработать такой алгоритм, который решает любую задачу ( например, задачу коммивояжера) с любой заранее заданной точностью: такая цель недостижима, что следует непосредственно из результатов, полученных в теории сложности алгоритмов. Для задачи коммивояжера необходимо разработать алгоритм, расширяющийся с учетом особенностей задачи и позволяющий получить приближенное решение с оценкой отклонения от оптимума. Существуют задачи из класса NP ( например, общая задача частично целочисленного линейного программирования), для которых даже эта цель недостижима, так как трудоемкость получения хотя бы одного допустимого решения сравнима с трудоемкостью нахождения оптимального решения. [18]

На практике этот вероятностный алгоритм работает несколько медленнее, чем комбинаторные алгоритмы для нахождения паросочетаний ( см. гл. [19]

Книга предназначена для программистов, желающих расширить свои знания в области комбинаторных алгоритмов, а также пополнить свои практические знания теоретическими. От читателя требуются элементарные сведения из математики, а также знакомство с языком программирования Паскаль [ 36, 75J и некоторый опыт программирования на языке высокого уровня. [20]

Когда появились программно-управляемые вычислительные машины, задачи сортировки стали наиболее важными из комбинаторных алгоритмов и именно на них были потрачены значительные усилия. [21]

Алгоритмы компоновки и размещения включают в себя алгоритмы, реализующие методы математического программирования и комбинаторные алгоритмы. [22]

Дерево с 11 узлами, помеченными буквами от А до К. Узлы с метками D, Е, F, H, J и / С являются листьями. другие узлы внутренние. Узел с меткой А - корень. [23]

Посредством деревьев изображаются иерархические организации, поэтому они являются наиболее важными нелинейными структурами данных в комбинаторных алгоритмах. [24]

В пособии приводятся основные понятия, необходимые при работе с разреженными матрицами, дается постановка ряда строительных задач, примеры построения комбинаторных алгоритмов их решения на ЭВМ на основе методов дискретной оптимизации. Рассматриваются способы хранения информации в оперативной памяти и на внешних носителях ЭВМ серии ЕС. [25]

Хотя комбинаторная математика является старой дисциплиной ( она получила свое наименование в 1666 г. от Лейбница и его Dis-sertatio de Arte Combinatoria), комбинаторные алгоритмы с их акцентом на разработку, анализ и реализацию практических алгоритмов являются продуктом века вычислительных машин. Ссылки на первые работы, касающиеся специальных вопросов этой области, будут даны в последующих главах, но список работ, носящих более общий характер, приводится ниже. [26]

В первом случае химические реакции должны быть заранее собраны в виде библиотеки, во втором случае для поиска трансформаций используют набор логических инструкций или комбинаторный алгоритм, непосредственно генерирующий трансформаций. [27]

Сейчас трудно было бы, пожалуй, назвать раздел теоретической информатики, в котором в течение последнего десятилетия были бы достигнуты большие успехи, нежели в конструировании и анализе комбинаторных алгоритмов. С одной стороны, было обнаружено много новых, более эффективных методов решения комбинаторных задач с помощью ЭВМ, с другой - получены теоретические результаты, свидетельствующие все более явно о том, что для широкого класса проблем не существует достаточно эффективных алгоритмов. Эффективные комбинаторные алгоритмы находят применение во многих областях нечисленной обработки информации, особенно в дискретной оптимизации и в исследовании операций. [28]

Читатель, который старательно проработал эту главу, начиная с тривиального алгоритма подсчета числа единиц в наборе, просматривающего все разряды по очереди, и кончая заполнением пробелов в выводе верхней оценки (1.4), имеет теперь общее представление о полном спектре комбинаторных алгоритмов. В частности, каждая тема, встречающаяся в этой книге, будет некоторым напоминанием принципов разработки алгоритмов, приведенных в разд. [29]

Курсы комбинаторных алгоритмов и примыкающие к ним курсы анализа алгоритмов теперь изучаются в колледжах и университетах на отделениях программирования, математики, электротехники и исследования операций. [30]

Страницы: 1 2 3 4