Cтраница 2
Существует тесная связь между основной идеей рассматриваемого метода и принципом оптимальности динамического программирования. Соответствующую формулировку указанного принципа применительно к аддитивному алгоритму можно выразить следующим образом: при заданном частичном решении значения остальных переменных должны выбираться так, чтобы дополнение этого решения было оптимальным. [16]
Этот метод - точный и потому трудоемкий; время решения задачи экспоненциально растет с ростом ее размерности. Однако, учитывая такой же порядок скорости счета аддитивным алгоритмом и то, что проверку ограничения на стоимость склеивания нужно проводить не более чем до 15 листов, разумно применять точный метод Литтла. Здесь метод Литтла для решения задачи коммивояжера описываться не будет: похожим методом решена задача проверки склеивае-мости листов. [17]
Для решения задач, содержащих только булевы переменные, обычно используется так называемый аддитивный алгоритм. Для решения нелинейных задач с булевыми переменными используется также обобщенный аддитивный алгоритм. [18]
Во-вторых, каждое частичное решение удовлетворяет условиям целочисленности. Применяя удачные правила выбора на шагах 1 и 4, с помощью аддитивного алгоритма можно найти допустимое по всем ограничениям и близкое к оптимальному решение на начальной итерации. [19]
Недавно в статье Джеффриона [80] был предложен метод неявного перебора, который является по существу вариантом аддитивного алгоритма. Наконец, в последней работе Балаша [48] развивается метод фильтра, позволяющий ускорить сходимость аддитивного алгоритма. Ограниченный объем книги не позволяет здесь остановиться на этих интересных вопросах. [20]
Ясно 1 что сформулированная выше задача & имеет 2П пробных планов. Основная черта аддитивного алгоритма, как и любого другого метода частичного перебора, состоит в получении оптимального плана ( или в выяснении отсутствия планов) путем рассмотрения лишь некоторого подмножества всех 2П пробных планов. Это осуществляется в рамках уже известной читателю общей схемы ветвления. [21]
Целочисленные алгоритмы, описанные в гл. В этом приложении мы обсудим другой подход, который может быть назван методом дерева поиска. Сюда относятся алгоритм ветвей и границ ( Лэнд и Дойг [139], Литтл и др. [144]), аддитивный алгоритм ( Балаш [4], Бил и Смол [14]), алгоритм прямого поиска ( Лемке и Шпильберг [143]) и многие другие. [22]
По своему характеру комбинаторные методы весьма разнородны. Пожалуй, центральное место среди них занимают в настоящее время методы, объединяемые под названием методов ветвей и границ. Общая идея метода ветвей и границ вместе с двумя важнейшими ее реализациями излагается в гл. Идейно близок к этому подходу аддитивный алгоритм Балаша, описываемый в гл. [23]
При выполнении этой команды МП будет пытаться вывести данные по 50-му адресу. При этом любой из синхроимпульсов, сопровождающих команду вывода, при помощи внешней логики заводится на шину Запуск АЦП, обеспечивая начало измерения. Этот же способ запуска АЦП использован в подпрограмме ADITER, реализующей аддитивный алгоритм итерационной коррекции погрешностей. [24]