Мои Конспекты
Главная | Обратная связь


Автомобили
Астрономия
Биология
География
Дом и сад
Другие языки
Другое
Информатика
История
Культура
Литература
Логика
Математика
Медицина
Металлургия
Механика
Образование
Охрана труда
Педагогика
Политика
Право
Психология
Религия
Риторика
Социология
Спорт
Строительство
Технология
Туризм
Физика
Философия
Финансы
Химия
Черчение
Экология
Экономика
Электроника

Способы сокращения перебора при решении комбинаторных задач



Методы перебора для комбинаторных задач.

Перебор всех планов задачи можно представить как обход некоторого дерева. Корень дерева соответствует началу выполнения перебора. Придавая по очереди все допустимые значения переменной x1, можно построить вершины первого уровня, для каждой из этих вершин можно выполнить разветвление по возможным значениям x2, получая вершины второго уровни, и т.д., вплоть до построения полных планов задачи, включающих все переменные.

Для программирования решения задач методом перебора удобнее всего использовать рекурсивные процедуры.

Общая рекомендация следующая: в параметры процедуры удобно включать те величины, которые изменяют свои значения в ходе углубления по дереву перебора, но требуют восстановления прежнего значения при возврате вверх по дереву.

Способы сокращения перебора при решении комбинаторных задач

· Если в задаче поиска найден один допустимый план, то можно прекратить перебор, поскольку задача уже решена.

· В некоторых случаях в задаче поиска после выбора нескольких первых переменных становится ясно, что получен допустимый план, независимо от значений оставшихся переменных.

· Возможна и обратная ситуация: выясняется, что для выбранного значения нескольких переменных xi нельзя получить допустимый план задачи, какими бы ни были значения остальных переменных.

· В задачах оптимизации иногда можно сравнить оценку с имеющимся рекордным значением функции.

4. Метод ветвей и границ: общие принципы

Общая идея метода может быть описана на примере поиска минимума и максимума функции f(x) на множестве допустимых значений x. Для метода ветвей и границ необходимы две процедуры: ветвление и нахождение оценок (границ).

Процедура ветвления состоит в разбиении области допустимых решений на подобласти меньших размеров.Полученные подобласти образуют дерево. Узлами этого дерева являются построенные подобласти.

Процедура нахождения оценок заключается в поиске верхних и нижних границ.

В основе метода ветвей и границ лежит следующая идея (для задачи минимизации): если нижняя граница для подобласти A дерева поиска больше, чем верхняя граница какой-либо ранее просмотренной подобласти B, то A может быть исключена из дальнейшего рассмотрения (правило отсева).

Если нижняя граница для узла дерева совпадает с верхней границей, то это значение является минимумом функции и достигается на соответствующей подобласти.

5. Метод ветвей и границ: решение задачи о коммивояжере

Идея метода. Пусть – множество всех допустимых замкнутых маршрутов задачи о коммивояжере с n городами.

Метод ветвей и границ основан на разбиении множества на два непересекающихся подмножества и на вычислении оценок каждого из них. Далее подмножество с минимальной оценкой разбивается на два подмножества и вычисляются их оценки.

На каждом шаге выбирается подмножество с наименьшей оценкой и производится его разбиение на два подмножества.

В конце концов получаем подмножество, содержащее замкнутый маршрут, удовлетворяющий наложенным ограничениям, стоимость которого минимальна.