Метод - ветвь
Cтраница 3
Язык метода ветвей и границ весьма универсален. С его помощью может быть описан обширный круг задач. [31]
Сущность метода ветвей и границ применительно к задаче коммивояжера состоит в следующем. [32]
Существо метода ветвей и границ рассмотрим применительно к задаче коммивояжера. [33]
Разновидностью метода ветвей и границ можно считать метод последовательного конструирования, анализа и отбора вариантов, идея которого очень-проста. Затем строится последовательность вариантов таким образом, чтобы каждый последующий был не хуже предыдущего по значению целевой функции. Эта последовательность в конце концов сходится к оптимальному решению задачи. Основная сложность метода заключается в разработке правил доминирования, определяющих выбор последовательности вариантов. Эти правила пока также разработаны для частных случаев. [34]
Эффективность метода ветвей и границ существенно зависит от того, насколько удачной является методика получения оптимистических оценок. Понятно, что если получаемые оценки будут слишком оптимистичны ( будут сильно отличаться от соответствующих нижних границ), то это может привести к необходимости полного перебора ветвей. [35]
Идея метода ветвей и границ основана на следующем элементарном факте. [36]
Разновидностью метода ветвей и границ можно считать метод последовательного конструирования, анализа и отбора вариантов, идея которого очень проста. Затем строится последовательность вариантов таким образом, чтобы каждый последующий был не хуже предыдущего по значению целевой функции. Эта последовательность в конце концов сходится к оптимальному решению задачи. Основная сложность метода заключается в разработке правил доминирования, определяющих выбор последовательности вариантов. Эти правила пока также разработаны дли частных случаев. [37]
Алгоритмы метода ветвей и границ различаются стратегией ветвления и принципами оценивания. Стратегии ветвления определяются обычно нижними оценками, построенными на последнем шаге и, возможно, на предыдущих шагах. Усиление оценок позволяет ускорить вычислительный процесс. При решении практических задач стратегии ветвления и оценивания определяются обычно эвристическими соображениями, существенно использующими специфику задачи. [38]
Идея метода ветвей и границ применительно к задаче о коммивояжере довольно прозрачна. Ветвление основано на следующем элементарном соображении: переезд из любого данного города / в любой другой город / может либо принадлежать оптимальному циклу коммивояжера, либо не принадлежать ему. При вычислении же границ используется тот факт, что изменение длин всех путей, приводящих в далный город, или всех путей, выводящих из данного города, на одну и ту же величину приводит к новой задаче, оптимальные планы которой совпадают с оптимальными планами исходной задачи. [39]
Основой метода ветвей и границ является несколько общих принципов, позволяющих, как правило, существенно уменьшить объем прямого перебора. [40]
Идея метода ветвей и границ основана на следующем элементарном факте. [41]
Под методом ветвей и границ понимается алгоритм решения задачи, имеющий древовидную структуру поиска оптимального решения и использующий результаты решения оценочных задач. Древовидная структура называется обычно деревом ветвления. [42]
 |
Число исследуемых узлов при полном переборе и переборе по методу ветвей и границ. [43] |
Перебор методом ветвей и границ исследует гораздо меньше узлов, чем полный перебор. Дерево решений для задачи о формировании портфеля с 20 элементами содержит 2 097 151 узел. В то время как полный перебор всегда исследует все узлы, метод ветвей и границ может перебрать только примерно 1 600 узлов. [44]
Здесь рассматривается метод ветвей и границ для задачи о ранце, для задачи о коммивояжере в симметричном и несимметричном случаях. Для задачи о ранце рассматриваются два алгоритма: основной и модифицированный. Основной алгоритм следует стандартной схеме, в которой для вычисления оценок решаются задачи линейного программирования. В модифицированном алгоритме вычисление оценок сводится к решению одномерных линейных задач о ранце, число которых равно числу ограничений. Получаемые при этом оценки являются менее точными по сравнению с оценками, получаемыми в основном алгоритме. Изложение сопровождается большим числом детально рассмотренных примеров для задач о ранце и о коммивояжере. [45]
Страницы: 1 2 3 4