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

Cтраница 1

Комбинаторные алгоритмы предназначаются для выполнения вычислений на дискретных конечных математических структурах. [1]

Комбинаторные алгоритмы, связанные с перебором всего множества элементов А, как правило, неприемлемы из-за большого размера задачи. Поэтому используются приближенные алгоритмы компоновки последовательного, последовательно-параллельного или итерационного типа. [2]

Излагаются современные комбинаторные алгоритмы для решения задач дискретной оптимизации с применением компьютерных средств. Основное внимание уделяется вычислительной реализации алгоритмов. Приводятся результаты вычислительного исследования алгоритмов для классических задач дискретной оптимизации - задачи о ранце и задачи о коммивояжере. Приведено много примеров для самостоятельной работы. [3]

В комбинаторных алгоритмах нам часто придется встречаться с представлениями конечных последовательностей ( или начальных сегментов бесконечных последовательностей) и операциями над ними. В данном разделе рассматриваются различные способы таких представлений и различные операции. [4]

В комбинаторных алгоритмах часто необходимо порождать и исследовать все элементы некоторого класса комбинаторных объектов. [5]

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

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

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

Раздел II посвящен изложению комбинаторных алгоритмов, наиболее часто применяемых при решении задач. Здесь рассматриваются метод ветвей и границ и метод динамического программирования. После изложения общих алгоритмов дано их описание для стандартных задач, сопровождаемое большим числом примеров. [9]

Примеры функции CIR ( е, Т. [10]

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

Задача поиска является фундаментальной в комбинаторных алгоритмах, так как она формулируется в такой общности, что включает в себя множество задач, представляющих практический интерес. При самой общей постановке: Исследовать множество Т с тем, чтобы найти элемент, удовлетворяющий некоторому условию С, о задаче поиска едва ли можно сказать что-либо стоящее. Удивительно, однако, что достаточно незначительных ограничений на структуру множества Т, чтобы задача стала интересной: возникает множество разнообразных стратегий поиска различной степени эффективности. [12]

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

Этот отчет является превосходным примером методологии анализа комбинаторного алгоритма. Наше изложение быстрой сортировки основано на отчете Седгевика. [14]

Универсальность компьютерной системы ФЛАМИНГО достигается вследствие использования общего комбинаторного алгоритма, в ходе которого могут быть генерированы самые различные химические реакции или стадии реакции, в том числе совершенно новые и малоизученные процессы. Данная система может быть использована для компьютерного синтеза, изучения перегруппировок, предсказания механизмов сложных многоступенчатых реакций. При использовании данной системы наиболее важные типы органических реакций формально описываются как результат циклического перераспределения связей ( ЦПС) в исходной химической системе, в результате которого образуется конечная химическая система. [15]

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