Алгоритм - ветвь
Cтраница 2
Решите задачу с помощью алгоритма ветвей и границ, приведенного в разд. [16]
В следующем параграфе вводится общая схема для алгоритмов ветвей и границ. Она включает ситуации переполнения памяти, превышения времени счета, а также остановки при достижении заданной точности. За этим следуют доказательство корректности и ряд недавних результатов, касающихся зависимости потребностей в вычислительных ресурсах от правил отсечения, определения допустимых решений, от правила доминирования, нижней оценки и заданной степени точности. Далее мы рассмотрим приближенные алгоритмы, включающие эвристические процедуры и поиск в локальной окрестности. В заключение представлены результаты расчетов для двухмашинной конвейерной задачи, которая упоминалась выше. Описаны характеристики точных, приближенных и гарантирующих заданную точность алгоритмов. Особое внимание уделено извлечению из результатов машинных расчетов наиболее полезной информации - в виде допустимых решений и нижних оценок оптимальных решений. [17]
Следующий код использует проверку верхней и нижней границ для реализации алгоритма ветвей и границ. [18]
Для непосредственного применения этого подхода предположим, что при решении задачи применяется алгоритм ветвей и границ, в котором отсев реализуется с помощью оценок подмножеств. [19]
В последнем случае ставится задача о поиске всех оптимальных решений; все рассмотренные ранее варианты алгоритма ветвей и границ ориентируются на поиск одного оптимального решения. [20]
 |
Ханойские башни. [21] |
Такая схема с возвратами, использующая некоторые ограничения для уменьшения роста потенциального дерева поиска, называется алгоритмом ветвей и границ. [22]
Последние две рекомендации относятся не только к симметричной задаче коммивояжера, но и к любой другой, решаемой с применением алгоритма ветвей и границ. [23]
Построение каждого из множеств S - ( Ri и S2 ( R2) связано с решением задачи, т.е. с применением алгоритма ветвей и границ с измененным правилом отсева. [24]
Еще один пример: алгоритмы ветвей и границ успешно решают задачу о рюкзаке и поэтому многие исследователи считают ее хорошо решаемой, хотя алгоритмы ветвей и границ имеют экспоненциальную оценку сложности. Приведенные примеры хорошего поведения экспоненциальных алгоритмов, достаточно редки, поэтому хотя экспоненциальные алгоритмы известны для многих задач, немногие из них можно использовать для практических целей. [25]
Эффективность алгоритма ветвей и границ при решении задач дискретного программирования оценивается числом решенных подзадач, т.е. числом вершин в дереве ветвления. [26]
Для алгоритма динамического программирования при решении любой задачи об одномерном ранце с целочисленными значениями параметров известны точные линейные по п оценки трудоемкости и памяти: 2Rn и 2n ( R 1) соответственно. Для алгоритма ветвей и границ при решении любой задачи указанного типа такие оценки, вообще говоря, неизвестны. [27]
 |
Обходы дерева. [28] |
Обход в глубину используется в алгоритмах, где необходимо сначала обратить-сяко всем листьям. Например, алгоритм ветвей и границ, описанный в главе 8, вначале посещает листья. Для сокращения времени поиска в оставшейся части дерева используются результаты, полученные на уровне листьев. [29]
Алгоритм построения приближенного решения х задачи (9.3.16) называется г-оптимальным, если он обеспечивает получение е-опти-мального решения. Подробное описание е-оптимального алгоритма ветвей и границ для решения задачи (9.3.16) содержится в гл. Переменная Xj называется е-существен-ной, если в процессе работы е-оптимального алгоритма по ней будет сделано хотя бы одно разветвление. [30]
Страницы: 1 2 3 4