Автор работы: Пользователь скрыл имя, 12 Марта 2014 в 15:16, курс лекций
Эйлеров цикл содержит не только все ребра (по одному разу), но и все вершины графа (возможно, по несколько раз). Ясно, что эйлеровым может быть только связный граф. С эйлеровым циклом как раз связана задача о кенигсбергских мостах, приведшей к исторически первой попытке развития теории графов как самостоятельного предмета. Чтобы решить данную задачу потребуется сначала сформулировать и доказать теорему. Эта теорема справедлива также и для мультиграфов, и для псевдографов, исключая тот случай, когда псевдограф имеет только одну вершину.
На основе этой идеи американский математик Р.Гомори предложил ряд сходящих-ся алгоритмов решения задач дискретного линейного программирования. Ему удалось обосновать правила построения дополнительных ограничений и доказать конечность алгоритмов.
Для решения задач дискретного (особенно нелинейного) программирования получили широкое распространение комбинаторные методы направленного частичного перебора допустимых планов. Из них наиболее универсален метод ветвей и границ.
18.3. Метод ветвей и границ.
Метод ветвей и границ относится к группе комбинаторных методов. Комби-наторные методы, исходя из конечности числа допустимых планов задачи, заменяют полный перебор всех планов их частичным направленных перебором. Комбинаторные методы в значительно меньшей степени подвержены в процессе вычислений влиянию ошибок округления, поэтому являются более предпочтительными по сравнению с мето-дами отсечения. Метод ветвей и границ – один из наиболее эффективных методов реше-ния задач комбинаторного типа.
Перейдем к изложению идеи метода ветвей и границ. Для этого рассмотрим общую задачу дискретного программирования
где W – конечное множество допустимых планов.
1. Находим верхнюю границу (оценку) функции , т.е. такое число , что для любых
Если при этом удается найти такой план задачи, для которого выполняется равенство
то – оптимальный план задачи.
2. Если оптимальный план не найден, то некоторым способом разбиваем мно-жество W на конечное число непересекающихся подмножеств :
и находим для каждого из этих подмножеств верхнюю границу . Если при этом удается найти такой план , что выполняется соотношение
то – оптимальный план задачи. Если же такой план не найден, то выбираем подмно-жество с наибольшей верхней границей (перспективное подмножество) и разбиваем его на несколько непересекающихся подмножеств . Для каждого нового подмножества находим верхнюю границу . Если будет найден такой план , что
то оптимальный план задачи. Если оптимальный план не найден, то дальнейшему подвергается подмножество с наибольшей верхней границей, и т.д. Процесс продолжается до получения оптимального плана. Способы ветвления и нахождения верхних границ выбираются для каждой конкретной задачи дискретного программирования. Процесс сопровождается построением дерева ветвления.
Информация о работе Лекции по "Развитию операционных систем"