Банк рефератов содержит более 364 тысяч рефератов, курсовых и дипломных работ, шпаргалок и докладов по различным дисциплинам: истории, психологии, экономике, менеджменту, философии, праву, экологии. А также изложения, сочинения по литературе, отчеты по практике, топики по английскому.
Полнотекстовый поиск
Всего работ:
364150
Теги названий
Разделы
Авиация и космонавтика (304)
Административное право (123)
Арбитражный процесс (23)
Архитектура (113)
Астрология (4)
Астрономия (4814)
Банковское дело (5227)
Безопасность жизнедеятельности (2616)
Биографии (3423)
Биология (4214)
Биология и химия (1518)
Биржевое дело (68)
Ботаника и сельское хоз-во (2836)
Бухгалтерский учет и аудит (8269)
Валютные отношения (50)
Ветеринария (50)
Военная кафедра (762)
ГДЗ (2)
География (5275)
Геодезия (30)
Геология (1222)
Геополитика (43)
Государство и право (20403)
Гражданское право и процесс (465)
Делопроизводство (19)
Деньги и кредит (108)
ЕГЭ (173)
Естествознание (96)
Журналистика (899)
ЗНО (54)
Зоология (34)
Издательское дело и полиграфия (476)
Инвестиции (106)
Иностранный язык (62792)
Информатика (3562)
Информатика, программирование (6444)
Исторические личности (2165)
История (21320)
История техники (766)
Кибернетика (64)
Коммуникации и связь (3145)
Компьютерные науки (60)
Косметология (17)
Краеведение и этнография (588)
Краткое содержание произведений (1000)
Криминалистика (106)
Криминология (48)
Криптология (3)
Кулинария (1167)
Культура и искусство (8485)
Культурология (537)
Литература : зарубежная (2044)
Литература и русский язык (11657)
Логика (532)
Логистика (21)
Маркетинг (7985)
Математика (3721)
Медицина, здоровье (10549)
Медицинские науки (88)
Международное публичное право (58)
Международное частное право (36)
Международные отношения (2257)
Менеджмент (12491)
Металлургия (91)
Москвоведение (797)
Музыка (1338)
Муниципальное право (24)
Налоги, налогообложение (214)
Наука и техника (1141)
Начертательная геометрия (3)
Оккультизм и уфология (8)
Остальные рефераты (21697)
Педагогика (7850)
Политология (3801)
Право (682)
Право, юриспруденция (2881)
Предпринимательство (475)
Прикладные науки (1)
Промышленность, производство (7100)
Психология (8694)
психология, педагогика (4121)
Радиоэлектроника (443)
Реклама (952)
Религия и мифология (2967)
Риторика (23)
Сексология (748)
Социология (4876)
Статистика (95)
Страхование (107)
Строительные науки (7)
Строительство (2004)
Схемотехника (15)
Таможенная система (663)
Теория государства и права (240)
Теория организации (39)
Теплотехника (25)
Технология (624)
Товароведение (16)
Транспорт (2652)
Трудовое право (136)
Туризм (90)
Уголовное право и процесс (406)
Управление (95)
Управленческие науки (24)
Физика (3463)
Физкультура и спорт (4482)
Философия (7216)
Финансовые науки (4592)
Финансы (5386)
Фотография (3)
Химия (2244)
Хозяйственное право (23)
Цифровые устройства (29)
Экологическое право (35)
Экология (4517)
Экономика (20645)
Экономико-математическое моделирование (666)
Экономическая география (119)
Экономическая теория (2573)
Этика (889)
Юриспруденция (288)
Языковедение (148)
Языкознание, филология (1140)

Реферат: Нахождение кратчайшего маршрута между двумя городами по существующей сети дорог

Название: Нахождение кратчайшего маршрута между двумя городами по существующей сети дорог
Раздел: Рефераты по информатике, программированию
Тип: реферат Добавлен 01:38:55 02 сентября 2005 Похожие работы
Просмотров: 2560 Комментариев: 3 Оценило: 1 человек Средний балл: 5 Оценка: неизвестно     Скачать

Информационная карта

5013 Информационная 5418 Исходящий 7992 Инвентарный 5436 Инвентарный

карта АИП номер, дата номер ФАП номер ВНТИЦ


ИКАП ———— —————————————— ——————————————— ———————————————

| 50 | | | | | | |

———— —————————————— ——————————————— ———————————————

7839 Тип ЭВМ 7902 Тип и версия ОС 5715 Инструмен- 7848 Оперативная

тальное ПО память

——————————— —————————————————— ——————————————— ——————————————

| | | | | | | |

——————————— —————————————————— ——————————————— ——————————————

7965 Разновидность ПС 73 Библиотека программ 5679 Код программы по

46 Программный модуль 82 Программная система ЕСПД

55 Программа 91 Программный комплекс ————————————————

64 Пакет программ 28 Информационная структура | |

19 Комплект программ 37 Прочее | |

————————————————

7884 Объем программы ————————————— 7362 Срок окончания ———————————————

| | разработки | |

————————————— ———————————————

7947 Описание программы ————————— 4956 Распространение 4511 Сертифика-

| | ПП ция

7956 Описание применения|—————————| 35 Организация- 34 Сертифициро-

| | разработчик вана

|—————————|

7974 РТО | | 44 Организация, 43 Несертифици-

————————— ведущая ФАП рована


Сведения об организации, представляющей АИП во ВНТИЦ


2457 Код ОКПО 2934 Телефон 2394 Телефакс 2754 Город

—————————————— —————————————— ————————————— ———————————————————

—————————————— —————————————— ————————————— ———————————————————

1332 Сокращенное наименование министерства (ведомства) 2403 Код ВНТИЦ

————————————————————————————————————————————————————— ———————————————

————————————————————————————————————————————————————— ———————————————

2151 Полное наименование организации

———————————————————————————————————————————————————————————————————————

| |

———————————————————————————————————————————————————————————————————————

2358 Сокращенное наименование организации —————————————————————————————

—————————————————————————————

2655 Адрес организации

———————————————————————————————————————————————————————————————————————

| |

———————————————————————————————————————————————————————————————————————

Сведения об организации-разработчике


2988 Телефон 3087 Телефакс 2781 Город

—————————————— ————————————— ————————————————————————————————————

—————————————— ————————————— ————————————————————————————————————

2187 Наименование организации

———————————————————————————————————————————————————————————————————————

| |

———————————————————————————————————————————————————————————————————————

2385 Сокращенное наименование организации —————————————————————————————

| |

—————————————————————————————

2682 Адрес организации

———————————————————————————————————————————————————————————————————————

———————————————————————————————————————————————————————————————————————

6183 Авторы (разработчики ПС)

———————————————————————————————————————————————————————————————————————

| |

———————————————————————————————————————————————————————————————————————

9045 Наименование программы

———————————————————————————————————————————————————————————————————————

| |

| |

———————————————————————————————————————————————————————————————————————

9117 Реферат

———————————————————————————————————————————————————————————————————————

| |

| |

| |

| |

| |

| |

| |

| |

| |

| —————————————————————|

| |5436 |

| | |

———————————————————————————————————————————————————————————————————————

Фамилия, инициалы Должность Уч.степень, Подпись МП

звание

———————————————————————————————————————————————————————————————————————

|Руководитель |6111 |6311 |6210 | |

|организации | | | | |

|—————————————|——————————————————————|——————————|————————————|——————————|

|Руководитель |6120 |6320 |6228 | |

|разр.(ФАП) | | | | |

———————————————————————————————————————————————————————————————————————

5634 Индексы УДК 7434 Дата 7506 Входящий номер

——————————————————————————————————— ———————— ——————————————————————

——————————————————————————————————— ———————— ——————————————————————

5616 Коды тематических рубрик

———————————————————————————————————————————————————————————————————————

| . . | . | . . | . | . . | . | . . | . | . . |

———————————————————————————————————————————————————————————————————————

5643 Ключевое слово

———————————————————————————————————————————————————————————————————————

|———————————————————————————————————————————————————————————————————————|

|———————————————————————————————————————————————————————————————————————|

|———————————————————————————————————————————————————————————————————————|

|———————————————————————————————————————————————————————————————————————|

|———————————————————————————————————————————————————————————————————————|

|———————————————————————————————————————————————————————————————————————|

———————————————————————————————————————————————————————————————————————



Введение


Проникновение математики в экономическую науку связано с преодолением значительных трудностей. В этом отчасти была “повинна” математика, развивающаяся на протяжении нескольких веков в основном в связи с потребностями физики и техники. Ног главные причины лежат все же в природе экономических процессов, в специфики экономической науки.

Большинство объектов, изучаемых экономической наукой, может быть охарактеризовано кибернетическим понятием сложная система.

Наиболее распространено понимание системы как совокупность элементов, находящихся во взаимодействии и образующих некоторую целостность, единство. Важным качеством любой системы является эмерджентность – наличие таких свойств, которые не присущи ни одному из элементов, входящих в систему. Поэтому при изучении систем недостаточно пользоваться методом их расчленения на элементы с последующим изучением этих элементов в отдельности. Одна из трудностей экономических исследований – в том, что почти не существует экономических объектов, которые можно было бы рассматривать как отдельные (внесистемные) элементы.

Сложность системы определяется количеством входящих в нее элементов, связями между этими элементами, а также взаимоотношениями между системой и средой. Экономика страны обладает всеми признаками очень сложной системы. Она объединяет огромное число элементов, отличается многообразием внутренних связей с другими системами (природная среда, экономика других стран и т. д.). В народном хозяйстве взаимодействуют природные, технологические, социальные процессы, объективные и субъективные факторы.

Сложность экономики иногда рассматривалась как обоснование невозможности ее моделирования, изучение средствами математики. Но такая точка зрения в принципе неверна. Моделировать можно объект любой природы и любой сложности. И как раз сложные объекты представляют собой наибольший интерес для моделирования; именно здесь моделирование может дать результаты, которые нельзя получить другими способами исследования.

Потенциальная возможность математического моделирования любых экономических объектов и процессов не означает, разумеется, ее успешной осуществимости при данном уровне экономических и математических знаний, имеющийся конкретной информации и вычислительной технике. И хотя нельзя указать абсолютные границы математической формализуемости экономических проблем, всегда будут существовать еще неформализованные проблемы, а также ситуации, где математическое моделирование недостаточно эффективно.


1. Краткое описание модели поставленной задачи


Благодаря своему широкому применению, теория о нахождении кратчайших путей в последнее время интенсивно развивается.

Нахождение кратчайшего пути - жизненно необходимо и используется практически везде, начиная от нахождения оптимального маршрута между двумя объектами на местности (напр. кратчайший путь от дома до академии),также используется в системах автопилота, используется для нахождения оптимального маршрута при перевозках коммутации информационного пакета Internet и мн. др.


Кратчайший путь рассматривается при помощи некоторого математического объекта, называемого графом. Граф задается множеством точек (вершин) и множеством линий (ребер), соединяющих все или часть этих точек.

Сетевые модели используются для решения следующих задач:

  1. проектирование газопровода;

  2. нахождение кратчайшего маршрута между городами по сети дорог;

  3. определение максимальной пропускной способности при транспортировки нефти;

  4. составление временных графиков работ и др.


Существуют три наиболее эффективных алгоритма нахождения кратчайшего пути:

1) алгоритм построения минимального основного дерева. Предполагает соединение всех узлов сети с помощью путей наименьшей длины.

2) алгоритм Дейкстры. Используется для нахождения кратчайшего пути между заданным исходным узлом и любым другим узлом сети

3) алгоритм Флойда. Используется для нахождения оптимального маршрута между любыми двумя узлами сети.


Основные определения


Сеть состоит из множества улов, связанных дугами (или ребрами). Таким образом, сеть описывается парой множеств (N,A), где N – множество узлов, а A – множество ребер. Например, сеть, показанная на рис. 1, описывается след образом.


N = {1, 2, 3, 4, 5},

A = {(1, 3), (1, 2), (2, 3), (2, 4), (2, 5), (3, 4), (3, 5), (4, 5)}.



С каждым типом сети связан определенный тип потоков (например, транспортный поток нефти в нефтепроводах или автомобильные потоки в сети дорог). В общем случае потоки в сети ограничены пропускной способностью ее ребер, которая может быть как конечной, так и бесконечной.

Ребро называется направленным, или ориентированным (и в этом случае ребро будем называть дугой), если в одном направлении возможен только положительный поток, а в противоположном – только нулевой. В ориентированной сети все ребра ориентированы.

Путем называется последовательность различных ребер, соединяющих два узла, независимо от направления от направления потока в каждом ребре. Путь формирует цикл, если начальный и конечный узлы совпадают. Например, на рис. 2 ребра (2, 3), (3, 4) и (4, 2) составляют цикл. Ориентированный цикл – это цикл, в котором все дуги ориентированы в определенном направлении.

Связная сеть – такая сеть, у которой любые два узла связаны по крайней мере одним путем. На рис. 1 показан именно такой тип сети и не имеющий циклов. Остовное дерево – это дерево, содержащая все узлы сети. На рис. 2 показаны дерево и Остовное дерево для сети из рис. 1.



2. Математическая формулировка задачи, обоснование

Алгоритм Флойда

Алгоритм Флойда находит кратчайший путь между любыми двумя узлами сети. В этом алгоритме сеть представлена в виде квадратной матрицы с n строками и n столбцами. Элемент (i ,j) равен расстоянию dij от узла i к узлу j, которое имеет конечное значение, если существует дуга (i ,j), и равен бесконечности в противном случае.

Покажем сначала основную идею метода Флойда. Пусть есть три узла i, j и k и заданы расстояния между ними (рис. 3). Если выполняется неравенство dij + djk < dik, то целесообразно заменить путь i → k путем i → j → k. Такая замена (далее ее будем условно называть треугольным оператором) выполняется систематически в процессе выполнения алгоритма Флойда.



Алгоритм Флойда требует выполнения следующих действий.

Шаг 0. Определяем начальную матрицу расстояний D0 и матрицу последовательности

узлов S0. Диагональные элементы обеих матриц помечаются знаком “ – “,

показывающим, что эти элементы в вычислениях не участвуют. Полагаем k=1.


Основной шаг. Задаем строку k и столбец k как ведущую строку и ведущий столбец.

Рассматриваем возможность применения треугольного оператора ко всем элементам dij матрицы Dk-1. Если выполняется неравенство


dij + djk < dik (i ≠k, j≠k, i ≠j),


тогда выполняем следующие действия :

  1. создаем матрицу Dk путем замены в матрице Dk-1 элемента dij на сумму dij + djk, (рис. 4)

  2. создаем матрицу Sk путем замены в матрице Sk-1 элемента sij на k. Полагаем k=k+1 и повторяют шаг k. (рис. 5)

d12

d1j

d1n

d21

d2i

d2n

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

di1

di2

dij

din

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

dn1

dn2

dnj



рис. 4




2 j n
1 j n

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

1 2 j n

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

1 2

j



рис. 5



После реализации n шагов алгоритма определение по матрицам Dn и Sn кратчайшего пути между узлами i и j выполняется по следующим правилам .

  1. Расстояние между узлами i и j равно элементу dij в матрице Dn.

  2. Промежуточные узлы пути от узла i до узла j определяем по матрице Sn. Пусть sij = k, тогда имеем путь i → j → k. Если далее sik = k и ski = j, тогда считаем, что весь путь определен, так как найдены все промежуточные узлы. В противном случае повторяем описанную процедуру для путей от узла i к узлу k и от узла k к узлу j.


3. Численное решение показательного примера


Найдем для сети, показанной на рисунке 5, кратчайшие пути между любыми двумя узлами. Расстояния между узлами этой сети проставлены на рисунке возле соответствующих ребер. Ребро (3,5) ориентировано, поэтому не допускается движение от узла 5 к узлу 3. Все остальные ребра допускают движение в обе стороны.




Шаг 0. Начальное решение матрицы D0 и S0 строятся непосредственно по заданной схеме

сети. Матрица D0 симметрична, за исключением пары элементов d35 и d53, где d35 = ∞ (поскольку невозможен переход от узла 5 к узлу 3).


рис. 8

D0

1

2

3

4

5

1

100 30

2

100 20 15

3

30 20 10

4

15 10 50

5

60 50

S0

1

2

3

4

5

1

2 3 4 5

2

1 3 4 5

3

1 2 4 5

4

1 2 3 5

5

1 2 3 4


Шаг 1. В матрице D0 выделены ведущие строка и столбец (k=1) (рис. 8). После этого каждый элемент проверяется с помощью треугольного оператора. Таким образом, чтобы на основе матриц D0 и S0 получить матрицы D1 и S1, выполняем следующие действия:

  1. проверяем d32 > d31 + d12 = 20 > 30 + 100 = 20 > 130 если условие принимает истину, то устанавливаем S32 = 1 ,а если нет тогда все так и остается.

Матрицы D1 и S1 имеют следующий вид (см. рис. 9):

рис. 9

D1

1

2

3

4

5

1

100 30

2

100 20 15

3

30 20 10

4

15 10 50

5

60 50

S1

1

2

3

4

5

1

2 3 4 5

2

1 3 4 5

3

1 2 4 5

4

1 2 3 5

5

1 2 3 4


Шаг 2. Полагаем k=2. Треугольный оператор применяется к элементам матриц D1 и S1,

выделенным двойной рамкой. В результате получаем матрицы D2 и S2 (см. рис.10):

рис. 10

D2

1

2

3

4

5

1

100 30 115

2

100 20 15

3

30 20 10

4

115 15 10 50

5

60 50

S2

1

2

3

4

5

1

2 3 2 5

2

1 3 4 5

3

1 2 4 5

4

2 2 3 5

5

1 2 3 4


Шаг 3. Полагаем k=3. В матрице D2 и S2 выделены ведущие строка и столбец.

Треугольный оператор применяется к элементам матриц D2 и S2, выделенные двойной рамкой. В результате получаем матрицы D3 и S3(см. рис.11):

рис. 11

D3

1

2

3

4

5

1

50 30 40

2

50 20 15

3

30 20 10

4

40 15 10 50

5

90 80 60 50

S3

1

2

3

4

5

1

3 3 3 5

2

3 3 4 5

3

1 2 4 5

4

3 2 3 5

5

3 3 3 4


Шаг 4. Полагаем k=4. Выделены ведущие строка и столбец в матрице D3 и S3.

Получаем новые матрицы (см. рис.12):

рис. 12

D4

1

2

3

4

5

1

50 30 40 90

2

50 20 15 65

3

30 20 10 60

4

40 15 10 50

5

90 65 60 50

S4

1

2

3

4

5

1

3 3 3 4

2

3 3 4 4

3

1 2 4 4

4

3 2 3 5

5

3 4 3 4


Шаг 5. Полагаем k=4. Ведущие строка и столбец в матрице D4 и S4 выделены. Никаких

действий на этом этапе не выполняем; вычисления закончены.

Конечные матрицы D4 и S4 содержат всю информацию, необходимую для определения кратчайших путей между любыми двумя узлами сети.

Для нахождения соответствующих маршрутов напомним, что сегмент маршрута (i,j) состоит из ребра (i,j) только в том случае, когда sij=j. В противном случае узлы i и j связаны, по крайней мере, через один промежуточный узел.


4. Описание алгоритма автоматизированных расчетов


  1. Cоставляется начальная матрица расстояний D0 и матрица последовательности узлов S0. В каждой ячейке матрицы D пишется элемент dij, который определяет расстояние между узлом i и узлом j, матрица S заполняется автоматически . Элемент, в котором i==j помечается “—“, он в вычислении не участвует.


  1. Шаг 1. Пока k<=n-1 выполняются следующие действия.

Определяем k-ую стоку и k-ый столбец как ведущую строку и ведущий столбец.

а) осуществляется переборка всех элементов, если dik+dkjij, то элемент dij заменяется на сумму dij+dkj. При условии, что i≠k, j≠k и j≠i.

б) cоставляется матрица расстояний D1 в соответствии с заменами на шаге 1 и матрица последовательности узлов, в котором элементы sij соответствующие элементам dij заменяется на k.

  1. Полагается, что k=k+1 и повторяется шаг 2.


5. Расчет экономической эффективности расчетной модели


Решение задачи сетевого моделирования при помощи программы курсовой работы по теме “Нахождение кратчайшего маршрута между двумя городами по существующей сети дорог” рассчитывает минимальное расстояние между любыми двумя пунктами с большой точностью, что не происходит при решение таких задач вручную. Результат, получаемый при решении данной задачи отличается от ручного решения тем, что человеку гораздо удобнее использовать ресурсы компьютера, а не заниматься рутинной работой, решая однотипные задачи вручную, что может привести к ошибочным результатам.


Пример некорректных данных с точки зрения данной модели


Некорректными данными с точки зрения выбранной модели являются данные, которые не удовлетворяют условиям ограничения данной модели. Например: при вводе отрицательного расстояния между городами то система выдаст сообщение «Расстояние между городами не может быть отрицательным»


Математический анализ найденного решения


Математический анализ решения задач из темы “Нахождение кратчайшего маршрута между двумя городами по существующей сети дорог” показывает. Что если при вводе входных данных не было допущено ошибки, т. е. входные данные удовлетворяют установленным для системы ограничениям, то полученное решение действительно будет соответствовать поставленной задаче.


Экономический анализ полученного решения


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


6. Постановка задачи на программирование

Ограничения модели


Данный проект имеет следующие ограничения:

  1. Количество вершин должно быть в диапазоне (i=3;i<=50);

  2. расстояния между одним и тем же узлом быть не может;

  3. Если между вершинами нет расстояния - вводится любое отрицательное число.

  4. Расстояние не может быть равно 0.


Техническое задание

Программа предназначена для вычисления кратчайшего пути между всеми городами заданной сети дорог.


Задание на проектирование

Результатами проектирования являются:

  1. Рассмотрение результатов анализа и проверка их полноты.

Достоверный ответ на поставленную задачу - это матрица действительных чисел, определяющая расстояние между любыми двумя узлами сети.

  1. Определение критических участков проекта и оценка ограничений проекта.

Данный проект имеет следующие ограничения:

а) число узлов ограничено (от 3 до 50);

б) Если между вершинами нет расстояния - вводится любое отрицательное число;

в) расстояния между одним и тем же узлом быть не может;

г) Расстояние не может быть равно 0;

  1. Определение архитектуры системы.

Windows 98, Turbo C++ IDE.

  1. Принятие решений об использовании продуктов других разработчиков, о способах интеграции и механизмов обмена информацией с другими программами.

Продукт не имеет механизмов обмена информацией с другими программами.


Программа может использоваться и копироваться любым пользователем в системе Windows.

  1. Проектирование процесса и кода: выбор средств разработки, определение интерфейсов программ, отображение функций системы на ее модуле и определение спецификации модулей.

Программа выполняет нахождении кратчайшего пути между двумя заданными точками методом Флойда.

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

Задача разбита на подзадачи (программа на модули):

1-ая часть – ввод начальных расстояний.

2-ой частью является определение ведущей строки и ведущего столбца.

3-ей – возможности применения треугольного оператора и произведение нужной замены в двух матрицах (расстояний и последовательности узлов).

2-ая и 3-я часть выполняются такое число раз, сколько узлов сети.

4-ая часть выводит результат на экран.

При программировании модулей словесный алгоритм переводиться в соответствующие операторы ЯП. 2-ой и 3-ий модули выполняются в цикле.

  1. Определение требований к процессу тестирования.

Тестирование (Testing) – это этап разработки программы, в процессе которого проверяется работоспособность программы, не содержащей явных ошибок

Тестирование производиться с помощью тестов, совокупностью входных данных, а также точного описания вех результатов, которые должна выработать программа на этих данных. Тесты могут быть взяты из различных источников или разработаны самим программистом.

Все результаты сравниваются с данными, которые были получены при решении задачи вручную.

  1. Определение требований безопасности системы.

Данный продукт не связан с другими программами, кроме его запускаемого кода (файла *.exe)


Обоснование выбора языка программирования

Язык Си (разработал Деннисом Ритчи в 1972 г.) соединяет свойства языка высокого уровня с возможностями эффективного использования ресурсов компьютера, которые обычно достигаются только при программировании на языке Ассемблера.

Си не очень прост в изучении и требует тщательности в программировании, но позволяет создавать сложные и весьма эффективные программы. Потому я и выбрал в качестве языка программирования Си.


7. Руководство пользователю

Данная программа находит кратчайшее расстояние между городами по существующей сети дорог. При запуске программа спрашивает, какое количество вершин сети (от 3 до 50) .После чего последовательно вводится расстояние между вершинами (если между вершинами нет расстояния, то ставиться любое отрицательное число).

После ввода данных на экран выводиться матрица расстояний и матрица последовательности узлов.



Если в матрице последовательности узлов sij ≠ j, то города i и j связаны, по крайней

мере, через один промежуточный узел. Рассмотрим этот случай на примере (см. «Численное решение показательного примера»):

Поскольку s15 = 4 и s45 = 5, сначала кратчайший маршрут между узлами 1 и 5 будет иметь вид 1→4→5. Но, т. к. s14 ≠ 4, узлы 1 и 4 в определяемом пути не связаны одним ребром (но в исходной сети они должны быть связаны непосредственно). Далее следует

определить промежуточный узел (узлы) между первым и четвертым узлами. Имеем s14=2 и s24=4, поэтому маршрут 1→4 заменяем на 1→2→4. Поскольку s12=2 и s24=4, других промежуточных узлов нет. Комбинируя определенные сегменты маршрута, окончательно получаем следующий кратчайший путь от узла 1 к узлу 5: 1→2→4→5. Длина этого пути равна 12 милям.


Заключение


Данная курсовая работа включает в себя два предмета: «Основы алгоритмизации и программирования» и «Математические методы».

В курсовой работе были рассмотрены следующие вопросы:

  • Рассмотрен и дан алгоритм решения сетевых задач методом Флойда.

  • Рассмотрен выбор языка программирования.

  • Даны ограничения модели.

  • Написана программа для решения данной модели.

  • Даны инструкции пользователю.

Данная программа была протестирована на многих примерах и на разных ПК и при этом выдавала правильные результат.


Список использованной литературы


  1. «Введение в исследование операций» Х.А.Таха;

  2. «Математика для экономических специальностей» М.С.Красс;

  3. «Основы математики и ее приложение в экономическом образовании» М.С. Красс, Б.П.Чупрынов;

  4. «Экономико-математические требования» В.А.Абчук.

  5. «C/C++ в задачах и примерах» Н.Культин.

  6. «Turbo Pascal в задачах и примерах» Н.Культин.

  7. «Информатика» Л.З.Шауцукова.

  8. «Дискретная математика для программистов» Ф.А.Новиков.

  9. «Основы алгоритмизации и программирования» О.Л.Гальцына, И.И.Попов.

  10. «C++ Builder 6 справочное пособие» А.Я.Архангельский.

  11. «Теория графов» О.И.Леонов.

  12. ссылка на алгоритм Флойда http://algolist.manual.ru/maths/graphs/shortpath/floyd.php

  13. ссылка “теория графа” http://www.csu.ac.ru/~yan/mvs2002/Mvslab_7.htm

  14. ссылка на математические графы http://www.sura.ru/maxwell/scripts/math-graphs.php

  15. ссылка “вопросы о графах” http://shade.msu.ru/~mab/summer2002/test/graph.html

  16. ссылка алгоритмы на Basic http://www.rsdn.ru/res/book/prog/basic_algorithms.xml

  17. ссылка http://olympiads.ru/sis/2003/plans/exam_c.doc

  18. ссылка на все алгоритмы http://alglib.dore.ru/all.html

  19. ссылка “теорию графов“ http://pco.iis.nsk.su/~dyatlov/alg/graph/index.php

  20. ссылка на различные алгоритмы http://www.citforum.ru/book/algoritm/algoritm_c.shtml

  21. ссылка “дискретная математика” http://ermak.cs.nstu.ru/site/students/rta/control.phtm


Приложение

Описание алгоритма в виде блок-схемы





Листинг программы

#include

#include

#define MAX_VERT 50


int main ( void )


{

clrscr ( );

int k = 0,

i = 0,

j = 0,

n = 0;

int D [ MAX_VERT ][ MAX_VERT ];

int S [ MAX_VERT ][ MAX_VERT ];


/*-------->8-------------start>>Vvod*dannix----------------->8--------------*/


while ( n < 3 || n > MAX_VERT ){

printf ( "\nvvedite kol_vo versin v seti [ 2 >> %d ] : ", MAX_VERT );

scanf ( "%i", &n );

if ( n > MAX_VERT || n < 3 )

printf ( "\nkol_vo versin dolzno bit v diapozone ot [ 2 >> %d ] ! \n", MAX_VERT );

};

printf ( "\n" );

for ( i=0;i

for ( j=0;j

if ( i = = j ) D[i][j] = 0;

else { printf ( "A [ %i , %i ] = ", i+1, j+1 );

scanf ( "%i", &D[i][j] );

};

};

};


for ( i=0;i

for ( j=0;j

if ( i==j ) S[i][j] = 0;

else S[i][j] = j+1;

};

};


/*-------->8---------------end>>Vvod*dannix----------------->8--------------*/

/*--------------------------------------------------------------------------------------*/

/*-------->8-------------start>>resenia*dannix-------------->8---------------*/


for( k=0;k

for( i=0;i

if ( k==i ) continue;

for ( j=0;j

if ( k = = j || i = = j ) continue;

if ( ( ( D[i][j] > ( D[i][k] + D[k][j] ) )

|| D[i][j] < 0 ) && D[k][j] > 0

&& D[i][k] > 0 ){

D[i][j] = ( D[k][j] + D[i][k] );

S[i][j] = k+1;

};

};

};

};


/*-------->8---------------end>>resenia*dannix-------------->8--------------*/

/*--------------------------------------------------------------------------------------*/

/*-------->8-------------start>>vivoda*dannix--------------->8---------------*/


printf ( "\n\t" );

printf ( "Matrixa Rastoqnij :" );

printf ( "\n\n" );

for ( i=0;i

for ( j=0;j

printf ( "%5i", D[i][j] );

};

printf ( "\n" );

};

printf ( "\n\t" );

printf ( "Matrixa Posledovatelnosti yzlov :" );

printf ( "\n\n" );

for ( i=0;i

for ( j=0;j

printf ( "%5i", S[i][j] );

};

printf ( "\n" );

};


/*-------->8---------------end>>vivoda*dannix--------------->8--------------*/


printf ( "\n < Nazmite lubyu klavisy ! >" );

getch ( );

return 0;

};

принял


…………………………………….

Лист
Н.контр.


23

Утв.

Лист






Министерство образования Российской Федерации

Департамент образования и науки Краснодарского края

Колледж «………………………..»


Курсовая работа


по предмету: «Математические методы»

на тему: «Нахождение кратчайшего маршрута между двумя городами по существующей сети дорог»


Выполнил:

Студент

Группы ……….. …………..


шифр: 2203021


Руководитель …………………...


Дата


г. Краснодар

2004



СОДЕРЖАНИЕ


Введение. 3
1.Краткое описание модели поставленной задачи 4
2. Математическая формулировка задачи, обоснование 6
3. Численное решение показательного примера 9
4. Описание алгоритма автоматизированных расчетов 11
5. Расчет экономической эффективности расчетной модели 12
6. Постановка задачи на программирование 13
7. Руководство пользователю 16
Заключение. 18
Список использованной литературы. 19
Приложение. 20






……………………………..






Изм Лист № документа Подпись Дата
Разраб. ……………..

Нахождение кратчайшего маршрута между двумя городами по существующей сети дорог Лит. Лист Листов
Пров. ……………..






Т.контр





Н. контр.


Утв


Оценить/Добавить комментарий
Имя
Оценка
Комментарии:
Где скачать еще рефератов? Здесь: letsdoit777.blogspot.com
Евгений22:07:57 18 марта 2016
Кто еще хочет зарабатывать от 9000 рублей в день "Чистых Денег"? Узнайте как: business1777.blogspot.com ! Cпециально для студентов!
13:23:23 24 ноября 2015
отличная работа...
17:03:34 06 мая 2011Оценка: 5 - Отлично

Работы, похожие на Реферат: Нахождение кратчайшего маршрута между двумя городами по существующей сети дорог
Основы дискретной математики
Федеральное агентство по образованию Новомосковский институт (филиал) Государственного образовательного учреждения высшего профессионального ...
В алгоритме поиск подходящего места осуществляется как бы просеиванием x: при движении по последовательности и сравнении с очередным a[j]. Затем х либо вставляется на свободное ...
Этот алгоритм выдает субоптимальное решение задачи коммивояжера, генерируя гамильтоновы циклы в нагруженном графе с множеством вершин V. Цикл, полученный в результате работы ...
Раздел: Рефераты по информатике, программированию
Тип: учебное пособие Просмотров: 4172 Комментариев: 2 Похожие работы
Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать
Разработка системы маршрутизации в глобальных сетях(протокол RIP для ...
Введение 3 1 Протоколы TCP/IP . Принципы, протоколы и архитектура 6 1.1 Структура стека протоколов TCP/IP 6 1.2 Протокол IP 12 1.3 Принципы построения ...
Некоторые алгоритмы маршрутизации предполагают, что конечный узел источника определяет весь маршрут.
Во время первого обмена узел B узнает, что A заработал и вносит в свою таблицу маршрутизации "1" как расстояние до A; все остальные узлы в этот момент по-прежнему считают A ...
Раздел: Рефераты по информатике, программированию
Тип: реферат Просмотров: 5036 Комментариев: 2 Похожие работы
Оценило: 2 человек Средний балл: 4.5 Оценка: неизвестно     Скачать
Нейрокомпьютерные системы
Введение. ПОЧЕМУ ИМЕННО ИСКУССТВЕННЫЕ НЕЙРОННЫЕ СЕТИ? После двух десятилетий почти полного забвения интерес к искусственным нейронным сетям быстро ...
где W ij (n) - значение веса от нейрона i к нейрону j до подстройки, W ij (п + 1) - значение веса от нейрона i к нейрону j после подстройки, . - коэффициент скорости обучения, OUT ...
Она может быть сформулирована следующим образом: для некоторой группы городов с заданными расстояниями между ними требуется найти кратчайший маршрут с посещением каждого города ...
Раздел: Рефераты по информатике, программированию
Тип: реферат Просмотров: 1761 Комментариев: 4 Похожие работы
Оценило: 4 человек Средний балл: 4.8 Оценка: неизвестно     Скачать
Задача остовных деревьев в k-связном графе
... Молдавский Государственный Университет Кафедра Информатики и Дискретной Оптимизации Дипломная работа: "Задача остовных деревьев в k-связном графе"
Введем, наконец, матрицу смежности ребер I(G), в которой и строки и столбцы отвечают ребрам G. Для простоты предположим.
Из ранее известных результатов "глобальным ананлогом" теоремы Менгера в некоторой степени является доказанный результат: в графе G с реберной связностью (G)k существуют k остовных ...
Раздел: Рефераты по математике
Тип: реферат Просмотров: 1728 Комментариев: 2 Похожие работы
Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать
Эйлеровы и гамильтоновы графы
Министерство народного образования Республики Дагестан Дагестанский Государственный Университет Курсовая работа Программирование задач на графах ...
Пусть [cij] - матрица весов ребер G. Используя алгоритм нахождения кратчайшей цепи, образуем |X-|*|X-| - матрицу D=[dij], где dij - вес цепи наименьшего веса, идущей из некоторой ...
Возьмём произвольную пару вершин j,k. Исключим непосредственное ребро D[j,k]. С помощью алгоритма Дейкстры найдём кратчайшее расстояние между городами j,.,k. Пусть это расстояние ...
Раздел: Рефераты по информатике, программированию
Тип: реферат Просмотров: 6743 Комментариев: 3 Похожие работы
Оценило: 1 человек Средний балл: 2 Оценка: неизвестно     Скачать
Основы C
Кафедра: Автоматика и Информационные Технологии ОСНОВЫ С ОГЛАВЛЕНИЕ Введение Глава 1. Основы языка Си 1.1. Алфавит 1.2. Основные конструкции Си 1.3 ...
printf(" В %d М содержится %d cm\n", I,J);
printf("Длина 1 строки= %d\n ",strlen(k))
Раздел: Рефераты по информатике, программированию
Тип: учебное пособие Просмотров: 1161 Комментариев: 2 Похожие работы
Оценило: 1 человек Средний балл: 5 Оценка: неизвестно     Скачать
Локальные сети на основе коммутаторов
Содержание Введение. Тенденция вытеснения концентраторов и маршрутизаторов коммутаторами Технологии коммутации кадров (frame switching) в локальных ...
Однако возможности этих устройств по увеличению максимально допустимого расстояния между двумя любыми узлами сети (которое называется диаметром сети) не очень велики - число ...
Если сервер подключен, например, к порту 4, то только 4-я строка матрицы и 4-ый столбец матрицы будут иметь отличные от нуля значения.
Раздел: Рефераты по информатике, программированию
Тип: реферат Просмотров: 6290 Комментариев: 5 Похожие работы
Оценило: 5 человек Средний балл: 4 Оценка: неизвестно     Скачать
Проектирование трансляторов
ЛЕКЦИЯ 1 СУЩНОСТЬ ПРЕДМЕТА. СОДЕРЖАНИЕ КП. СРОКИ. ОРГАНИЗАЦИЯ РАБОТ. МАТЕМАТИЧЕСКИЙ АППАРАТ. СТРУКТУРНАЯ СХЕМА ТРАНСЛЯТОРА. ПРОХОДЫ ТРАНСЛЯТОРА ...
чении i-ой строки и j-го столбца записывается отношение предшес-
Если в матрице предшествования (i,j)-ый элемент пуст (знак
Раздел: Рефераты по информатике, программированию
Тип: реферат Просмотров: 655 Комментариев: 3 Похожие работы
Оценило: 1 человек Средний балл: 5 Оценка: неизвестно     Скачать
Алгоритмы параллельных процессов при исследовании устойчивости ...
... Санкт-Петербургский государственный архитектурно-строительный университет Кафедра прикладной математики и информатики Дипломная работа АЛГОРИТМЫ ...
J_m - Количество ребер жесткости вдоль направления X;
printf ("X1 [%d] =%.3f\n",sqrtN * (i - 1) + j - 1,X1 [sqrtN * (i - 1) + j - 1])
Раздел: Рефераты по информатике, программированию
Тип: дипломная работа Просмотров: 639 Комментариев: 2 Похожие работы
Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать

Все работы, похожие на Реферат: Нахождение кратчайшего маршрута между двумя городами по существующей сети дорог (9260)

Назад
Меню
Главная
Рефераты
Благодарности
Опрос
Станете ли вы заказывать работу за деньги, если не найдете ее в Интернете?

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



Результаты(150195)
Комментарии (1830)
Copyright © 2005-2016 BestReferat.ru bestreferat@mail.ru       реклама на сайте

Рейтинг@Mail.ru