Методы покрытия многосвязных ортогональных многоугольников для задач оптимального размещения сенсоров в области мониторинга

• Автор: Кузнецов, Вячеслав Юрьевич
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2009
• Место защиты: Уфа
• Количество страниц: 162 с. : ил.

ОГЛАВЛЕНИЕ

Использованные обозначения.

Введение.

1 .Модели и методы покрытий.

1.1. Постановки задач покрытия

1.2. Упаковки и их связь с покрытиями.

Выводы по главе 1.

2.Методы конструирования покрытий кругами многосвязных ортогональных многоугольников.
2.1. Математическая модель задачи покрытия кругами многосвязных ортогональных многоугольников.
2.2. Блочная эвристика v, ВС покрытия кругами многосвязного ортогонального многоугольника.
2.3. Гексагональная эвристика x v, НС покрытия кругами многосвязного ортогонального многоугольника.
2.4. Эволюционная эвристика 11ЕА
Выводы по главе 2.
3.Задача оптимального размещения сенсоров в области мониторинга и ее технические приложения.
3.1. Задача размещения газоанализаторов на территории
нефтеперерабатывающего завода.
3.2. Задача генерации карт вейпоинтов.
3.3. Другие задачи территориального распределения объектов
Выводы по главе 3.
4. Проблемноориентированный комплекс программ и проведение
численного эксперимента.
4.1. Пректированис комплекса программ.
4.2. Численный эксперимент с анализом его результатов.
Выводы по главе 4.
Основные результаты работы и выводы
Литература


В четвертой главе. В заключении приведены основные результаты работы и выводы. У задач покрытия более чем столетняя история - первые задачи были поставлены еще в веке, но поскольку их решение обычно связано с большими вычислительными затратами, они не получили большого распространения. С развитием теории сложности, комбинаторной геометрии и вычислительной техники интерес к задачам покрытия возрос. Это обусловлено как возможностью проведения численных экспериментов, так и практическими применениями методов решения задач. Задачи покрытия применяются в различных предметных областях: в промышленности, в строительстве, в астрономии и т. Все остальные задачи являются подклассами этих задач. Специфика конкретных задач состоит в структуре покрывающих и покрываемых множеств, а также в выборе критериев оптимизации. Задача минимального покрытия множества является КПР-трудной, как и большинство других представителей задач покрытия, однако специфика множеств может быть такова, что решение можно найти за полиномиальное время. Такой является, например, задача о минимальном покрытии выпуклой области равными кругами. Задача минимального покрытии множества [1]. Х = ^Х]. Xе и, покрывал множество X, т. X = ^Х,. Например, Х={ 1,2,3,4. Х5={3,5,7,9}. Гогда решением будут 2 подмножества Х| и X*. Выбор проектной группы. Для решения некоторой задачи требуется знание п навыков. Каждый из сотрудников организации владеет некоторым набором навыков. Требуется собрать группу из наименьшего числа сотрудников таким образом, чтобы каждым из требуемых навыков обладал хотя бы один из членов группы. Проектирование логических схем. У логической схемы есть п входов и единственный выход. Схема вычисляет некоторую булеву функцию. Одну и ту же булеву функцию можно записать различными способами. Требуется найти самый простой способ записи булевой функции. Это задача о нахождении дизъюнктивной нормальной формы (ДНФ). Задача поиска ДНФ эквивалентна задаче поиска минимального покрытия множества. Задача реберного покрытия [8]. Реберным покрытием графа называется такое множество ребер, что всякая вершина графа инцидентна хотя бы одному из этих ребер. Требуется найти реберное покрытие, содержащее наименьшее число ребер. Заметим, что реберное покрытие существует только для графов без изолированных вершин. Наименьшее число ребер в реберном покрытии графа в обозначим через р(О). Паросочетанием раг(С) в графе называется множество ребер, попарно не имеющих общих вершин. G). Число ребер в maxpar(G) обозначим через л(G). Следующая теорема дает ключ к построению точного алгоритма полиномиальной сложности. Теорема 1. Для любого графа Gen вершинами, не имеющего изолированных вершин, справедливо равенство 7t(G)+p(G)=n. Алгоритм линейной сложности приведен в [8]. Задача вершинного покрытия |8]. Вершинным покрытием неориентированного графа G-(V, Е) называется некоторое подмножество V множества вершин К, со следующим свойством: для любого ребра е графа G ХОТЯ бы один ИЗ КОНЦОВ содержится В V|. Размером вершинного покрытия называется количество вершин входящих в него. Требуется найти вершинное покрытие минимального размера. Задача поиска минимального вершинного покрытия - одна из первых задач, для которых установлено свойство NP-полноты [3]. Задача максимального покрытия []. Пусть имеются прямоугольные листы заданной ширины W и длины L и набор из ш прямоугольников. Требуется, размещая прямоугольники на листах, найти такой план покрытия, чтобы количество полностью покрытых листов было максимальным. Если каждая точка каждого листа в плане покрытия принадлежит одному или нескольким прямоугольникам, то план покрытия допустимый. Если среди всех допустимых планов покрытия найден такой, что количество полностью покрытых листов максимально, то такой план покрытия оптимальный. Для удобства здесь и далее введем прямоугольную систему координат: оси Ох и Оу совпадают соответственно с нижней и боковой сторонами покрываемого объекта. Любая точка на объекте принадлежит одному или нескольким покрывающим деталям.