📄Работа №55264
Тема: Точный и приближённый алгоритмы для решения задачи размещения - поиска нескольких медиан
Характеристики работы
Тип работы
Магистерская диссертация
Предмет
Математика
Объем:
129 листов
Год:
2017
Просмотров:
386
5750
руб.
🛒 Купить работу
Не подходит эта работа?
Закажите новую по вашим требованиям
Узнать цену на написание
Закажите новую по вашим требованиям
Представленный материал является образцом учебного исследования, примером структуры и содержания учебного исследования по заявленной теме. Размещён исключительно в информационных и ознакомительных целях.
Workspay.ru оказывает информационные услуги по сбору, обработке и структурированию материалов в соответствии с требованиями заказчика.
Размещение материала не означает публикацию произведения впервые и не предполагает передачу исключительных авторских прав третьим лицам.
Материал не предназначен для дословной сдачи в образовательные организации и требует самостоятельной переработки с соблюдением законодательства Российской Федерации об авторском праве и принципов академической добросовестности.
Авторские права на исходные материалы принадлежат их законным правообладателям. В случае возникновения вопросов, связанных с размещённым материалом, просим направить обращение через форму обратной связи.
Настоящий учебно-методический информационный материал размещён в ознакомительных и исследовательских целях и представляет собой пример учебного исследования. Не является готовым научным трудом и требует самостоятельной переработки.
📋 Содержание
Введение 4
Постановка задачи 5
Глава 1. Теоретическая часть 6
1.1. Основные определения 6
1.2. Начальная обработка данных 9
1.3. Алгоритм Флойда-Уоршелла 11
1.4. Алгоритм нахождения внешней и внутренней медианы в графе 13
1.5. Приближенный алгоритм поиска p-медиан в графе 15
1.6. Точный алгоритм поиска p-медиан в графе 17
Глава 2. Программный комплекс 1 9
2.1. Работа с данными 23
2.1.1. Ввод данных вручную 2 4
2.1.2. Считывание данных из файла 27
2.1.3. Заполнение матрицы расстояний случайным образом 29
2.2. Проверка данных 31
2.3. Проверка связности графа и его направленности 34
2.4. Реализация алгоритма нахождения медианы в графе 36
2.5. Реализация приближенного алгоритма Тейтца и Барта поиска p-медиан
в графе 38
2.6. Реализация точного алгоритма поиска p-медиан в графе 40
Глава 3. Тестирование Windows-приложения 45
3.1. Тестирование точного алгоритма поиска внешней и внутренней медианы в графе на примерах 46
3.2. Тестирование приближенного алгоритма поиска p-медиан в графе на
примерах 53
3.3. Тестирование точного алгоритма поиска p-медиан в графе на примерах 6 7
3.4. Сравнение полученных результатов точного алгоритма поиска и медиан и приближенного алгоритма поиска p-медиан в графе
Заключение 93
Литература 94
Приложение 95
Постановка задачи 5
Глава 1. Теоретическая часть 6
1.1. Основные определения 6
1.2. Начальная обработка данных 9
1.3. Алгоритм Флойда-Уоршелла 11
1.4. Алгоритм нахождения внешней и внутренней медианы в графе 13
1.5. Приближенный алгоритм поиска p-медиан в графе 15
1.6. Точный алгоритм поиска p-медиан в графе 17
Глава 2. Программный комплекс 1 9
2.1. Работа с данными 23
2.1.1. Ввод данных вручную 2 4
2.1.2. Считывание данных из файла 27
2.1.3. Заполнение матрицы расстояний случайным образом 29
2.2. Проверка данных 31
2.3. Проверка связности графа и его направленности 34
2.4. Реализация алгоритма нахождения медианы в графе 36
2.5. Реализация приближенного алгоритма Тейтца и Барта поиска p-медиан
в графе 38
2.6. Реализация точного алгоритма поиска p-медиан в графе 40
Глава 3. Тестирование Windows-приложения 45
3.1. Тестирование точного алгоритма поиска внешней и внутренней медианы в графе на примерах 46
3.2. Тестирование приближенного алгоритма поиска p-медиан в графе на
примерах 53
3.3. Тестирование точного алгоритма поиска p-медиан в графе на примерах 6 7
3.4. Сравнение полученных результатов точного алгоритма поиска и медиан и приближенного алгоритма поиска p-медиан в графе
Заключение 93
Литература 94
Приложение 95
📖 Введение
Пусть в городе, поселке городского типа или деревне необходимо выбрать место для размещения пожарной части, станции скорой помощи. Каким образом можно оптимально расположить данные объекты в населенном пункте? От того, как быстро доберутся пожарная команда или врачи до места назначения, зависит человеческая жизнь.
В задачах о размещении пункта обслуживания необходимо расположить его так, чтобы сумма кратчайших расстояний от данного пункта, где необходимо разместить объект, до других вершин графа была минимальной. Такое место, где более рационально можно расположить пункт обслуживания, называется медианой графа. Медиан в графе может быть несколько - p-медианы.
Для этого были описаны и реализованы алгоритмы поиска медианы и p- медиан в графе, которые и вычисляют выгодное местоположение объектов, необходимых разместить в населенном пункте.
Модель города или поселка городского типа будет представлена в виде графа, где дома будут вершинами графа, а ребрами в графе будут выступать дороги между домами.
В задачах о размещении пункта обслуживания необходимо расположить его так, чтобы сумма кратчайших расстояний от данного пункта, где необходимо разместить объект, до других вершин графа была минимальной. Такое место, где более рационально можно расположить пункт обслуживания, называется медианой графа. Медиан в графе может быть несколько - p-медианы.
Для этого были описаны и реализованы алгоритмы поиска медианы и p- медиан в графе, которые и вычисляют выгодное местоположение объектов, необходимых разместить в населенном пункте.
Модель города или поселка городского типа будет представлена в виде графа, где дома будут вершинами графа, а ребрами в графе будут выступать дороги между домами.
✅ Заключение
1. По Рис.64 и Рис.65 видно, что при любых количествах вершин в графе чем больше количество p-медиан, тем быстрее работают алгоритмы, как точный алгоритм поиска p-медиан в графе, так и приближенный алгоритм Тейтца и Барта.
2. По Рис.64 и Рис.65 можно судить о том, что точный алгоритм для поиска p- медиан в графе работает дольше, чем приближенный алгоритм Тейтца и Барта.
3. По результатам тестируемых примеров в Примере 11 в Табл.13 и Табл.14, а также в Примере 12 в Табл.17 и в Примере 13 в Табл.18 наблюдаются расхождения в наборах медиан, выданных точным и приближенным алгоритмами поиска p-медиан в графе. Это говорит о том, что в редких случаях приближенный алгоритм Тейтца и Барта дает неверные ответы.
Итак, в ходе выполнения работы создано Windows-приложение, реализующее:
1) ввод матрицы расстояний между вершинами графа вручную, считывание расстояний между вершинами графа из файла или заполнение матрицы расстояний псевдослучайными числами;
2) реализован алгоритм поиска внешней и внутренней медианы в графе;
3) реализован приближенный алгоритм Тейтца и Барта для поиска p-медиан в графе;
4) реализован точный алгоритм поиска p-медиан в графе;
5) разработан пользовательский интерфейс, содержащий 13 кнопок с названиями соответствующих операций;
6) были проведены численные эксперименты по проверке работоспособности точного алгоритма поиска p-медиан в графе, установлено, что алгоритм из-за ограничения памяти не работает при количестве вершин более 65;
7) были проведены численные эксперименты по сравнению результатов приближенного и точного алгоритмов, показано, что для небольших графов (до 25 вершин) алгоритмы давали одинаковые результаты, а для графов с большим количеством вершин погрешность не превосходила 2%.
При работе с приложением пользователю видно, с каким графом он работает, потому что матрица расстояний данного графа выводится в окне визуализации. Можно также увидеть и матрицу кратчайших расстояний между вершинами графа, если выполнить ее расчет.
Результаты работы программы можно как наблюдать в окне приложения, так и вывести их в текстовый файл.
2. По Рис.64 и Рис.65 можно судить о том, что точный алгоритм для поиска p- медиан в графе работает дольше, чем приближенный алгоритм Тейтца и Барта.
3. По результатам тестируемых примеров в Примере 11 в Табл.13 и Табл.14, а также в Примере 12 в Табл.17 и в Примере 13 в Табл.18 наблюдаются расхождения в наборах медиан, выданных точным и приближенным алгоритмами поиска p-медиан в графе. Это говорит о том, что в редких случаях приближенный алгоритм Тейтца и Барта дает неверные ответы.
Итак, в ходе выполнения работы создано Windows-приложение, реализующее:
1) ввод матрицы расстояний между вершинами графа вручную, считывание расстояний между вершинами графа из файла или заполнение матрицы расстояний псевдослучайными числами;
2) реализован алгоритм поиска внешней и внутренней медианы в графе;
3) реализован приближенный алгоритм Тейтца и Барта для поиска p-медиан в графе;
4) реализован точный алгоритм поиска p-медиан в графе;
5) разработан пользовательский интерфейс, содержащий 13 кнопок с названиями соответствующих операций;
6) были проведены численные эксперименты по проверке работоспособности точного алгоритма поиска p-медиан в графе, установлено, что алгоритм из-за ограничения памяти не работает при количестве вершин более 65;
7) были проведены численные эксперименты по сравнению результатов приближенного и точного алгоритмов, показано, что для небольших графов (до 25 вершин) алгоритмы давали одинаковые результаты, а для графов с большим количеством вершин погрешность не превосходила 2%.
При работе с приложением пользователю видно, с каким графом он работает, потому что матрица расстояний данного графа выводится в окне визуализации. Можно также увидеть и матрицу кратчайших расстояний между вершинами графа, если выполнить ее расчет.
Результаты работы программы можно как наблюдать в окне приложения, так и вывести их в текстовый файл.
ИЛИ
Поиск аналога
📕 Список литературы
🛒 Оформить заказ
⚡ Работу высылаем в течении 5 минут после оплаты.