Алгоритмизация в инженерных задачах

Размещено на http://www.allbest.ru/

1

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

Пензенский государственный университет

Кафедра «Информатика и вычислительная техника»

Пояснительная записка

к курсовой работе

Алгоритмизация в инженерных задачах

Выполнил: Исхаков Н.В.

студент группы 16ВВ2

Принял: Пащенко Д.В., Малютина Г.И.

Пенза

2017

Оглавление

• Введение
• Постановка задачи
• Теоретическая часть
• Описание алгоритма решения поставленной задачи
• Ручной просчет
• Описание программы
• Тесты
• Литература
• Введение
• Алгоритмизация задачи представляет собой процесс составления алгоритма ее решения. Алгоритм - строго определенная процедура, гарантирующая получение результата за конечное число шагов.
• Логика и основы алгоритмизации в инженерных задачах связанна с построением графов. Так как для решения задачи необходимо составить алгоритм и разработать программу, которая будет работать на основе расчетов.
• В графах основными элементами являются вершины и связи (ребра) между этими вершинами. Граф может изображать сеть улиц в городе, вершины графа -- перекрестки, стрелками обозначены улицы с разрешенным направлением движения. (Улицы могут быть с односторонним и двусторонним движением.)
• На этом применение графов не заканчивается. Можно составить граф любой позиционной игры: шахмат, шашек, «крестиков - ноликов».
• Здесь позиции станут вершинами, а направленные отрезки между ними будут означать, что одним ходом можно перейти от одной позиции к другой, по направлению стрелки.
• Графами являются блок - схемы программ для ЭВМ, а так же любые электрические цепи или электрическая сеть.
• Немало поводов для появления графов и в математике. Наиболее очевидный пример - любой многогранник в трёхмерном пространстве.
• Помимо этого графы можно использовать в: в психологии при исследовании межличностных отношений в группах, представить схему метрополитена, железных дорог, авиалиний, блок-схем, генеалогического древа.
• Постановка задачи
• Необходимо разработать программу с графическим интерфейсом, реализующую нахождение минимального остова графа по алгоритм Краскала.
• Необходимо написать и отладить программу, выполняющую нахождение остова минимального веса. В результате работы программы должен строиться граф и остов минимального веса с указанием всех вершин, а так же выводится матрица смежности для графа и остова со всеми значениями длин ребер. Программа должна позволять интерактивно изменять значения длины ребер, связывающих вершины графа. Программа должна иметь интуитивно понятный интерфейс, и меню помощи.
• Программа так же должна обладать дополнительными функциями, такими как: заполнение матрицы случайными числами, подсчет длины графа, меню помощи, оповещение о несуществовании остова.
• Сама программа должна быть реализована на языке Visual C (C++), так как этот язык имеет свои достоинства. Одно из главных достоинств - это высокое быстродействие написанной программы.

Теоретическая часть

Граф -- абстрактный математический объект, представляющий собой множество вершин графа и набор рёбер, то есть соединений между парами вершин.

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

Остовное дерево -- ациклический связный подграф данного связного неориентированного графа, в который входят все его вершины.

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

Таким образом остовов у графа может быть несколько, а минимальный остов только один.

Алгоритм Краскала -- эффективный алгоритм построения минимального остовного дерева взвешенного связного неориентированного графа.

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

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

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

Описание алгоритма решения поставленной задачи

Для решения задачи используется алгоритм Краскала.

Рисунок 1. Алгоритм Краскала

алгоритмизация программа краскал

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

Существуют два способа окончания работы алгоритма Краскала. Если мы найдем V- 1 ребер, то мы уже построили остовное дерево и можем остановиться. Если мы просмотрим все вершины и не найдем V-- 1 древесных ребер, то это означает, что граф не является связным. Алгоритм приведен на рисунке 1

Ручной просчет

Рисунок 2. Начальный граф

Имеется граф (рис. 2), необходимо найти остов минимального веса.

Начало алгоритма Краскала:

Каждую вершину примем за отдельную компоненту.

Найдем ребро, имеющее минимальный вес и соединим две вершины.(рис. 3)

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

После опять выбираем следующую по минимальному весу ребро и соединяем две разные компоненты. (рис. 5)

Рисунок 3

Рисунок 4

Рисунок 5

Следующее по минимальности веса ребро имеет 20 единиц, соединяющее 1 и 5 вершину, но их соединить нельзя, так как это ребро соединяет одну и ту же компоненту графа. Поэтому берем следующее ребро, которое имеет вес в 25 единиц и соединяет 3 и 4 вершину. Оно уже соединяет разные компоненты, а значит это ребро нужно использовать. (рис. 6)

Рисунок 6

Мы соединили 5 вершин 4 ребрами, поэтому нужно прекратить поиск следующих ребер, потому что минимальный остов уже построен.

Конец алгоритма Краскала.

Описание программы

Программа строит минимальный вес остова графа по алгоритму Краскала.

Язык программирования, на котором написана программа - Visual C(C++)

Пользователь должен задать матрицу смежности в программе с помощью ползунка, затем нажать на кнопку «ОК», после чего нажать на кнопку «Расчет» для нахождения минимального веса остова графа, если таблицу слишком долго заполнять, то у пользователя есть возможность заполнения матрицы смежности случайными числами. Так же если человек первый раз видит программу у него есть возможность просмотреть описание программы и назначение каждой из клавиш, нажав на кнопку «Помощь».

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

Интерфейс программы (рис.7)

Рисунок 7. Интерфейс программы

Вверху находится панель управления, состоящая из четырех кнопок:

«ОК» - задать матрицу смежности (Существующая матрица будет обнулена)

«Расчет» - произвести расчет поиска минимального остова

«Рандом» - заполнить матрицу случайными числами

«Помощь» - вызвать меню помощи.

Ниже располагается сама матрица смежности графа.

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

Программа может вывести помощь начинающему пользователю.(рис. 8)

Рисунок 8. Помощь

Слева от двух матриц расположено поле вывода графического изображения графа со всеми вершинами и связями. При возможности можно отключить или включить отображение веса ребер минимального остова. Так же программа выводит численный вес всего остова. (рис. 9)

Рисунок 9. Отображение веса

Тесты

Удачный запуск программы, остов минимального веса построен верно.(рис. 10)

Рисунок 10. Удачный запуск