Автор работы: Пользователь скрыл имя, 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
Учебно-научно-
Специальность 080801 «Прикладная информатика (в экономике)»
Группа 41-ЭИ
1 Тема курсовой работы
«Реализация алгоритма поиска гамильтонова цикла в графе переборным методом Робертса и Флореса»
2 Срок сдачи студентом законченной работы: «29» декабря 2012 г.
3 Исходные данные
Теоретические сведения по алгоритму поиска гамильтонова цикла в графе переборным методом Робертса-Флореса
4 Содержание курсовой работы
Постановка задачи
Алгоритм Робертса и Флореса
Улучшение метода Робертса и Флореса
Реализация алгоритма и его описание
Примеры работы программы
5 Отчетный материал курсовой работы
Пояснительная записка курсовой работы; программа на языке LISP, записанная на CD-диске; презентация
Руководитель
Задание принял к исполнению: «15» сентября 2012 г.
Подпись студента ___________________