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

ЛИЧНЫЙ КАБИНЕТ 

 

Здравствуйте гость!

 

Логин:

Пароль:

 

Запомнить

 

 

Забыли пароль? Регистрация

Быстрая помощь студентам

 

Работа № 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 :"< int k;
for (i=0; i

4 РАБОТА ПРОГРАММЫ
На рисунке 1 представлен граф – карта города.

Рисунок 1 – карта города.
На рисунке 2 представлен скриншот работы программы.

Рисунок 2 – скриншот работы программы.
По результатам работы программы можно сделать выводы, что внешний центр – это вершина 6.

5 СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ
1. Торчинский В.Е., Файнштейн С.И. Структуры и алгоритмы обработки данных на ЭВМ. Магнитогорск, МГТУ, 2007.




Перейти к полному тексту работы


Скачать работу с онлайн повышением уникальности до 90% по antiplagiat.ru, etxt.ru или advego.ru


Смотреть похожие работы