ВВЕДЕНИЕ 3
1 Постановка задачи и структура работы 5
2 Теория размещения на графах 6
3 Фундаментальные алгоритмы, используемые в программном комплексе 9
3.1 Алгоритм Флойда-Уоршелла 9
3.2 Алгоритм нахождения центра и медианы графа 11
4 Модифицированный метод Хакими 15
5 Особенности реализации алгоритмов в программном комплексе 25
6 Анализ времени работы программы 32
ЗАКЛЮЧЕНИЕ 37
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ 38
Приложение №1. Код программы 39
Приложение №2. Результаты работы программного комплекса на модельных данных разных размерностей 45
В практической деятельности возникают задачи «наилучшего» размещения центров обслуживания в городах и регионах, таких как: торговые центры, посты пожарной охраны, фабрики, аэропорты, склады и т.д.
Цель таких задач — разместить некоторые объекты так, чтобы минимизировать максимальное из расстояний (или время проезда) от этого объекта до самой отдаленной точки города или региона. По очевидным причинам этот класс задач принято называть минимаксными задачами размещения.
Актуальность данного типа задач доказывает их исключительная практическая ценность, человечество развивается: появляются всё новые и новые службы, виды услуг, города растут, и население нуждается в оптимальных способах взаимодействия со всеми службами, ведь именно это определяет качество жизни в городе, его престижность.
Вследствие этого существует много разнообразных задач размещения, и техническая литература изобилует методами их решения. В этом разделе мы ограничимся рассмотрением только таких задач размещения, для которых областью допустимых точек размещения центров обслуживания является некоторый граф, т. е. эти центры могут располагаться в какой-либо вершине или на какой-либо дуге графа.
В изученных источниках [1], [2] рассматриваемые задачи размещения часто разделяют на 3 категории:
1. Размещения на перекрёстках (в вершине графа) так, чтобы минимизировать взвешенное расстояние до наиболее удаленного перекрестка (это одна из тех минимаксных задач, которые были озвучены выше), то есть нахождение центра.
2. Размещения на перекрёстках (в вершине графа) так, чтобы минимизировать суммарное взвешенное расстояние до всех перекрестков, то есть нахождение медианы.
3. Размещения на дороге (на ребре графа) так, чтобы минимизировать взвешенное расстояние до наиболее удаленного перекрестка, то есть нахождение абсолютного центра.
В результате выполнения выпускной квалификационной работы, а также самостоятельного изучения дополнительного материала, удалось добиться хороших результатов в освоении материала по темам, связанным с задачами размещения, удалось освоить алгоритм нахождения центра и медианы графа, алгоритм Флойда, а также модифицированный метод Хакими. Также удалось приобрести практические навыки в написании программ на языке Python.
Создан программный комплекс для решения задач размещения при поиске центра, медианы и абсолютного центра. Наиболее сложная из рассматриваемых задач поиска абсолютного центра опробована на различных графах размерностью до 200 вершин.
ВКР опробована на реальных данных, а также был проведен эксперимент на модельных данных разной размерности, который продемонстрировал работоспособность программы. Например, для размерности в 1000 вершин программа будет выполняться примерно 14 минут.
Новизна данной работы заключается в том, что геометрический метод Хакими переведен на алгебраический язык, при этом те варианты, которые не будут приводить к оптимальному решению, отсечены как за счет модификации метода Хакими, так и за счет собственных алгоритмических находок, связанных с учетом только тех вариантов, которые удовлетворяют соответствующим ограничениям. За счет этого алгоритм получился фактически менее чем кубической сложности (судя по экспериментам на модельных данных).
