Функциональное и эксплуатационное назначение изделия, методологические ограничения. Требования к составу и параметрам технических средств. Описание алгоритма, входные и выходные данные. Стадии и этапы разработки, технико-экономическое обоснование.
Аннотация к работе
Если объекты изобразить точками (вершинами), а связи - линиями (ребрами), соединяющими соответствующие пары точек, то получится рисунок, называемый графом. Историю теории графов принято исчислять с 1736 г., когда Эйлер исследовал «задачу о кенигсбергских мостах»: построить в графе циклический путь, проходящий по одному разу через каждое ребро. Если ребра из множества А ориентированы, что обычно показывается стрелкой, то они называются дугами, и граф с такими ребрами называется ориентированным графом. Если узел j уже имеет метку [uj, k], полученную от другого узла k, и если ui dij <uj, тогда метка [uj, k] заменяется на [ui dij, i]. b) Если все узлы имеют постоянные метки, процесс вычислений заканчивается. Вычисляем метки для этих узлов, в результате получаем следующую таблицу меток: Узел Метка Статус меткиПрограмма обладает следующими характеристиками: удобный интерфейс; легкость в использовании; оптимальность при использовании физических ресурсов компьютера. Пользователь рисует на image вершины и ребраВ ходе данного курсового проекта была проанализирована поставленная задача, создана и протестирована программа определения достижимости населенного пункта в системе односторонних дорог.if ((point (points[i]).x>(X-10))&&(point (points[i]).x(Y-10))&&(point (points[i]).y<(Y 10))) {if (! fr) {f=true; ir =i; fr=true; this->Image1->Canvas->MOVETO (point(points[i]).x, point (points[i]).y);} else { DRAWLINE (this->Image1->Canvas, point (points[ir]).x, point (points[ir]).y, point (points[i]).x, point (points[i]).y, 10,20); DRAWLINE (this->Image1->Canvas, point (points[AROW-1]).x, point (points[AROW-1]).y, point (points[ACOL-1]).x, point (points[ACOL-1]).y, 10,20); for (int kversh=0; kversh<n; kversh ) {if (kversh!=versh) {int s=versh; // Номер исходной вершины int g=kversh; // Номер конечной вершины int * x; // Массив, содержащий единицы и нули для каждой вершины, // x[i]=0 - еще не найден кратчайший путь в i-ю вершину, // x[i]=1 - кратчайший путь в i-ю вершину уже найден x = new int [n]; h[s].
Введение
Определение достижимости населенного пункта в системе односторонних дорог рассматривается при помощи некоторого математического объекта, называемого графом.
Граф - это совокупность непустого множества вершин и наборов пар вершин (связей между вершинами).
Наиболее эффективным алгоритмом нахождения кратчайшего пути является алгоритм Дейкстры.
Основная задача данного курсового проекта: определение достижимости населенного пункта в системе односторонних дорог. Решить задачу можно средством программирования. В данной курсовой работе задача была решена в среде C Builder.
1. Техническое задание
Программа определения достижимости населенного пункта в системе односторонних дорог. Описание: даны несколько населенных пунктов, соединенных между собой (произвольным образом) односторонними дорогами некоторой длины. Определить, есть ли населенный пункт, из которого можно добраться до каждого из остальных пунктов, проезжая не более 100 км. Отобразить решение графически, выделив цветом найденный результат.
1.1 Основания для разработки
Основанием для разработки программы является задание к курсовому проекту по предмету «Программирование».
1.2 Функциональное и эксплуатационное назначение изделия
Перечень требований пользователя к программному изделию.
Программа должна обеспечивать: удобный интерфейс;
легкость в использовании;
оптимальность при использовании физических ресурсов компьютера.
1.3 Методологические ограничения программа алгоритм технический
Часто попадаются задачи, в условиях которых заданы некоторые объекты и между некоторыми их парами имеются определенные связи. Если объекты изобразить точками (вершинами), а связи - линиями (ребрами), соединяющими соответствующие пары точек, то получится рисунок, называемый графом. Историю теории графов принято исчислять с 1736 г., когда Эйлер исследовал «задачу о кенигсбергских мостах»: построить в графе циклический путь, проходящий по одному разу через каждое ребро. В середине 19-го века Гамильтон заинтересовался задачей построения циклического пути, проходящего по одному разу через каждую вершину графа. В это же время графы использовали для анализа электрических цепей (Кирхгоф) и химических молекул (Кэли). Развитие современной теории графов относится к 30-м годам 20-го столетия. Они нашли многочисленные применения в электротехнике, электронике, биологии, экономике, программировании и в других областях.
Общие сведения о графах
Граф G (рис. 1.1) задается множеством точек (вершин) х1, х2,…, xn. (которое обозначается через Х) и множеством линий (ребер) а1, а2,…, ам. (которое обозначается символом А), соединяющих между собой все или часть этих точек. Таким образом, граф G полностью задается (и обозначается) парой (Х, А). Если ребра из множества А ориентированы, что обычно показывается стрелкой, то они называются дугами, и граф с такими ребрами называется ориентированным графом.
Рис. 1.1 Граф G
Рис. 1.2 Пути и последовательности дуг
Например, если дорога имеет не двух-, а одностороннее движение то направление этого движения будет показано стрелкой.
Если ребра не имеют ориентации, то граф называется неориентированным, (двухстороннее движение).
В ориентированном графе дуга обозначается упорядоченной парой, состоящей из начальной и конечной вершин, ее направление предполагается заданным от первой вершины ко второй. Путем (или ориентированным маршрутом) ориентированного графа называется последовательность дуг, в которой конечная вершина всякой дуги, отличной от последней, является начальной вершиной следующей.
Так, на рис. 1.2 путями являются последовательности дуг: а6, а5, а9, а8, а4. (1) а1, а6, а5, а9. (2) а1, а6, а5, а9, а10, а6, а4. (3)
Ориентированной цепью (орцепью) называется такой путь, в котором каждая дуга используется не больше одного раза.
Простой орцепью называется такой путь, в котором каждая вершина используется не более одного раза. Например, путь (2).
Маршрут есть неориентированный «двойник» пути, и это понятие рассматривается в тех случаях, когда можно пренебречь направленностью дуг в графе. Таким образом, маршрут есть последовательность ребер a1, a2,…, aq, в которой каждое ребро аі, за исключением первого и последнего ребер, связано с ребрами аі-1 и аі 1 своими концевыми вершинами.
В графе, изображенном на рис. 1.2, являются маршрутами; две точки над символом дуги означают, что ее ориентацией пренебрегают, т.е. дуга рассматривается как неориентированное ребро. Также путь или маршрут можно изображать последовательностью вершин. Например, путь (1) будет выглядеть следующем образом: х2, х5, х4, х3, х5, х6. Иногда дугам графа приписываются числа, называемые весом, стоимостью, или длиной этой дуги. В этом случае граф называется графом с взвешенными дугами. А если вес приписывается вершинам графа, то тогда получается граф с взвешенными вершинами. Если в графе веса приписаны и дугам и вершинам, то он называется просто взвешенным.
При рассмотрении пути ? представленного последовательностью дуг (a1, a2,…, aq), за его вес принимается число l(?), равное сумме весов всех дуг, входящих в ?, т.е.
Алгоритм Дейкстры
На этом шаге приводится описание алгоритма Дейкстры.
Напомним, что алгоритм Дейкстры разработан для нахождения кратчайшего пути между заданным исходным узлом и любым другим узлом сети.
В процессе выполнения этого алгоритма при переходе от узла i к следующему узлу j используется специальная процедура пометки ребер. Обозначается через ui кратчайшее расстояние от исходного узла 1 до узла i, через dij - длину ребра (i, j). Тогда для узла j определим метку [uj, следующим образом: [uj, i] = [ui dij, i], dij >= 0
Метки узлов в алгоритме Дейкстры могут быть двух типов: временные и постоянные. Временная метка впоследствии может быть заменена на другую временную, если будет найден более короткий путь к данному узлу. Когда же станет очевидным, что не существует более короткого пути от исходного узла к данному, статус временной метки изменяется на постоянный.
Вычислительная схема алгоритма состоит из следующих шагов.
Шаг i. а) Вычисляются временные метки [ui dij, i] для всех узлов j, которые можно достичь непосредственно из узла i и которые не имеют постоянных меток. Если узел j уже имеет метку [uj, k], полученную от другого узла k, и если ui dij < uj, тогда метка [uj, k] заменяется на [ui dij, i]. b) Если все узлы имеют постоянные метки, процесс вычислений заканчивается. В противном случае выбирается метка [ur, s] с наименьшим значением расстояния ur среди всех временных меток (если таких меток несколько, то выбор произволен). Полагаем i = r и повторяем шаг i.
Пример. На рисунке 2 показана транспортная сеть, состоящая из пяти городов (расстояния между городами (в километрах) приведены возле соответствующих дуг сети). Необходимо найти кратчайшие расстояния от города 1 (узел 1) до всех остальных четырех городов.
Рис. 2. Транспортная сеть
Шаг 0. Назначаем узлу 1 постоянную метку [0, -].
Шаг 1. Из узла 1 можно достичь узлов 2 и 3. Вычисляем метки для этих узлов, в результате получаем следующую таблицу меток: Узел Метка Статус метки
1 [0, -] Постоянная
2 [0 100, 1] = [100, 1] Временная
3 [0 30, 1] = [30, 1] <-Временная
Среди узлов 2 и 3 узел 3 имеет наименьшее значение расстояния (u3 = 30). Поэтому статус метки этого узла изменяется на «постоянная».
Шаг 2. Из узла 3 (последнего узла с постоянной меткой) можно попасть в узлы 4 и 5. Получаем следующий список узлов: Узел Метка Статус метки
1 [0, -] Постоянная
2 [100, 1] Временная
3 [30, 1] Постоянная
4 [30 10, 3] = [40, 3] <-Временная
5 [30 60, 3] = [90, 3] Временная
Временный статус метки [40, 3] узла 4 заменяется на постоянный (u4 = 40).
Шаг 3. Из узла 4 можно достичь узлов 2 и 5. После вычисления меток получим следующий их список: Узел Метка Статус метки
1 [0, -] Постоянная
2 [40 15, 4] = [55, 4] <-Временная
3 [30, 1] Постоянная
4 [40, 3] Постоянная
5 [90, 3] или [40 50, 4] = [90, 4] Временная
Временная метка [100, 1], полученная узлом 2 на втором шаге, изменена на [55, 4]. Это указывает на то, что найден более короткий путь к этому узлу (проходящий через узел 4). На третьем шаге узел 5 получает две метки с одинаковым значением расстояния u5 = 90.
Шаг 4. Из узла 2 можно перейти только в узел 3, но он уже имеет постоянную метку, которую нельзя изменить. Поэтому на данном шаге получаем такой же список меток, как и на предыдущем шаге, но с единственным изменением: метка узла 2 получает статус постоянной. С временной меткой остается только узел 5, но так как из этого узла нельзя попасть ни в какой другой, процесс вычислений заканчивается.
Алгоритм позволяет проводить вычисления непосредственно по схеме сети, как показано на рисунке 3.
Рис. 3 Вычисления по схеме (в скобках указан номер шага)
Кратчайший маршрут между узлом 1 и любым другим узлом определяется начиная с узла назначения путем прохождения их в обратном направлении с помощью информации, представленной в постоянных метках. Например, для определения кратчайшего маршрута между узлами 1 и 2 получаем такую обратную последовательность узлов: (2) -> [55, 4] -> (4) -> [40, 3] -> (3) -> [30, 1] -> (1).
Таким образом, получаем путь 1->3->4->2 общей длиной 55 километров.
2. Программная совместимость
Программа должна работать под управлением операционной систем Windows 98/NT/XP/Vista/se7en/Win8. программа алгоритм технический
2.2 Требования к составу и параметрам технических средств
Для работы программы желательно иметь персональный компьютер со следующей характеристикой: микропроцессор Intel Pentium 4 с тактовой частотой 2.1 ГГЦ;
видеоадаптер SVGA с цветным дисплеем;
объем ОЗУ не менее 64 Мб;
объем свободного места на жестком диске 559 Кб;
USB-порт.
CD - ROM.
2.3 Описание алгоритма
Основным алгоритмом данной программы является нахождение кратчайшего пути из множества различных (Алгоритм Дейкстры).
2.4 Входные данные
Входными данными для моделируемых устройств, будут являться данные, вводимые пользователем с помощью мыши. Входными данными будет являться: - вершина;
Программа не является секретной. Предназначена для всех лиц. Используется в качестве решение поставленной задачи.
2.7 Мобильность
Для копирования программы с диска или flash-USB на компьютер необходимо: 1. Распаковать RAR-архив, расположенный на диске (flash-USB), в какую-либо папку на жестком диске компьютера.
2. Запустить программу.
2.8 Стадии и этапы разработки
Выполнение разработки должно включать две стадии: 1. Техническое задание
2. Пояснительная записка
На стадии «Техническое задание» проводится постановка задачи, разработка требований к программному изделию, изучение литературы по задаче и оформление документа «Техническое задание».
На стадии «Пояснительная записка» проводится разработка схем алгоритмов для каждого из функциональных модулей, физическое проектирование программного изделия. В заключение данного этапа оформляется документ «Пояснительная записка».
2.9 Технико-экономические показатели разработки
Программное изделие разрабатывается в качестве курсовой работы, поэтому технико-экономические показатели не рассчитываются.
2.10 Порядок контроля и приема
Данный программный продукт должен успешно пройти следующие тесты: Тест 1. Пользователь рисует на image вершины и ребра
Тест 2. Вводим данные в таблицу смежности
Тест 3. Выполнение задания, определение достижимости пункта
Тест 4. Вывод результата на экран
3. Пояснительная записка
Вывод
В ходе данного курсового проекта была проанализирована поставленная задача, создана и протестирована программа определения достижимости населенного пункта в системе односторонних дорог. Тестирование программы показало, что она находит кратчайший путь верно, при отсутствие пути выводит ошибку.
Можем констатировать, что курсовой проект сделан верно.
Список литературы
1. Программирование в С Builder 6 / А.Я. Архангельский, 2006 г. с. 1304.
2. Программирование. Принципы и практика использования C / Бьерн Издательство Вильямс, 2013 г. с. 1248
3. C для начинающих. Серия «Шаг за шагом» Г. Шилдт, 2010 г.с. 640 с