Файл: Алгоритмизация как обязательный этап разработки программы (Подходы к разработке программных систем).pdf

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

3. Программная разработка

3.1. Постановка задачи

Алгоритм Форда–Беллмана представляет собой специализированный алгоритм для нахождения кратчайшего пути в рамках обработки взвешенного графа. За отведенное время O(|V| × |E|) алгоритм Форда–Беллмана позволяет выполнить необходимый поиск кратчайшего пути от определенной вершины графа ко всем остальным.

Алгоритм Беллмана–Форда, в отличие от алгоритма Дейкстры допускает оперативную обработку рёбер обрабатываемого объекта, которые имеют отрицательный вес. Данный алгоритм был предложен независимо Ричардом Беллманом и Лестером Фордом.

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

Следует построить матрицу A_ij, элементы которой обозначают следующее: A_ij представляет собой длину наименьшего пути из s в i, который содержит не более j рёбер исследуемого графа.

Можно предположить, что граф содержащий 0 рёбер, может существовать только до вершины s. Таким образом, A_i0 является равным 0 при i = s, и +∞ в противном случае.

Теперь следует рассмотреть все возможные пути из s в i, содержащие ровно j рёбер исследуемого графа. Каждый такой путь является путем из j-1 ребра, к которому будет добавлено последнее ребро данного графа. Если на пути длины j-1 все данные уже будут подсчитаны, то определить j-й столбец матрицы не будет составлять особого труда.

Так выглядит алгоритм оперативного поиска длин кратчайшего пути в анализируемом графе без наличия отрицательных циклов:

for v V

do d[v] +

d[s] 0

for i 1 to |V| - 1

do for (u, v) E

if d[v] > d[u] + w(u, v)

then d[v] d[u] + w(u, v)

return d

В представленном алгоритме переменная V представляет собой специальное множество вершин исследуемого графа, переменная E представляет собой множество его рёбер, а переменная w является весовой функцией, которая задается на ребрах исследуемого графа (используется для возвращения длины полученной дуги, которая ведет из вершины u в вершину v), переменная d представляет собой массив, который содержит расстояния от вершины s до любой другой вершины исследуемого графа.

Внешний цикл будет выполнен |V| - 1 раз, в связи с тем, что наименьший путь не может включать большее число ребер исследуемого графа, иначе он будет содержать итерационный цикл, который точно можно будет исключить из вычисления.

Вместо массива d можно хранить всю анализируемую матрицу A, но это требует O(V²) достаточно большого количества вычислительной памяти. Зато при этом можно будет выполнить вычисление и самих кратчайших путей, а не только их непосредственной длины. Для этого необходимо завести дополнительную матрицу в виде массива P_ij.

Если элемент матрицы A_ij будет включать длину наименьшего по длине пути из s в i, который содержит j рёбер исследуемого графа, то P_ij будет включать предыдущую вершину до i в одном из таких кратчайших путей (ведь кратчайших путей в исследуемом графе может быть и несколько).

Теперь изучаемый алгоритм Форда-Беллмана будет выглядеть следующим образом:

for v V

for i 0 to |V| - 1

do A_vi +

A_s0 0

for i 1 to |V| - 1

do for (u, v) E

if A_vi > A_{u, i-1} + w(u, v)

then A_vi A_{u, i-1} + w(u, v)

P_vi u

После непосредственного исполнение представленного алгоритма элементы матрицы A_i,j будет включать длины кратчайших путей исследуемого графа от s до i с количеством ребер j, и из всех таких путей необходим будет выполнить выбор самого короткого пути. А сам кратчайший путь до вершины i с j ребрами может быть восстановлен следующим образом:

while j > 0

p[j] i

i P_ij

j j - 1

return p

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

После непосредственного запуска программа предлагает пользователю ввести имя файла с параметрами графа и необходимые вершины графа, между которыми будет вычисляться кратчайший путь. Графическое представление файла data.txt представлено на рис. 2.

Рисунок 2 – Граф

Например, пользователь вводит data.txt 1 7, это значит, что параметры графа будут взяты с заранее созданного информационного файла data.txt. Содержание файла data.txt

7 11

1 2 5

1 6 7

2 3 1

2 4 3

2 6 1

3 4 1

3 5 2

3 7 4

4 6 2

5 7 2

6 5 1

Значения 1 7 представляют собой вершины графа, между которыми и будет найден кратчайший путь.

3.2. Разработка алгоритма программы

Для практической реализации поставленной задачи необходимо выполнить следующие действия:

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

Приведем реализацию алгоритма Форда-Беллмана.

for (h=1 ; h<=N ;h++) {

i=0;

for (j=2 ; j<=N ; j++) {

for (k=1 ; k<=N ; k++) {

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

D[k]=D[j]+m[j][k] ;

i++;

// преобразуем полученный информационный массив расстояний

// в матрицу значений

for (l=2 ; l<=N ; l++) {

// (i-ая строка информационной матрицы является массивом

// расстояний на i-ом шаге)

W[i][l]=D[l];

// выполняем отслеживание улучшений полученного пути

// исследуемого графа

if (W[i][l]<W[i-1][l])

// выполняем запоминание вершины, через которую

// будет проходить данный путь

G[k][2]=j ;

}

Реализация функции для непосредственного нахождения возможных путей между данными вершинами в исследуемом графе не пересекающиеся по ребрам выглядит следующим образом

void PYTU () {

// пока путь будет существовать ...

while (D[F]<MAX) {

// выполняем вызов функции нахождения наименьшего

// расстояния для исследуемого графа

// без учета весов рёбер (все ребра будут иметь вес равный единице)

GRAF(v);

for (j=0 ; j<M ; j++)

// пройденные ребра будут удалены

v[Z[j+1]][Z[j]]=MAX;

}

// завершение функции

return;

}

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

for ( i=1 ; i<=N ; i++)

for ( j=1 ; j<=N ; j++) {

m[i][j]=MAX;

v[i][j]=MAX;

}

Исходный программный код разработанной программы представлен в Приложении.

3.3. Порядок работы с программой

После выполнения запуска программы необходимо будет ввести имя файла, которое содержит информацию о графе (имя файла txt.txt). Затем ввести необходимые узлы графа, для определения кратчайшего пути (например, вводим вершины 1 и 7). Результат работы программы представлен на рис. 3.

Рисунок 3 – Результат работы программы

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

Рисунок 4 – Результат работы программы

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

Рисунок 5 – Результат работы программы

Таким образом, был представлен процесс алгоритмизации и описание хода работы с программной системой, реализующей алгоритм Форда–Беллмана для нахождения кратчайшего пути в рамках взвешенного графа.

Заключение

В процессе выполнения данной работы были получены следующие результаты. Установлено, что существует широкий спектр методологий, которые придерживаются принципами и ценностями, заявленными в Agile Manifesto, к основным можно отнести следующие: Agile Modeling; Agile Unified Process; Agile Data Method; DSDM; Feature driven development; Getting Real; OpenUP; Scrum. Описанные методологии базируются на принципах и ценностях методологии Agile позволяя разработчикам выбрать наиболее подходящий инструмент разработки программных систем.

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

Процесс оказания услуг по разработке программной системы в рамках методологии Agile включает следующие стадии: определение проблемы практической реализации программной системы; определение различных вариантов решения выявленных проблем клиента; проверка рынка существующих программных систем, которые могут быть использованы в качестве альтернативных или основных вариантов решения проблем; разработка программного решения.

Установлено, что язык программирования С++ представляет собой компилируемый, статически типизированный язык программирования общего назначения. Поддерживает такие парадигмы программирования, как процедурное программирование, объектно-ориентированное программирование, обобщённое программирование.

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

Чаще всего в процессе программирования используются одномерные и двумерные массивы, поэтому можно рассмотреть только эти виды массивов для понимания данной темы.

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

В языках программирования существуют следующие циклические операторы: for; while; do while.

В качестве практической разработки была разработана программа, работающая по алгоритму Форда–Беллмана для нахождения кратчайшего пути в рамках взвешенного графа.

Алгоритм Беллмана–Форда, в отличие от алгоритма Дейкстры допускает обработку рёбер, которые имеют отрицательный вес. Данный алгоритм был предложен независимо Ричардом Беллманом и Лестером Фордом.

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

Гаврилов М.В. Информатика и информационные технологии: Учебник / М.В. Гаврилов, В.А. Климов. - Люберцы: Юрайт, 2016. – 383 c.
Гома Х. UML. Проектирование систем реального времени, распределенных и параллельных приложений / Х. Гома. - М.: ДМК, 2016. – 700 c.
Дарков А.В. Информационные технологии: теоретические основы: Учебное пособие / А.В. Дарков, Н.Н. Шапошников. - СПб.: Лань, 2016. – 448 c.
Довек Ж. Введение в теорию языков программирования / Ж. Довек, Ж.-Ж. Леви. - М.: ДМК, 2016. – 134 c.
Ерохин В.В. Безопасность информационных систем: учеб пособие / В.В. Ерохин, Д.А. Погонышева, И.Г. Степченко. - М.: Флинта, 2016. – 184 c.
Информационные технологии: Учебное пособие / Л.Г. Гагарина, Я.О. Теплова, Е.Л. Румянцева и др.; Под ред. Л.Г. Гагариной - М.: ИД ФОРУМ: НИЦ ИНФРА-М, 2015. – 320 c.
Информационные системы и технологии: Научное издание. / Под ред. Ю.Ф. Тельнова. - М.: ЮНИТИ, 2016. – 303 c.
Корнеев И.К. Информационные технологии в работе с документами: Учебник / И.К. Корнеев. - М.: Проспект, 2016. – 304 c.
Косиненко Н.С. Информационные системы и технологии в экономике: Учебное пособие для бакалавров / Н.С. Косиненко, И.Г. Фризен. - М.: Дашков и К, 2015. – 304 c.
Кулямин В.В. Технологии программирования. Компонентный подход / В.В. Кулямин. - М.: Интуит, 2014. – 463 c.
Куроуз Д. Компьютерные сети. Нисходящий подход / Д. Куроуз, К. Росс. - М.: Эксмо, 2016. – 912 c.
Лукин В.Н. Введение в проектирование баз данных / В.Н. Лукин. - М.: Вузовская книга, 2015. – 144 c.
Романова Ю.Д. Информационные технологии в управлении персоналом: Учебник и практикум / Ю.Д. Романова, Т.А. Винтова, П.Е. Коваль. - Люберцы: Юрайт, 2016. – 291 c.
Сальникова Л.С. Современные коммуникационные технологии в бизнесе: Учебник / Л.С. Сальникова. - М.: Аспект-Пресс, 2015. – 296 c.
Советов Б.Я. Информационные технологии: теоретические основы: Учебное пособие / Б.Я. Советов, В.В. Цехановский. - СПб.: Лань, 2016. – 448 c.