Cтраница 3
Рассмотренные в этой главе комбинаторные схемы и методы позволяют формализовать отдельные этапы выбора целевой архитектуры на основе заданных спецификацией функций программных приложений. При этом применяются классические комбинаторные алгоритмы или их модификации. В случае синтеза описания архитектуры сеть строится для отыскания общей трансверсали Н семейств, что связано с Н вариантами начальной фрагментации спецификации программы. [31]
Для большинства комбинаторных задач не существует изящного и эффективного пути отыскания оптимального решения, такого, как алгоритм 1.5 для задачи о фальшивой монете. В этом отношении литература по комбинаторным алгоритмам зачастую вводит читателя в заблуждение, поскольку она сосредоточивает внимание на элегантных решениях, даже если они применяются только к отдельным задачам. Красивые решения часто страдают большим пороком: если задачу слегка изменить, решение становится неприменимым. [32]
Изложенное означает, что для того чтобы применить в данном случае метод ветвей и границ необходимо сначала сформировать указанные матрицы для всех возможных сочетаний ( h v), i и у, а потом уже реализовывать этот метод. Поэтому в данном случае эффективнее применить следующий эвристический комбинаторный алгоритм, позволяющий получить оптимальное решение в ходе генерации допустимых вариантов решения задачи. [33]
Мир, 1977), написанной совместно с Дж. В данной книге предпринята попытка систематизации комбинаторных алгоритмов, выявления их общих черт и закономерностей. Подробно рассматриваются конкретные задачи использования комбинаторных алгоритмов, в частности очень важная для. Каждая глава сопровождается достаточно подробной исторической справкой и большим числом упражнений. [34]
Понятие рекуррентных соотношений проиллюстрируем на классической проблеме, поставленной и изученной около 1200 года Леонардо из Пизы, известным как Фибоначчи. Удивительная важность чисел Фибоначчи для анализа комбинаторных алгоритмов делает этот пример весьма подходящим. [35]
Действительно, остроумные приемы играют здесь известную роль и, для того чтобы проиллюстрировать это, в данной главе мы рассмотрим некоторые примеры техники игры на двоичности. Однако, после того как было исследовано много комбинаторных алгоритмов, стали вырисовываться некоторые общие принципы. Именно эти принципы делают комбинаторные вычисления связной областью знаний и позволяют изложить ее в систематизированном виде. [36]
Рекомендуем читателю доказать, что в общем виде предложенный алгоритм корректен. Этот принцип является хорошей иллюстрацией нашего утверждения о том, что комбинаторные алгоритмы имеют общие идеи и методы, из которых следуют многие частные случаи. [37]
Случай 6 подробно рассмотрен в разд. Это рассуждение иллюстрирует эмпирическое правило, которое удивительно часто присутствует в комбинаторных алгоритмах. [38]
Такая, кажущаяся на первый взгляд надуманной, задача чрезвычайно полезна в определенных комбинаторных алгоритмах; пример ее полезности мы увидим в жадном алгоритме разд. [39]
Вся область комбинаторных алгоритмов насыщена задачами, которые требуют подсчета или оценивания числа элементов в конечном множестве или перечисления без повторений всех этих элементов в некотором специальном порядке. Следовательно, стандартные процедуры подсчета и оценивания являются необходимым инструментом для каждого, кто имеет дело с комбинаторными алгоритмами. При подсчете и перечислении наиболее широкое применение имеет процедура поиска с возвращением ( и ее варианты), поскольку она предъявляет меньше всего требований к исследуемому множеству; более подробно мы обсудим эту процедуру в разд. В этой главе будут рассмотрены процедуры подсчета, которые применимы, когда исследуемое множество ( или семейство множеств) имеет хорошую структуру. При использовании такой структуры эти процедуры часто позволяют применять аналитические методы в противоположность вычислительному подходу поиска с возвращением. [40]
В той же книге, где помещена работа Уокера ( Walker), рассматриваются многие теоретические разделы комбинаторики и, таким образом, дается хорошее представление обо всей этой области. Там же в статье Лемера ( Lehmer) Обучение ЭВМ комбинаторным фокусам обсуждаются некоторые проблемы, связанные с программированием комбинаторных алгоритмов. [41]
Для недвудольных графов ситуация совершенно иная. Известные алгоритмы для нахождения наибольшего паросочетания в общем графе, выполняемые за полиномиальное время, занимают место среди самых сложных комбинаторных алгоритмов. Многие из них базируются на процедуре пополнения, осуществляемой с использованием чередующихся цепей, - как в большинстве доказательств теоремы Татта и формулы Бержа. Но чтобы превратить эти минимаксные результаты в выполняемые за полиномиальное время алгоритмы, требуются принципиально новые идеи. В его алгоритме в качестве ключевой была использована идея сжатия или стягивания определенных нечетных циклов. Вплоть до наших дней большинство алгоритмов построения паросочетаний ( и даже самые удачные из них) базируются - явно или неявно - на этой идее. [42]
Способы представления комбинаторных алгоритмов довольно разнообразны, и лекции или учебники по этому предмету могут предназначаться для разных аудиторий. Настоящая книга обращена к читателю, которого можно охарактеризовать как обладающего больше программистской, нежели математической квалификацией, к читателю, который интересуется комбинаторными алгоритмами в силу их практического значения. [43]
Сейчас трудно было бы, пожалуй, назвать раздел теоретической информатики, в котором в течение последнего десятилетия были бы достигнуты большие успехи, нежели в конструировании и анализе комбинаторных алгоритмов. С одной стороны, было обнаружено много новых, более эффективных методов решения комбинаторных задач с помощью ЭВМ, с другой - получены теоретические результаты, свидетельствующие все более явно о том, что для широкого класса проблем не существует достаточно эффективных алгоритмов. Эффективные комбинаторные алгоритмы находят применение во многих областях нечисленной обработки информации, особенно в дискретной оптимизации и в исследовании операций. [44]
Мир, 1977), написанной совместно с Дж. В данной книге предпринята попытка систематизации комбинаторных алгоритмов, выявления их общих черт и закономерностей. Подробно рассматриваются конкретные задачи использования комбинаторных алгоритмов, в частности очень важная для. Каждая глава сопровождается достаточно подробной исторической справкой и большим числом упражнений. [45]