Модели, построенные с помощью алгоритмов ветвей и границ

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

На первом этапе при решении таким методом, определяется полный перебор вариантов (описывается ветвление). Выбирается база ветвления и от неё производится само ветвление (разбиение задачи на подзадачи).

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

Пример. В некой файловой системе справочник организован в виде двоичного дерева. Каждой вершине соответствует некий файл, в котором содержится имя файла и d – дата последнего обращения к нему. Требуется удалить все файлы, последнее обращение к которым происходило до некоторой даты D.

При решении задачи, на каждом уровне проверяется соответствие вершины ветвления условию d_ij>D. Файлы – вершины ветвления, которые не удовлетворяют условию, удаляются. На нижнем уровне удаляются файлы, не удовлетворяющие условию d_ij>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:однозначность