Здесь можно найти учебные материалы, которые помогут вам в написании курсовых работ, дипломов, контрольных работ и рефератов. Так же вы мажете самостоятельно повысить уникальность своей работы для прохождения проверки на плагиат всего за несколько минут.
Предлагаем нашим посетителям воспользоваться бесплатным программным обеспечением «StudentHelp», которое позволит вам всего за несколько минут, выполнить повышение оригинальности любого файла в формате MS Word. После такого повышения оригинальности, ваша работа легко пройдете проверку в системах антиплагиат вуз, antiplagiat.ru, РУКОНТЕКСТ, etxt.ru. Программа «StudentHelp» работает по уникальной технологии так, что на внешний вид, файл с повышенной оригинальностью не отличается от исходного.
Работа № 100490
Наименование:
Курсовик «Внешний Центр. Ориентированный граф»
Информация:
Тип работы: Курсовик.
Предмет: Программирование.
Добавлен: 11.11.2016.
Год: 2016.
Страниц: 7.
Уникальность по antiplagiat.ru: < 30%
Описание (план):
Оглавление 1 реальная оптимизационная задача 4 1.1Текстовое описание задачи 4 1.2Математическая постановка задачи 4 2 Теоритическая часть 5 3 алгоритм и его реализация 6 3.1 Реализуемый алгоритм 6 3.2 Листинг программы 6 4 Работа программы 8 5 Список использованной литературы 9
1 РЕАЛЬНАЯ ОПТИМИЗАЦИОННАЯ ЗАДАЧА 1.1Текстовое описание задачи Сеть банков, расположенных в одном городе, соединенная сетью односторонних дорог. Где оптимально поместить инкассаторский центр, чтобы путь до самого удаленного банка был минимальным? 1.2Математическая постановка задачи УСЛОВИЕ: Дана карта города, на карте отмечены банки, соединенные сетью односторонних дорог, известна их протяженность. ВОПРОС: Требуется поместить инкассаторский центр таким образом, чтобы путь, проезжаемый инкассаторами до самого удаленного банка, был минимальным.
2 ТЕОРИТИЧЕСКАЯ ЧАСТЬ В данной работе будем рассматривать сильно связный ориентированный граф G (для каждой пары вершин существует ориентированный путь туда и обратно), каждой дуге (i›j) которого поставлено в соответствие неотрицательное число Aij – длина дуги. Вершинам и дугам графа могут быть приписаны веса. То есть дуга графа помимо длины может иметь вес. Все длины и веса неотрицательны. Внешний центр – вершина графа r такая, что расстояние от нее до самой удаленной вершины минимально, т.е. Max(Dri) ® min, где i = 1…n и Dri – расстояние от центра r до i-й вершины. Если вершинам графа приписаны положительные веса P1,P2,..,Pn, то минимизируется «взвешенное» расстояние: Max(Dri ? Pi) ® min.
3 АЛГОРИТМ И ЕГО РЕАЛИЗАЦИЯ 3.1 Реализуемый алгоритм 1. Используем алгоритм Флойда, находим матрицу D (матрица кратчайших расстояний). 2. Сформируем массив Max[1..n], где Max[i] – расстояние от центра в вершине i до самой удаленной вершины. 3. Найдем в массиве Max минимальный элемент. 4. Выводим на экран минимальный элемент из массива Max и вершину, на которой он достигается. 3.2 Листинг программы 1. Алгоритм Флойда. void Floid (int ** D, int V) { cout‹‹"Shortest paths matrix :"‹‹endl; int k; for (i=0; i‹V; i++) D[i][i]=0;...
4 РАБОТА ПРОГРАММЫ На рисунке 1 представлен граф – карта города.
Рисунок 1 – карта города. На рисунке 2 представлен скриншот работы программы.
Рисунок 2 – скриншот работы программы. По результатам работы программы можно сделать выводы, что внешний центр – это вершина 6.
5 СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ 1. Торчинский В.Е., Файнштейн С.И. Структуры и алгоритмы обработки данных на ЭВМ. Магнитогорск, МГТУ, 2007.
* Примечание. Уникальность работы указана на дату публикации, текущее значение может отличаться от указанного.
