Алгоритм Форда-Беллмана
Понятие и структура алгоритма Беллмана-Форда. Разработка презентующей ее программы в среде Microsoft Visual Studio 2015, с помощью языка программирования С++. Основные модули программы и описание ее работы, листинг, а также оценка функциональности.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | курсовая работа |
| Язык | русский |
| Дата добавления | 22.02.2019 |
| Размер файла | 666,6 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
Алгоритм Форда-Беллмана
Введение
История алгоритма связана сразу с тремя независимыми математиками: Лестером Фордом, Ричардом Беллманом и Эдвардом Муром. Форд и Беллман опубликовали алгоритм в 1956 и 1958 годах соответственно, а Мур сделал это в 1957 году. И иногда его называют алгоритмом Беллмана - Форда - Мура. Метод используется в некоторых протоколах дистанционно-векторной маршрутизации, например в RIP (Routing Information Protocol - Протокол маршрутной информации).
Также как и алгоритм Дейкстры, алгоритм Беллмана - Форда вычисляет во взвешенном графе кратчайшие пути от одной вершины до всех остальных. Он подходит для работы с графами, имеющими ребра с отрицательным весом. Но спектр применимости алгоритма затрагивает не все такие графы, ввиду того, что каждый очередной проход по пути, составленному из ребер, сумма весов которых отрицательна (т.е. по отрицательному циклу), лишь улучшает требуемое значение. Бесконечное число улучшений делает невозможным определение одного конкретного значения, являющегося оптимальным. В связи с этим алгоритм Беллмана - Форда не применим к графам, имеющим отрицательные циклы, но он позволяет определить наличие таковых, о чем будет сказано позже.
В качестве среды разработки мною была выбрана среда Microsoft Visual Studio 2015, язык программирования - С++.
В ходе выполнения данной курсовой работы были приобретены навыки работы с формами и их элементами в среде Microsoft Visual Studio 2015, навыки работы с проектами и многомодульными программами.
1. Постановка задачи
Требуется разработать программу, которая находит минимальное расстояние между выбранной вершиной и остальными вершинами, используя алгоритм Форда-Беллмана.
Исходный граф в программе должен задаваться матрицей смежности, причём при вводе данных должны быть предусмотрены граничные условия, должна выполняться проверка корректности введенных данных. Устройства ввода данных - клавиатура и мышь.
2. Теоретическая часть задания
Общие теоретические сведения
Пусть нам дана матрица весов С(D) орграфа D и начальная вершина s. Найдем расстояния от вершины s до всех вершин орграфа D: D[v] = d (s, v), v V.
1. Всем вершинам vV орграфа присвоим метку D[v] = csv. Вершине s присвоим метку D[s] = 0.
2. Положим k=1.
3. Выберем произвольную вершину v V \ {s}.
4. Выберем произвольную вершину u V.
5. Положим D[v] = min (D[v], D[u] + cuv).
6. Если вершина u пробежала еще не все множество вершин V, то выбрать среди оставшихся произвольную вершину и вернуться к шагу 5.
7. Если вершина v пробежала еще не все множество вершин V \ {s}, то выбрать среди оставшихся произвольную вершину и перейти к шагу 4.
8. Если k < n-2, то положить k=k+1 и вернуться к шагу 3, иначе алгоритм заканчивает свою работу, полученные значения D[v] будут равны расстояниям d (s, v) в орграфе D.
Отметим, что закончить вычисления можно, когда выполнение цикла по k не вызывает изменения ни одной из переменных D[v].
3. Описание алгоритма программы
Решить задачу, т.е. найти все кратчайшие пути из вершины s до всех остальных, используя алгоритм Беллмана - Форда, это значит воспользоваться методом динамического программирования: разбить ее на типовые подзадачи, найти решение последним, покончив тем самым с основной задачей. Здесь решением каждой из таких подзадач является определение наилучшего пути от одного отдельно взятого ребра, до какого-либо другого. Для хранения результатов работы алгоритма заведем одномерный массив d[]. В каждом его i-ом элементе будет храниться значение кратчайшего пути из вершины s до вершины i (если таковое имеется). Изначально, присвоим элементам массива d[] значения равные условной бесконечности (например, число заведомо большее суммы всех весов), а в элемент d[s] запишем нуль. Так мы задействовали известную и необходимую информацию, а именно известно, что наилучший путь из вершины s в нее же саму равен 0, и необходимо предположить недоступность других вершин из s. По мере выполнения алгоритма, для некоторых из них, это условие окажется ложным, и вычисляться оптимальные стоимости путей до этих вершин из s.
Задан граф G=(V, E), n=|V|, а m=|E|. Обозначим смежные вершины этого графа символами v и u, а вес ребра (v, u) символом w. Иначе говоря, вес ребра, выходящего из вершины v и входящего в вершину u, будет равен w. Тогда ключевая часть алгоритма Беллмана - Форда примет следующий вид:
Для i от 1 до n-1 выполнять. Для j от 1 до m выполнять. Если d[v] + w (v, u) d[u], то d[u] < d[v] + w (v, u).
На каждом n-ом шаге осуществляются попытки улучшить значения элементов массива d[]: если сумма, составленная из веса ребра w (v, u) и веса хранящегося в элементе d[v], меньше веса d[u], то она присваивается последнему.
4. Ручной расчёт задачи
Пример. Определим минимальные пути из вершины v1 до всех остальных вершин в нагруженном графе D, изображенном на рис. 1.
Рисунок 1. Исходный граф
Ниже в таблице 1 приведены матрица весов, а также все вычисления по шагам.
Таблица 1. Матрица весов
На первом шаге всем вершинам vV графа присвоим метку D[v] = csv, где s = v1. Выберем следующую вершину v2. Ей присвоим метку D[v2] = min (D[v2], D[u] + cuv), где u V, т.е. D[v2] = min (D[v2], D[v3]+ c32, D[v4]+ c42, D[v5]+ c52, D[v6]+ c62) = (, 5+2, 5+2, 2+, 12+) = 7. Зафиксируем, что эта метка может быть получена из вершин 3 или 4.
Аналогично корректируются метки всех оставшихся вершин, а именно,
D[v3] = min (D[v3], D[v2]+c23, D[v4]+c43, D[v5]+c53, D[v6]+c63) = (5,7+, 5+, 2+1, 12+) = 3,
D[v4] = min (D[v4], D[v2]+c24, D[v3]+c34, D[v5]+c54, D[v6]+c64) = (5,7+, 3+, 2+2, 12+) = 4,
D[v5] = min (D[v5], D[v2]+ c25, D[v3]+ c35, D[v4]+ c45, D[v6]+ c65) = (2,7+, 3+, 4+, 12+) = 2,
D[v6] = min (D[v6], D[v2]+ c26, D[v3]+ c36, D[v4]+ c46, D[v5]+ c56) = (12,7+2, 3+, 4+, 2+) = 9.
Т.к. метки вершин изменились, то продолжаем процесс дальше. Результаты третьей и четвертой итераций совпали, значит итерационный процесс можно закончить, кроме того k = n-2 = 4.
Величины, стоящие в последнем столбце, и дают длины минимальных путей из вершины v1 до всех остальных вершин. Например, длина минимального пути из v1 в v2 равна 5, сам путь имеет вид: v1v5v3v2.
Ответ сошелся с результатом программы.
5. Описание программы
Основные модули
Программа разбита на несколько модулей. MyForm.cpp - главный файл проекта. В нем осуществляется запуск главного окна Form(), реализация класса формы и функции Main().
Файл MyForm.h отвечает за внешний вид главного окна, а именно: заголовок, пункты меню. Также в этом файле осуществляются сам алгоритм поиска кратчайшего расстояния от одной вершины графа до всех остальных. Листинг программы находится в приложении А.
6. Описание работы программы
алгоритм программа листинг
На рис. 3 изображен запуск приложения:
Рисунок 4. Исходное состояние
В нем мы указываем количество вершин, номер вершины от которой будем считать расстояние, а также заполняем матрицу весов графа.
Пользователь вводит матрицу весов с клавиатуры, каждый элемент - в отдельную ячейку. Окно ввода данных изображено на рис. 4:
Рисунок 5. Окно ввода данных
После ввода количества вершин в соответствующее текстовое поле, следует нажать кнопку «Рассчитать». В результате в правом окне мы увидим кратчайшее расстояние от выбранной вершины графа до всех оставшихся, а так же сам граф. На рис. 5 изображен результат работы программы, так же результаты работы отображены в листинге В.
Рисунок 6. Результат выполнения программы
7. Тестирование
В процессе тестирования проверялась реакция программы на неверно введенные данные при заполнении матрицы весов графа. Ошибки изображены на рисунках 6-8.
Обработка некорректных значений при заполнении матрицы смежности.
При вводе букв в строку, где содержится количество вершин:
Рисунок 7. Обработка ошибки
При вводе отрицательного числа в строку для начальной вершины:
Рисунок 8. Обработка ошибки
При вводе единицы на главной диагонали:
Рисунок 9. Обработка ошибки
алгоритм программа листинг
В результате тестирования было выявлено, что программа успешно проверяет введенные с клавиатуры данные на соответствие необходимым требованиям.
Размещено на Allbest.ru
...Подобные документы
Блок-схема алгоритма Флойда. Разработка его псевдокода в программе Microsoft Visual Studio. Программа реализации алгоритмов Беллмана-Форда. Анализ трудоемкости роста функции. Протокол тестирования правильности работы программы по алгоритму Флойда.
курсовая работа [653,5 K], добавлен 18.02.2013Понятие и сущность графы, методы решения задач по поиску кратчайших путей в ней. Особенности составления программного кода на языке программирования Pascal с использованием алгоритма Форда-Беллмана, а также порядок ее тестирования с ручным просчетом.
курсовая работа [1,2 M], добавлен 31.07.2010Содержательная и формальная (математическая) постановка задачи. Разработка алгоритма решения задачи. Структуры программы и алгоритмы программных модулей, их описание. Решение задачи на конкретном примере. Разработка системы тестов и отладка программы.
курсовая работа [882,1 K], добавлен 24.11.2014Анализ алгоритмов нахождения кратчайших маршрутов в графе без отрицательных циклов: Дейкстры, Беллмана-Форда и Флойда-Уоршалла. Разработка интерфейса программы на языке C++. Доказательство "правильности" работы алгоритма с помощью математической индукции.
курсовая работа [1,5 M], добавлен 26.07.2013Общие сведения о работе программы в среде программирования Microsoft Visual Studio 2008, на языке программирования C++. Ее функциональное назначение. Инсталляция и выполнение программы. Разработанные меню и интерфейсы. Алгоритм программного обеспечения.
курсовая работа [585,5 K], добавлен 24.03.2009Microsoft Visual C++ и среда программирования Microsoft Developer Studio 6.0. Решение интеллектуальной задачи на компьютере. Построение алгоритма кодирования на Visual C++. Алгоритм решения задачи. Описание программы "Sort". Инструкции пользователя.
курсовая работа [46,0 K], добавлен 27.11.2007Разработка игры "Угадай персонажа", ее суть и содержание. Запоминание новых персонажей и вопросов, коррекция базы данных. Использование языка программирования С++ и среды разработки Microsoft Visual Studio 2010. Алгоритмы и методы, структура программы.
курсовая работа [571,9 K], добавлен 14.07.2012Создание программы с использованием принципов объектно-ориентированного программирования на языке высокого уровня С# средствами Microsoft Visual Studio 2010. Построение алгоритма реализации. Определение математического аппарата, применение его в задаче.
курсовая работа [500,4 K], добавлен 13.01.2015Проведение сравнительного анализа языков программирования. Создание алгоритма и специфика составления математической модели программы "Механические часы, показывающие текущее время" в среде Microsoft Visual Studio 2010, на базе языка программирования С++.
курсовая работа [408,9 K], добавлен 11.03.2013Создание программы, реализующей игру "Линии". Среда разработки программы, описание ее общего вида. Основные алгоритмы программы. Реализация программы в среде разработки Microsoft Visual Studio 2008 на языке объектно-ориентированного программирования С++.
курсовая работа [639,0 K], добавлен 16.03.2012История создания алгоритма Форда-Фалкерсона, краткое описание его алгоритма, особенности работы, анализ сложности. Создание распараллеленного варианта алгоритма и его краткое описание. Основные характеристики теории графов, специфика, пути и маршруты.
контрольная работа [246,3 K], добавлен 06.08.2013Математическое описание задачи решения обыкновенного дифференциального уравнения численным явным методом Рунге-Кутта, разработка схемы алгоритма и написание программы в среде программирования Microsoft Visual Studio 2010. Тестирование работы программы.
курсовая работа [1,1 M], добавлен 22.01.2014Структура и основные операции коммерческого банка. Использование языка программирования Visual Basic for Application, математическая формулировка задачи. Разработка модуля программы расчёта кредитов и депозитов. Схема алгоритма выполнения программы.
курсовая работа [2,9 M], добавлен 09.04.2012Программа по созданию стрелочных часов. Минимальные требования к составу и параметрам технических средств программы. Выбор и обоснование системы программирования Microsoft Visual Studio. Общее описание алгоритма. Руководство пользователя и программиста.
контрольная работа [1017,1 K], добавлен 11.12.2012Задача о кратчайшем пути как одна из важнейших классических задач теории графов. Общий обзор трех наиболее популярных алгоритмов для решения задачи о кратчайшем пути. Написание программы, которая реализует алгоритм Дейкстры и алгоритм Форда-Беллмана.
курсовая работа [2,1 M], добавлен 23.06.2014Приемы программирования в Delphi. Алгоритм поиска альфа-бета отсечения, преимущества. Описание программного средства. Разработка программы, реализующая алгоритм игры "реверси". Руководство пользователя. Листинг программы. Навыки реализации алгоритмов.
курсовая работа [357,1 K], добавлен 28.02.2011Разработка программы FileInfo, выдающей полную информацию о заданном файле с применением языка программирования С++, используя API функции Win 32. Использование пространств имён .NetFramework. Руководство пользователя и системные требования программы.
курсовая работа [1,2 M], добавлен 25.04.2012Описание алгоритма решения задачи графическим способом. Вывод элементов массива. Описание блоков укрупненной схемы алгоритма на языке Pascal. Листинг программы, а также ее тестирование. Результат выполнения c помощью ввода различных входных данных.
контрольная работа [150,4 K], добавлен 03.05.2014Разработка программы с использованием языка программирования Pascal для выполнения алгебраических действий с действительными числами без знака в шестнадцатеричной системе счисления. Описание хода выполнения, схема алгоритма, листинг программы, ее функции.
реферат [687,5 K], добавлен 28.10.2011Разработка алгоритма и программы "Расчет стыкового паяного соединения" в среде Microsoft Visual Studio для облегчения расчётов сварных швов. Создание главной формы приложения и его кодирование для расчёта углового шва. Тестирование программы на ошибки.
курсовая работа [1,5 M], добавлен 06.02.2013
