Автор работы: Пользователь скрыл имя, 05 Мая 2013 в 21:13, курсовая работа
Пока неизвестно никакого простого критерия или алгебраического метода, позволяющего ответить на вопрос, существует или нет в произвольном графе G гамильтонов цикл. Критерии существования, данные выше, представляют теоретический интерес, но являются слишком общими и не пригодны для произвольных графов, встречающихся на практике. Алгебраические методы определения гамильтоновых циклов не могут быть применены с более чем несколькими десятками вершин, так как они требуют слишком большого времени работы и большой памяти компьютера. Более приемлемым является способ Робертса и Флореса, который не предъявляет чрезмерных требований к памяти компьютера, но время в котором зависит экспоненциально от числа вершин в графе.
Основная цель данной курсовой работы состоит в том, что нужно написать программу реализующую алгоритм поиска гамильтонова цикла в графе переборным методом Робертса и Флореса.
Введение 4
1 Постановка задачи 6
2 Алгоритм Робертса и Флореса 7
2.1 Улучшение метода Робертса и Флореса 10
3 Реализация алгоритма и его описание 12
4 Примеры работы программы 16
Заключение 19
Список использованной литературы 20
Приложение А Листинг программной реализации алгоритма поиска гамильтонова цикла переборным методом Робертса и Флореса 21
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ
УЧРЕЖДЕНИЕ ВЫСШЕГО
«ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ – УЧЕБНО-НАУЧНО-
ПРОИЗВОДСТВЕННЫЙ КОМПЛЕКС»
Кафедра «Информационные системы»
Работа допущена к защите
___________________
«»____»» ___________ 2012г.
КУРСОВАЯ РАБОТА
на тему: «Реализация алгоритма поиска в Гамильтонова цикла в графе переборным методом Робертса и Флореса»
по дисциплине «Интеллектуальные информационные системы»
Выполнил: ______________Щеголев С.Д. Шифр: 090271
Факультет УНИИ ИТ
Направление / специальность: Прикладная информатика (в экономике)
Группа: 41 – ЭИ
Преподаватель: Стычук А.А.
Орел, 2012
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ
УЧРЕЖДЕНИЕ ВЫСШЕГО
«ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ – УЧЕБНО-НАУЧНО-
ПРОИЗВОДСТВЕННЫЙ КОМПЛЕКС»
Кафедра «Информационные системы»
ЗАДАНИЕ
на курсовую работу
УТВЕРЖДАЮ:
____________Зав. кафедрой
«___»_____________2012 г.
по дисциплине
«Интеллектуальные информационные системы»
Студент Щеголев С.Д. Шифр 090271
Факультет УНИИ ИТ
Специальность Прикладная информатика
Группа 41-ЭИ
1 Тема курсовой работы
«Реализация алгоритма поиска в Гамильтонова цикла в графе переборным методом Робертса и Флореса»
2 Срок сдачи студентом законченной работы 29 декабря 2012 г
3 Исходные данные
В главном окне приложения отобразить меню, при помощи которого можно изменять внешний вид окна
4 Содержание пояснительной записки
Постановка задачи
Алгоритм Роберста и Флореса
Реализация алгоритма LISP – программы и ее описание
Примеры
5 Отчетный материал курсовой работы
Пояснительная записка, программа, реализующая поставленную задачу
Руководитель ____________ Стычук А.А.
Задание принял к исполнению: «15» марта 2012 г.
Подпись студента______________________