Автоматизация проектирования охранной системы

Введение 3

Техническое задание 3

1. Постановка задачи 4

2. Обзор методов решения 5

2.1 Точный метод решения – метод покрытия двоичных таблиц. 5

2.1.1 Пример решения задачи с помощью метода двоичного покрытия таблиц 5

2.2 Приближенный метод решения – «Жадный алгоритм». 9

2.2.1 Пример решения задачи с помощью «Жадного алгоритма» 9

2. Описание программной реализации 11

2.1 Обзор инструментальных средств 11

2.2 Описание структуры программы 11

2.3 Описание разработанного ПО 12

3. Вывод 14

Техническое задание

Автоматизация проектирования охранной системы.

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

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

Для проектирования оптимальной охранной системы целесообразно использовать метод покрытия булевых матриц, т.к. при его использовании гарантируется точное решение задачи в течении времени Θ(mn). Время же работы алгоритма покрытия булевых матриц в наихудшем случае растет экспоненциально и сложно прогнозировать время решения задачи, т.к. оно зависит от размерности территории. В некоторых случаях задача может быть решена за более короткое время методом «Жадного алгоритма». Метод покрытия булевых таблиц в отличие от метода «Жадного алгоритма» требует много более значительных затрат памяти.