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

Введение

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

Для удовлетворения требований задачи был выбрал язык C++. C++ --компилируемый, статически типизированный язык программирования общего назначения. Язык имеет богатую стандартную библиотеку, которая включает в себя распространённые контейнеры и алгоритмы, ввод-вывод, регулярные выражения, поддержку многопоточности и другие возможности. C++ сочетает свойства как высокоуровневых, так и низкоуровневых языков. В сравнении с его предшественником -- языком C, -- наибольшее внимание уделено поддержке объектно-ориентированного и обобщённого программирования.

C++ широко используется для разработки программного обеспечения, являясь одним из самых популярных языков программирования. Область его применения включает создание операционных систем, разнообразных прикладных программ, драйверов устройств, приложений для встраиваемых систем, высокопроизводительных серверов, а также развлекательных приложений (игр).

Существует множество реализаций языка C++, как бесплатных, так и коммерческих и для различных платформ. Например, на платформе x86 это GCC, Visual C++, Intel C++ Compiler, Embarcadero (Borland) C++ Builder и другие.

Синтаксис C++ унаследован от языка C. Одним из принципов разработки было сохранение совместимости с C. Тем не менее, C++ не является в строгом смысле надмножеством C; множество программ, которые могут одинаково успешно транслироваться как компиляторами C, так и компиляторами C++, довольно велико, но не включает все возможные программы на C.

2.Теоретическая часть задания

Множество вершин U графа G = (V,X) называется независимым (внутренне устойчивым), если никакие две вершины из этого множества не смежны. Другими словами, если U V и U независимо в графе G, то порожденный подграф G(U) является пустым. Очевидно, что если при этом U* U, то U* - также независимое множество.

Очевидный алгоритм, который можно применить для нахождения независимых множеств вершин, это «полный перебор всех возможностей»: генерируем все возможные подмножества вершин заданного графа или орграфа и проверяем, является ли оно независимым. Среди всех независимых множеств выбираем максимальные. Опишем теперь общий метод, позволяющий значительно сократить число шагов в алгоритмах полного перебора всех возможностей. Чтобы применить этот метод, представим искомое решение в виде последовательности <x1,…x n>. Основная идея метода состоит в том, что решение строится последовательно, начиная с пустой последовательности е (длины 0). Вообще, имея данное частичное решение <x1,…x k>, мы стараемся найти такое допустимое значение x k+1, относительно которого мы не можем сразу сказать, что <x1,…x k, x k+1> можно расширить до некоторого решения (либо <x1,…x k, x k+1> уже является решением). Если такое предполагаемое, но еще не использованное значение x k+1 существует, то мы добавляем его к нашему частичному решению и продолжаем процесс для последовательности <x1,…x k, x k+1>. Если его не существует, то мы возвращаемся к нашему частичному решению <x1,…x k-1> и продолжаем процесс, отыскивая новое, еще не использованное допустимое значение xk - отсюда название «алгоритм с возвратом» (англ.: backtracking).

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

В качестве алгоритма для нахождения независимых множеств, рассмотрим алгоритм с возвратом. Идея алгоритма с возвратами состоит в следующем. Находясь в некоторой ситуации, пробуем изменить ее в надежде найти решение. Если изменение не привело к успеху, то возвращаемся в исходную ситуацию (отсюда название «поиск с возвратами») и пробуем изменить ее другим образом, и так до тех пор, пока не будут исчерпаны все возможности.

В качестве среды программирования был выбран программный продукт Visual Studio 2017.

Сначала была разработана форма для удобной работы с программой.

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

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

4. Пример ручного расчёта задачи и вычислений

Рисунок 1. Граф для ручного расчета части программы

Для ручного расчёта решим задачу. Представим граф с 4 вершинами. Выбранный граф изображен на рисунке 1.

1. Задаем пустое множество вершин, которое тоже является независимым, но нам нужно наибольшее.

2. Проверяем первую вершину на смежность. Так как первая вершина не смежна ни с одно вершиной из текущего множества, то добавляем ее в множество{1}.Полученное множество снова независимо, но нам нужно наибольшее.

3. Возьмем вершину 2. Проверим ее на смежность с элементами множества. Вершина 2 смежна с вершиной 1 из множества {1}.

4. Берем вершину 3.Проверим ее на смежность с элементами множества. Вершина 3 смежна с вершиной 1 из множества {1}.

5. Берем вершину 4. Она не смежна ни с одной вершиной множества {1}, добавляем ее в множество. Получаем множество {1,4}.

6. Номер текущей вершины больше, чем количество вершин в множестве.

7. Возвращаемся на предыдущий уровень.

8. Берем следующую вершину. Это вершина 2. Проверяем ее на смежность с элементами множества. Так как множество пустое, записываем ее в множество. Получаем множество {2}.

9. Проверяем вершину 3 на смежность с элементами множества, вершина не смежна, записываем ее в множество. Получаем {2,3}.

10. Проверяем вершину 4. Вершину 4 смежна с вершиной 2 из множества {2,3}.

11. Номер текущей вершины больше, чем количество вершин в множестве.

12. Возвращаемся на предыдущий уровень.

13. Берем следующую вершину. Это вершина 3. Проверяем ее на смежность с элементами множества. Так как множество пустое, записываем ее в множество. Получаем множество {3}.

14. Проверяем вершину 4 на смежность с элементами множества, вершина не смежна, записываем ее в множество. Получаем {3,4}.

15. Номер текущей вершины больше, чем количество вершин в множестве.

16. Поиск завершен.

Проверим программой.

Результат работы показан на рисунке 2.

Рисунок 2. Результат тестирования программы с графом для ручного расчета.

Результат ручного расчета совпал с результатом работы программы.

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

5.1 Общее описание

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

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

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

5.2 Функции программы

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

Функция «Intecface()»

Функция Intecface() отображает интерфейс.

Функция «Dann()»

Функция Dann() обрабатывает данные, введенные пользователем.

Функция «Backtracking()»

Функция Backtracking() главная функция программы. Именно она выполняет алгоритм с возвратом.

6. Тесты

Для тестирования используем 2 различных по типам наборов данных:

· Некорректное введение данных (Буква);

· Допустимое введение данных (Множество букв).

Проверка реакции программы на неверно введенные данные (буквы) в поле для генерации матрицы. Результат тестирования программы на исключения представлен на рисунках 3-4.

Рисунок 3. Результат тестирования программы с тестируемым набором «буква».

Так как программа ориентирована только на работу с цифрами, всплывает окно ошибок.

Проверка реакции программы на неверно введенные данные (буквы) в поле для количества вершин матрицы.

Рисунок 4. Окно ошибок при вводе в программу некорректной записи данных.

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

Проверка реакции программы на верно введенные данные представлена на рисунках 5-7.

Рисунок 5. Результат тестирования программы с графом, содержащим 4 вершины.

Рисунок 6. Результат тестирования программы с графом, содержащим 10 вершин.

Рисунок 7. Результат тестирования программы с графом, содержащим 3 вершины.

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

7. Результаты работы программы

На рисунках 8 - 10 представлена работа программы.

Рисунок 8. Состояние программы при запуске.

Рисунок 9. Состояние программы при выводе результата

Рисунок 10. Окно ошибок при вводе некорректного значения

Заключение

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

Список литературы

язык программирование алгоритм

1.Новиков Ф.А. «Дискретная математика для программистов» 2-е изд. - СПб.: Питер, 2000.

2.Электронныйресурс:https://www.intuit.ru/studies/courses/648/504/lecture/11464. Дата обращения: 01.11.2017.

3.Герберт Шилдт «Полный справочник по C++» - Вильямс, 2006 5. Х. М. Дейтел, П. Дж. Дейтел «Как программировать на C++» - Бином-Пресс, 2008.

4.М. Эллис, Б. Строуструп. Справочное руководство по языку C++ с комментариями: Пер. с англ. - Москва: Мир, 1992. 445с.

5.Х. Дейтел, П. Дейтел. Как программировать на C++: Пер. с англ. - Москва: ЗАО "Издательство БИНОМ", 1998. 1024с.

Размещено на Allbest.ru