Модели, построенные с помощью алгоритмов ветвей и границ
Алгоритмы ветвей и границ, как и большая часть алгоритмов, описанных ранее, применяются для решения переборных задач. Как и алгоритм с отходами, они исследуют древовидную модель пространства решений и ориентированы на поиск в некотором смысле оптимального решения (из конечного множества возможных решений-вариантов).
На первом этапе при решении таким методом, определяется полный перебор вариантов (описывается ветвление). Выбирается база ветвления и от неё производится само ветвление (разбиение задачи на подзадачи).
На втором этапе для полученного дерева ветвления определяем нижние границы (термин «нижние границы» относителен), для каждой из возникающих в дереве подзадач. Ветвь не имеет смысл исследовать, если нижняя граница для подзадач в данной ветви превышает значение решения найденного в данный момент.
Пример. В некой файловой системе справочник организован в виде двоичного дерева. Каждой вершине соответствует некий файл, в котором содержится имя файла и d – дата последнего обращения к нему. Требуется удалить все файлы, последнее обращение к которым происходило до некоторой даты D.
При решении задачи, на каждом уровне проверяется соответствие вершины ветвления условию dij>D. Файлы – вершины ветвления, которые не удовлетворяют условию, удаляются. На нижнем уровне удаляются файлы, не удовлетворяющие условию dij>D (рис.3.).
Рисунок
Тесты
1. К высшим уровням абстрактного описания систем относят:
1:символический
2:топологический
3:динамический
4:логико-математический
2. Метод исследования сложных вычислительных систем это:
1:Системный анализ
2:Математический анализ
3:Теория технических систем
4:Нечеткие логики
3. Новый объект, отражающий существенные особенности изучаемого объекта, процесса или явления, называют …
1:моделью
2:предметной областью
3:сущностью
4:языком представления знаний
4. К моделированию НЕЦЕЛЕСООБРАЗНО прибегать, когда …
1:не определены существенные свойства исследуемого объекта
2:процесс очень медленный
3:создание объекта чрезвычайно дорого
4:исследование самого объекта приводит к его разрушению
5. К основным формам представления информационных моделей НЕ ОТНОСЯТ
1:экономические
2:описательные
3:формально-логические
4:графические
6. Процесс описания объекта на искусственном языке называют ___________ объекта.
1:формализацией
2:семантическим анализом
3:синтаксическим анализом
4:компиляцией
7. В модели «черный ящик» система представляется как
1:совокупность функций входов и выходов
2:наиболее абстрактное представление структуры системы
3:совокупность связей между входами и выходами
4:совокупность состояний системы
8. На каком этапе осуществляется определение целей моделирования
1:постановка задачи
2:разработка концептуальной модели
3:разработка имитационной модели
4:разработка математической модели
9. Укажите число различных деревьев, которые можно построить на n нумерованных вершинах.
1: 
2: 
3: 
4: 
10. Выберите наиболее точное определение. Информационный процесс с известным начальным состоянием объектов, конечным состоянием, исполнителем и набором операций из системы команд исполнителя называется …
1:алгоритмическим процессом
2:моделированием
3:компиляцией
4:аналитическим процессом
11. Среди общепринятых классификаций видов моделей нет классификации …
1:«логические – сенсорные»
2:«статические – динамические»
3:«детерминированные – стохастические»
4:«дискретные-непрерывные»
12. Укажите наиболее точное определение. Модели типа «черный ящик» – это …
1:модели, описывающие зависимость выходных параметров объекта от входных без учета внутренней структуры объекта;
2:модели, описывающие зависимость параметров состояния объекта от входных с учетом структуры и закономерностей работы объекта
3:модели «аварийного» ящика на самолетах
4:модели мышления
5:модели, описывающие изменение выходных параметров объекта без связи со значением входных переменных
13. Укажите наиболее точное определение. Модель конечного автомата – это …
1:модель, описывающая набор ограниченного числа состояний объекта моделирования и условия перехода из одного состояния в другое;
2:модель, описывающая набор ограниченного числа переменных состояния и закономерности изменения их значений.
3:модель, описывающая изменение конечного набора состояний
4:дискретная модель
5:модель станков-автоматов
14. Укажите содержательную модель:
1:милицейский протокол
2:имитационная модель
3:системы уравнений, описывающие физические процессы, происходящие в недрах Земли
4:модель «черный ящик»
15. Какая модель системы изображена на рис.:
1:модель отношений
2:модель «черный ящик»
3:модель состава
4:модель переходов
16. Формализация задачи с использованием пространства состояний не включает:
1:алгоритм решения
2:формы описания состояний
3:множество операторов перехода из состояния в состояние
4:свойства целевых состояний
17. Метод решения задач, при котором объекты разного рода объединяются общим понятием (концепцией), а затем сгруппированные сущности рассматриваются как элементы единой категории:
1:абстрагирование
2:декомпозиция
3:индукция
4:структуризация
18. Деревья , списки, хэш-адресация – это…
1:структуры данных
2:модели предметной области
3:условия вывода
4:типы информации
19. Изменение концентрации соли в растворе пропорционально самой концентрации. Самая подходящая для описания процесса модель, описывающая изменение концентрации во времени, …
1:относится к классу непрерывных динамических моделей и имеет вид дифференциального уравнения (с независимой переменной времени)
2:относится к классу непрерывных статических моделей и имеет вид дифференциального уравнения (с независимой пространственной переменной)
3:относится к классу непрерывных статических моделей и имеет вид разностного уравнения
4:относится к классу дискретных динамических моделей и имеет вид модели конечного автомата
20. Самая подходящая математическая модель, с помощью которой может быть описана (задана) работа обычного уличного светофора – это модель …
1:детерминированного конечного автомата
2:описываемая системой дифференциальных уравнений
3:описываемая системой алгебраических уравнений
4:вероятностного автомата
21. Задача коммивояжера (объехать все пункты из списка по разу и вернуться так, чтобы преодоленное расстояние было бы минимальным) формализуется проще всего с использованием языка …
1:описания графов
2:представления знаний
3:алгоритмического
4:программирования
5:баз данных
22. Граф, в котором есть путь, проходящий только один раз через каждую вершину, называется
1:гамильтоновым
2:эйлеровым
3:ориентированным
4:полным
23. Задача «Обслуживание станков мостовыми кранами» является задачей
1:массового обслуживания
2:управления запасами
3:сетевого планирования
4:календарного планирования
24. Задача моделирования эволюции реализуется
1:на основе генетических алгоритмов
2:с использованием нейронных сетей
3:алгоритмами нечеткой логики
4:интеллектуальными программными агентами
25. Одна из моделей для описания простейшей лотереи типа «Спринт» (тянешь билет и сразу проверяешь) – это модель …
1:вероятностного автомата
2:детерминированного автомата
3:системы массового обслуживания
4:динамической системы
5:случайного блуждания
26. К естественному представлению алгоритма относят:
1:блок-схема
2:ER-диаграмму
3:язык PASCAL
4:рекурсивные функции
27. Можно ли считать формальным исполнителем алгоритма следующие устройства:
1:графический редактор
2:кодовый замок
3:телефон с памятью для записи номеров
4:принтер
28. Формализация задачи с использованием пространства состояний не включает:
1:алгоритм решения
2:формы описания состояний
3:множество операторов перехода из состояния в состояние
4:свойства целевых состояний
29. Метод познания, состоящий в исследовании объекта на его модели, называют ..
1:моделированием
2:логическим выводом
3:исчислением предикатов
4:имитацией
30. К основным классам моделей (по способу отражения свойств объекта) относят …
1:предметные
2:социальные
3:медико-биологические
4:территориальные
31. В представлении алгоритма не существенна
1:трудоемкость
2:понятность
3:наглядность
4:однозначность