Разработка алгоритма и программного обеспечения для решения прикладной задачи теории графов

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ

ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«ТЮМЕНСКИЙ ГОСУДАРСТВЕННЫЙ НЕФТЕГАЗОВЫЙ УНИВЕРСИТЕТ»

КАФЕДРА ИНФОРМАТИКИ И ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ

КУРСОВАЯ РАБОТА

По дисциплине «Дискретная математика»

Тема: Разработка алгоритма и программного обеспечения для решения прикладной задачи теории графов.

Выполнил

студент группы

АСОиУзс-07-01

Быстров Евгений М.

Шифр: 742301020016500

Проверил

Гапанович И.В..

Тюмень 2008

Содержание.

1. Введение. Постановка задачи.	3
2. Назначение и область применения.	3
3. Описание алгоритма решения задачи.	3
4. Ручной просчёт.	4
5. Описание программы.	6
6. Тестирование программы.	7
7. Литература.	9
8. Приложение 1. Листинг программы.	10

1. Введение. Постановка задачи.

Задание на курсовую работу по дисциплине «Дискретная математика».

Студент группы АСОиУзс-07-01 Быстров Евгений М.

Специальность «Автоматизированные системы обработки информации и управления»

Тема: Разработка алгоритма и программного обеспечения для решения прикладной задачи теории графов.

ЗАДАНИЕ 13 . Построить гамильтонову цепь в графе, используя алгоритм с возвратом.

Определения.

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

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

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

Матрица смежности графа – квадратная матрица, показывающая взаимосвязь вершин и рёбер.

2. Назначение и область применения.

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

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

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

Для того, что сократить число шагов в предложенном методе, рассмотрим следующий алгоритм. Предположим, что решение имеет вид последовательности v1…vi. Идея метода состоит в следующем: решение строится последовательно, начиная с пустой последовательности (длины 0). Далее, имея частичное решение ищем такое допустимое значение vi+1, которое ещё не было использовано, добавляем его к пройденному частичному решению и продолжаем процесс для нового частичного решения v1…vi+1. В противном случае, если такого значения vi+1 не существует, возвращаемся к предыдущему частичному решению v1…vi-1 и продолжаем процесс, пытаясь определить новое, еще не использованное допустимое значение vk. Такие алгоритмы носят название «алгоритмы с возвратом». Процесс поиска с возращением будет продемонстрирован в разделе «Ручной просчет» и «Тестирование программы» на примерах, показывающих как работает программа.

Алгоритм работы программы:

1. Создаётся пустая последовательность цепи длиной v (количество вершин).
2. Создаётся динамический массив для таблицы смежности графа, который заполняется из файла или прямо из программы.
3. Начинается поиск цепи с первой вершины (нулевая для матрицы).
4. Поочерёдно просматривается матрица смежности циклом for(где i - строка, j - столбец). Если от вершины идёт ребро , то проверяем была ли уже такая вершина. Если такая вершина уже есть в пути, то выходим из цикла и ищем следующую вершину. Если такой вершины не было, то записываем вершину в путь и продолжаем поиск с найденной вершины. Здесь же проверяем: если это последняя j-тая вершина, а ребер больше нет, то проверяем готова ли цепь, если последняя вершина пути не пуста, то цепь найдена. Если цепь не готова, записываем частичное решение сначала в переменную временной цепи (tempput), затем сравниваем это значение пути с уже имеющимися, если найдено совпадение, то возвращаемся на предыдущую вершину, а если такого пути не было, то записываем неполный путь в список временных путей.

Если идет не ребро , если это последняя j-тая вершина, а ребер больше нет, то проверяем готова ли цепь. Если последняя вершина пути не пуста, то цепь найдена. Если цепь не готова записываем частичное решение сначала в переменную временной цепи (tempput), затем сравниваем это значение пути с уже имеющимися, если найдено совпадение,

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать