Категория
Информатика
Тип
реферат
Страницы
6 стр.
Дата
15.02.2008
Формат файла
.doc — Microsoft Word
Архив
19691.zip — 26.67 kb
  • lekcii-po-vychislitelnoj-matematike_19691_1.DOC — 148.5 Kb
  • Readme_docus.me.txt — 125 Bytes
Оцените работу
Хорошо  или  Плохо


Текст работы

Вычислительная математикаСпециальность ПО
5-й семестрКонспект лекцийЛекция 1
Общее описание метода ветвей и границ организации пол-ного перебора возможностей. Решение задачи о коммивояжере методом ветвей и границ: основная схема.
Пусть - конечное множество и - ве-щественно-значная функция на нем; требуется найти минимумэтой функции и элемент множества, на котором этот минимумдостигается.
Когда имеется та или иная дополнительная информация о множестве, решение этой задачи иногда удается осуществить без полного перебора элементов всего множества M. Но чащевсего полный перебор производить приходится. В этом случаеобязательно возникает задача, как лучше перебор организовать.
Метод ветвей и границ - это один из методов организации полного перебора. Он применим не всегда, а только тогда, когдавыполняются специфические дополнительные условия на множество M и минимизируемую на нем функцию. А именно, предположим, что имеется вещественно-значная функция , на множестве подмножеств множества M со следующими двумя свойствами:
1) для (здесь - множество, состоящееиз единственного элемента );
2) если и , то .
В этих условиях можно организовать перебор элементов множества M с целью минимизации функции на этом множестве так:
разобьем множество M на части (любым способом) и выберем ту из его частей р1, на которой функция , минимальна; за-тем разобьем на несколько частей множество 1 и выберем ту из его частей 2, на которой минимальна функция ,; затем разо-бьем ;2 на несколько частей и выберем ту из них, где минималь-на , и так далее, пока не придем к какому-либо одноэлементно-му множеству .
Это одноэлементное множество называется рекордом.
Функция Ф, которой мы при этом выборе пользуемся, называетсяоценочной. Очевидно, что рекорд не обязан



Ваше мнение



CAPTCHA