- •Билет 1. Концепция языка Си, его достоинства и недостатки
- •Билет 2. Представление целых чисел в эвм. Основные типы данных в Си и операции над ними. Особенности операций над вещественными числами.
- •Билет 3. Основные управляющие конструкции в Си. Понятие инварианта цикла и его применение.
- •Билет 4. Характеристика алгоритмов, программ, языков программирования и соответствия между ними.
- •Билет 5. Массивы и указатели в языке Си. Их представление, связь между ними.
- •Билет 6. Метод барьера и различные варианты его применения.
- •Билет 7. Процедуры и функции в Си. Формальные и фактические. Входные и выходные параметры, локальные и глобальные переменные.
- •Билет 8. Массивы и указатели в Си, связь между ними. Передача массивов и указателей как параметров процедур.
- •Билет 9. Представление строк и символов в Си. Операции над ними.
- •Билет 10. Понятие эффективности алгоритма, различные способы ее измерения.
- •Билет 11. Понятие рекурсии. Виды и характеристики.
- •Билет 12. Алгоритмы перебора с возвратом. Способы сокращения перебора.
- •Способы сокращения перебора
- •Билет 13. Алгоритмы оптимального поиска. Метод ветвей и границ.
- •Билет 14. Сортировка массивов. Простые методы.
- •Билет 15. Сортировка массивов. Усовершенствованные методы.
- •Билет 16. Алгоритм поиска подстроки в строке.
- •3. Эвристика совпавшего суффикса. Если при сравнении строки и шаблона совпало один или
- •Билет 17. Алгоритм получения случайных чисел. Правильный выбор параметров линейного конгруэнтного генератора.
Билет 13. Алгоритмы оптимального поиска. Метод ветвей и границ.
Метод ветвей и границ (англ. branch and bound) — общий алгоритмический метод для нахождения оптимальных решений различных задач оптимизации, особенно дискретной и комбинаторной оптимизации. По существу, метод является вариацией полного перебора с отсевом подмножеств допустимых решений, заведомо не содержащих оптимальных решений. Метод ветвей и границ был впервые предложен в 1960 году Ленд и Дойг для решения задач целочисленного программирования.
Запишем алгоритм на псевдоязыке: void try ( ) { int k; for (k=0; k<m; k++) { If (подходит) { запись_варианта ( ); if (n<N) try(n+1); else if (f (вариант)</=/> f (оптимум) ) оптимум=вариант; } } }
В отличии от метода перебора, который ищет допустимое решение конкретной задачи, метод ветвей и границ ищет оптимальное решение, т.е. допустимое решение с наилучшим значением целевой функции.
Метод ветвей и границ требует: 1) Способы получить для каждого узла дерева границу наилучшего значения функции для всех решений (эта граница должна быть нижней для задачи минимизации и верхней для задачи максимизации). 2) Значение наилучшего решения, полученного к этому моменту.
Если такая информация доступна, то можно сравнивать значения границ узла со значением полученного к этому моменту решения. Если значения границ не лучше значения ужу имеющегося наилучшего решения, то такой узел является бесперспективным и его обработка может быть завершена.
Общая идея метода может быть описана на примере поиска минимума и максимума функции f(x) на множестве допустимых значений x. Функция f и x могут быть произвольной природы. Для метода ветвей и границ необходимы две процедуры: ветвление и нахождение оценок (границ).
Процедура ветвления состоит в разбиении области допустимых решений на подобласти меньших размеров. Процедуру можно рекурсивно применять к подобластям. Полученные подобласти образуют дерево, называемое деревом поиска или деревом ветвей и границ. Узлами этого дерева являются построенные подобласти.
Процедура нахождения оценок заключается в поиске верхних и нижних границ для оптимального значения на подобласти допустимых решений.
В основе метода ветвей и границ лежит следующая идея (для задачи минимизации): если нижняя граница для подобласти A дерева поиска больше, чем верхняя граница какой-либо ранее просмотренной подобласти B, то A может быть исключена из дальнейшего рассмотрения (правило отсева). Обычно, минимальную из полученных верхних оценок записывают в глобальную переменную m; любой узел дерева поиска, нижняя граница которого больше значения m, может быть исключен из дальнейшего рассмотрения.
Если нижняя граница для узла дерева совпадает с верхней границей, то это значение является минимумом функции и достигается на соответствующей подобласти.
Оптимальность метода поиска зависит от размера массива, в котором мы ищем. Прямой перебор всех значений прост в понимании, легок в исполнении и достаточно быстр на малых массивах данных.
Т.о. метод прямого перебора оптимален для малых массивов. Если же массив данных достаточно велик, то оптимальность поиска достигается предварительной сортировкой значений в массиве.